The goal of this paper is to study the asymptotic behavior of almost alternating permutations, that is, permutations that are alternating except for a finite number of exceptions. Let β(l1,...,lk) denote the number of permutations which consist of l1 ascents, l2 descents, l3 ascents, and so on. By combining the Viennot triangle and the boustrophedon transform, we obtain the exponential generating function for the numbers β(L, 1n-m-1), where L is a descent-ascent list of size m. As a corollary we have β(L, 1n-m-1) ∼ c(L)·En, where En = β(1n-1) denotes the nth Euler number and c(L) is a constant depending on the list L. Using these results and inequalities due to Ehrenborg-Mahajan, we obtain β(1a,2,1b) ∼ 2/π·En, when min(a, b) tends to infinity and where n = a+b+3. From this result we obtain that the asymptotic behavior of β(L1, 1a, L2, 1b, L3) is the product of three constants depending respectively on the lists L1, L2, and L3, times the Euler number Ea+b+m+1, where m is the sum of the sizes of the Li's.
|Number of pages||17|
|Journal||Advances in Applied Mathematics|
|State||Published - 2002|
Bibliographical noteFunding Information:
The author thanks Margaret Readdy and Doron Zeilberger for inspiring conversations. This research was supported by National Science Foundation, DMS 97-29992, and NEC Research Institute, Inc., while the author was a member of the Institute of Advanced Study. The paper was completed under Swedish Natural Science Research Council Grant DNR 702-238/98 and National Science Foundation, Grants DMS 98-00910 and DMS 99-83660, while visiting Cornell University.
- Boustrophedon transform
- Euler number
- Viennot triangle
ASJC Scopus subject areas
- Applied Mathematics