The maximal-inversion statistic and pattern-avoiding permutations. (English) Zbl 1189.05009
Summary: We define a new combinatorial statistic, maximal-inversion, on a permutation. We remark that the number \(M(n,k)\) of permutations in \(S_n\) with \(k\) maximal-inversions is the signless Stirling number \(c(n,n - k)\) of the first kind. A permutation \(\pi \) in \(S_n\) is uniquely determined by its maximal-inversion set MI\((\pi)\). We prove it by making an algorithm for retrieving the permutation from its maximal-inversion set. Also, we remark on how the algorithm can be used directly to determine whether a given set is the maximal-inversion set of a permutation. As an application of the algorithm, we characterize the maximal-inversion set for pattern-avoiding permutations. Then we give some enumerative results concerning permutations with forbidden patterns.
MSC:
| 05A05 | Permutations, words, matrices |
References:
| [1] | Bóna, M., Combinatorics of Permutations (2004), Chapman & Hall/CRC · Zbl 1052.05001 |
| [2] | Comtet, L., Advanced Combinatorics (1974), Reidel: Reidel Boston · Zbl 0283.05001 |
| [3] | Foata, D., Distributions eulériennes et mahonniennes sur le groupe des permutations, (Higher Combinatorics (Proc. NATO Adv. Study Inst., Berlin, 1976; M. Aigner, Ed.) (1977), Reidel: Reidel Amsterdam), 27-49 · Zbl 0447.05004 |
| [4] | Foata, D., Rearrangements of words, in M. Lothaire, (Rota, G. C., Combinatorics on Words. Combinatorics on Words, Encyclopedia of Math. and its Appl., vol. 17 (1983), Addison-Wesley) · Zbl 0514.20045 |
| [5] | Foata, D.; Schützenberger, M. P., Major index and inversion number of permutations, Math. Nachr., 83, 143-159 (1978) · Zbl 0319.05002 |
| [6] | Foata, D.; Zeilberger, D., Denert’s permutation statistic is indeed Euler-Mahonian, Stud. Appl. Math., 83, 31-59 (1990) · Zbl 0738.05001 |
| [7] | Labelle, G.; Leroux, P.; Pergola, E.; Pinzani, R., Stirling numbers interpolation using permutations with forbidden subsequences, Discrete Math., 246, 177-195 (2002) · Zbl 1001.05007 |
| [8] | Mansour, T., Permutations avoiding a pattern from \(S_k\) and at least two patterns from \(S_3\), Ars Combin., 62, 227-239 (2001) · Zbl 1071.05004 |
| [9] | Rawlings, D., Permutation and multipermutation statistics, European J. Combin., 2, 67-78 (1981) · Zbl 0471.05006 |
| [10] | Simion, R.; Schmidt, F. W., Restricted permutations, European J. Combin., 6, 383-406 (1985) · Zbl 0615.05002 |
| [11] | Stanley, R. P., Enumerative Combinatorics, vol. 1 (1986), Wadsworth & Brooks/Cole: Wadsworth & Brooks/Cole Belmont, CA · Zbl 0608.05001 |
| [12] | Stanley, R. P., Binomial posets, Möbius inversion and permutation enumeration, J. Combin. Theory Ser. A, 20, 712-719 (1976) · Zbl 0331.05004 |
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.
