The Asymptotics of Almost Alternating Permutations

✍ Scribed by Richard Ehrenborg

• Book ID: 102559660
• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 144 KB
• Volume: 28
• Category: Article
• ISSN: 0196-8858
• DOI: 10.1006/aama.2001.0790

✦ Synopsis

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 β l 1 l k denote the number of permutations which consist of l 1 ascents, l 2 descents, l 3 ascents, and so on. By combining the Viennot triangle and the boustrophedon transform, we obtain the exponential generating function for the numbers β L 1 n-m-1 , where L is a descent-ascent list of size m. As a corollary we have β L 1 n-m-1 ∼ c L • E n , where E n = β 1 n-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 β 1 a 2 1 b ∼ 2/π • E n , when min a b tends to infinity and where n = a + b + 3. From this result we obtain that the asymptotic behavior of β L 1 1 a L 2 1 b L 3 is the product of three constants depending respectively on the lists L 1 , L 2 , and L 3 , times the Euler number E a+b+m+1 , where m is the sum of the sizes of the L i 's.  2002 Elsevier Science (USA)