The asymptotics of almost alternating permutations

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)421-437
Number of pages17
JournalAdvances in Applied Mathematics
Volume28
Issue number3-4
DOIs
StatePublished - 2002

Bibliographical note

Funding 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.

Keywords

  • Boustrophedon transform
  • Euler number
  • Viennot triangle

ASJC Scopus subject areas

  • Applied Mathematics

Fingerprint

Dive into the research topics of 'The asymptotics of almost alternating permutations'. Together they form a unique fingerprint.

Cite this