Alternating permutations and symmetric functions. (English) Zbl 1118.05002
Summary: We use the theory of symmetric functions to enumerate various classes of alternating permutations \(w\) of \(\{1,2,\dots ,n\}\). These classes include the following: (1) both \(w\) and \(w^{-1}\) are alternating, (2) \(w\) has certain special shapes, such as \((m - 1,m - 2,\dots ,1)\), under the RSK algorithm, (3) \(w\) has a specified cycle type, and (4) \(w\) has a specified number of fixed points. We also enumerate alternating permutations of a multiset. Most of our formulas are umbral expressions where after expanding the expression in powers of a variable \(E, E^{k}\) is interpreted as the Euler number \(E_{k}\). As a small corollary, we obtain a combinatorial interpretation of the coefficients of an asymptotic expansion appearing in Ramanujan’s “Lost” Notebook.
MSC:
| 05A05 | Permutations, words, matrices |
| 05A15 | Exact enumeration problems, generating functions |
| 05A16 | Asymptotic enumeration |
| 05A40 | Umbral calculus |
| 05E05 | Symmetric functions and generalizations |
| 05E10 | Combinatorial aspects of representation theory |
Software:
EHRENBORGOnline Encyclopedia of Integer Sequences:
Euler (or secant or ”Zig”) numbers: e.g.f. (even powers only) sec(x) = 1/cos(x).Coefficients of asymptotic expansion of Ramanujan false theta series.
a(n) is the number of permutations w of 1,2,...,n such that both w and w^{-1} are alternating.
a(n) = number of reverse alternating fixed-point-free involutions w on 1,2,...,2n, i.e., w(1) < w(2) > w(3) < w(4) > ... < w(2n), w^2=1 and w(i) != i for all i.
Number of reverse alternating fixed-point-free permutations on n letters.
Number of alternating fixed-point-free permutations on n letters.
Number of alternating full cycles on n letters.
Triangle read by rows: T(n,k) is the number of alternating (i.e., down-up) permutations of {1,2,...,n} having k fixed points (n >= 0, 0 <= k <= ceiling(n/2)).
Triangle read by rows: T(n,k) is the number of reverse alternating (i.e., up-down) permutations of {1,2,...,n} having k fixed points (n >= 0, 0 <= k <= 1 + floor(n/2)).
a(n) is the number of permutations w of 1,2,...,n such that w is alternating and w^{-1} is reverse alternating.
a(n) is the number of totally alternating permutations of 1,2,...,n.
References:
| [1] | André, D., Développement de \(\sec x\) and tg \(x\), C. R. Math. Acad. Sci. Paris, 88, 965-979 (1879) |
| [2] | Andrews, G. E., Ramanujan’s “Lost” Notebook. 1. Partial \(θ\)-functions, Adv. Math., 41, 137-172 (1981) · Zbl 0477.33001 |
| [3] | Brendt, B. C., Ramanujan’s Notebooks, Part V (1998), Springer: Springer New York · Zbl 0886.11001 |
| [4] | Carlitz, L., Enumeration of up-down sequences, Discrete Math., 4, 273-286 (1973) · Zbl 0255.05003 |
| [5] | Foulkes, H. O., Enumeration of permutations with prescribed up-down and inversion sequences, Discrete Math., 15, 235-252 (1976) · Zbl 0338.05002 |
| [6] | Foulkes, H. O., Tangent and secant numbers and representations of symmetric groups, Discrete Math., 15, 311-324 (1976) · Zbl 0342.20005 |
| [7] | Galway, W. F., An asymptotic expansion of Ramanujan, (Gupta, R.; Williams, K. S., Number Theory, Fifth Conference of the Canadian Number Theory Association. Number Theory, Fifth Conference of the Canadian Number Theory Association, CRM Proc. Lecture Notes, vol. 19 (1999), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 107-110 · Zbl 0923.41018 |
| [8] | Gessel, I. M., Symmetric functions and \(P\)-recursiveness, J. Combin. Theory Ser. A, 53, 257-285 (1990) · Zbl 0704.05001 |
| [9] | Gessel, I. M.; Reutenauer, C., Counting permutations with given cycle structure and descent set, J. Combin. Theory Ser. A, 64, 189-215 (1993) · Zbl 0793.05004 |
| [10] | Guibert, O.; Linusson, S., Doubly alternating Baxter permutations are Catalan, Discrete Math., 217, 157-166 (2000) · Zbl 0965.05005 |
| [11] | Goulden, I. P.; Jackson, D. M., Combinatorial Enumeration (1983), Wiley: Wiley New York · Zbl 0519.05001 |
| [12] | Ismail, M.; Stanton, D., Classical orthogonal polynomials as moments, Canad. J. Math., 49, 520-542 (1997) · Zbl 0882.33012 |
| [13] | Krattenthaler, C., Advanced determinantal calculus, Séminaire Lotharingien Combin., 42 (1999), (electronic) article B42q, 67 pp · Zbl 0923.05007 |
| [14] | E. Ouchterlony, Pattern avoiding doubly alternating permutations, in: Proc. FPSAC (2006), in press, http://garsia.math.yorku.ca/fpsac06/papers/83_ps_or_pdf.ps; E. Ouchterlony, Pattern avoiding doubly alternating permutations, in: Proc. FPSAC (2006), in press, http://garsia.math.yorku.ca/fpsac06/papers/83_ps_or_pdf.ps |
| [15] | Rota, G.-C.; Taylor, B., The classical umbral calculus, SIAM J. Math. Anal., 25, 694-711 (1994) · Zbl 0797.05006 |
| [16] | Schocker, M., Multiplicities of higher Lie characters, J. Aust. Math. Soc., 75, 9-21 (2003) · Zbl 1037.20013 |
| [17] | Stanley, R., Enumerative Combinatorics, vol. 2 (1999), Cambridge Univ. Press: Cambridge Univ. Press New York · Zbl 0928.05001 |
| [18] | Zeilberger, D., I am sorry, Richard Ehrenborg and Margie Readdy, about your two conjectures, but one is famous while the other is false |
| [19] | Zeng, J., Weighted derangements and the linearization coefficients of orthogonal Sheffer polynomials, Proc. London Math. Soc. (3), 65, 1-22 (1992) · Zbl 0770.05006 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
