Counting permutations by runs. (English) Zbl 1336.05010
Summary: I. Gessel [Generating functions and enumeration of sequences. Cambridge, MA: Massachusetts Institute of Technology (PhD Thesis) (1977)] proved a reciprocity formula for noncommutative symmetric functions which enables one to count words and permutations with restrictions on the lengths of their increasing runs. We generalize Gessel’s theorem to allow for a much wider variety of restrictions on increasing run lengths, and use it to complete the enumeration of permutations with parity restrictions on peaks and valleys, and to give a systematic method for obtaining generating functions for permutation statistics that are expressible in terms of increasing runs. Our methods can also be used to obtain analogous results for alternating runs in permutations.
MSC:
| 05A15 | Exact enumeration problems, generating functions |
| 05A05 | Permutations, words, matrices |
| 05E05 | Symmetric functions and generalizations |
Software:
OEISOnline Encyclopedia of Integer Sequences:
Triangle read by rows: T(n,k) (n >= 1, 0 <= k <= ceiling(n/2)-1) = number of permutations of [n] with k peaks.Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k up-down runs (1 <= k <= n).
References:
| [1] | Bóna, M., Combinatorics of Permutations, Discrete Mathematics and Its Applications (2012), CRC Press · Zbl 1255.05001 |
| [2] | Chebikin, D., Variations on descents and inversions in permutations, Electron. J. Combin., 15, 1, Article 132 pp. (2008), 34 pp · Zbl 1179.05004 |
| [3] | David, F. N.; Barton, D. E., Combinatorial Chance (1962), Lubrecht & Cramer Ltd |
| [4] | Entringer, R. C., Enumeration of permutations of \((1, \cdots, n)\) by number of maxima, Duke Math. J., 36, 575-579 (1969) · Zbl 0186.01502 |
| [5] | Gelfand, I. M.; Krob, D.; Lascoux, A.; Leclerc, B.; Retakh, V. S.; Thibon, J.-Y., Noncommutative symmetric functions, Adv. Math., 112, 2, 218-348 (1995) · Zbl 0831.05063 |
| [6] | Gessel, I. M., Generating functions and enumeration of sequences (1977), Massachusetts Institute of Technology, PhD thesis |
| [7] | Gessel, I. M., A coloring problem, Amer. Math. Monthly, 98, 6, 530-533 (1991) · Zbl 0771.05009 |
| [9] | Gessel, I. M.; Zhuang, Y., Counting permutations by alternating descents, Electron. J. Combin., 21, 4, Article P4.23 pp. (2014), 21 pp · Zbl 1302.05007 |
| [10] | Goulden, I. P.; Jackson, D. M., Combinatorial Enumeration (1983), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York · Zbl 0519.05001 |
| [11] | Jackson, D. M.; Aleliunas, R., Decomposition based generating functions for sequences, Canad. J. Math., 29, 5, 971-1009 (1977) · Zbl 0345.05117 |
| [12] | Kitaev, S., Introduction to partially ordered patterns, Discrete Appl. Math., 115, 8, 929-944 (2007) · Zbl 1118.05001 |
| [13] | La Croix, M., A combinatorial proof of a result of Gessel and Greene, Discrete Math., 306, 18, 2251-2256 (2006) · Zbl 1103.05002 |
| [15] | Sloane, N. J.A., The On-Line Encyclopedia of Integer Sequences (2015), published electronically at: · Zbl 1044.11108 |
| [16] | Stanley, R. P., Longest alternating subsequences of permutations, Michigan Math. J., 57, 675-687 (2008) · Zbl 1247.05016 |
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.
