Asymptotics of Permutations with Nearly Periodic Patterns of Rises and Falls

  • Edward A. Bender
  • William J. Helton
  • L. Bruce Richmond


Ehrenborg obtained asymptotic results for nearly alternating permutations and conjectured an asymptotic formula for the number of permutations that have a nearly periodic run pattern. We prove a generalization of this conjecture, rederive the fact that the asymptotic number of permutations with a periodic run pattern has the form $Cr^{-n}\,n!$, and show how to compute the various constants. A reformulation in terms of iid random variables leads to an eigenvalue problem for a Fredholm integral equation. Tools from functional analysis establish the necessary properties.

Article Number