Distributions of statistics over pattern-avoiding permutations. (English) Zbl 1407.05005
Summary: We consider the distribution of ascents, descents, peaks, valleys, double ascents, and double descents over permutations avoiding a set of patterns. Many of these statistics have already been studied over sets of permutations avoiding a single pattern of length 3. However, the distribution of peaks over 321-avoiding permutations is new, and we relate it to statistics on Dyck paths. We also obtain new interpretations of a number of well-known combinatorial sequences by studying these statistics over permutations avoiding two patterns of length 3.
MSC:
| 05A05 | Permutations, words, matrices |
| 05A10 | Factorials, binomial coefficients, combinatorial functions |
| 05A15 | Exact enumeration problems, generating functions |
| 05A19 | Combinatorial identities, bijective combinatorics |
Online Encyclopedia of Integer Sequences:
Triangle of Narayana numbers T(n,k) = C(n-1,k-1)*C(n,k-1)/k with 1 <= k <= n, read by rows. Also called the Catalan triangle.Pascal’s triangle read by rows: C(n,k) = binomial(n,k) = n!/(k!*(n-k)!), 0 <= k <= n.
Triangle of Eulerian numbers T(n,k) (n >= 1, 1 <= k <= n) read by rows.
Triangular array formed by taking every other term of each row of Pascal’s triangle.
Triangle of odd-numbered terms in rows of Pascal’s triangle.
Triangle a(n,k) giving number of binary sequences of length n containing k subsequences 00.
Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having k long ascents (i.e., ascents of length at least 2). Rows are of length 1,1,2,2,3,3,... .
Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n, having k ddu’s [here u = (1,1) and d = (1,-1)].
Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having exactly k UUU’s (triple rises) where U=(1,1). Rows have 1,1,1,2,3,4,5,... entries, respectively.
(3,1) Pascal triangle.
Binomial coefficients C(n,k) with n-k even, read by rows.
Triangle read by rows: T(n,k) is the number of circular binary words of length n having k occurrences of 01 (0 <= k <= floor(n/2)).
Triangle read by rows: number of (1-2-3)-avoiding permutations on n letters with k peaks.
Number of permutations of length n that avoid the patterns 213 and 312 and have k double ascents, read by rows.
References:
| [1] | M. Barnabei, F. Bonetti, and M. Silimbani, The descent statistic on 123 avoiding permutations, S´em. Lothar. Combin. 68 (2010), B63a. · Zbl 1267.05004 |
| [2] | A. M. Baxter, Refining enumeration schemes to count according to permutation statistics, Electron. J. Combin. 21 (2014), #P2.50. · Zbl 1300.05026 |
| [3] | T. Dokos, T. Dwyer, B. P. Johnson, B. E. Sagan, and K. Selsor, Permutation patterns and statistics. Discrete Math. 312 (2012), 2760-2775. · Zbl 1248.05004 |
| [4] | S. Elizalde, Statistics on pattern-avoiding permutations, Ph.D. thesis, MIT, 2004. |
| [5] | C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. Appl. Math. 27(2001), 510-530. · Zbl 0994.05001 |
| [6] | T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, Ann. Comb. 6 (2003), 407-418. · Zbl 1017.05011 |
| [7] | R. Pan, D. Qiu, and J. Remmel, Counting consecutive pattern matches in Sn(132) and Sn(123), Adv. Appl. Math. 105 (2019), 130-167. · Zbl 1407.05008 |
| [8] | T. K. Petersen, Eulerian Numbers, Birkh¨auser, 2015. · Zbl 1337.05001 |
| [9] | A. Robertson, D. Saracino, and D. Zeilberger, Refined restricted permutations, Ann. Comb. 6(2003), 427-444. · Zbl 1017.05014 |
| [10] | R. Simion and F. W. Schmidt, Restricted permutations, European J. Combin. 6 (1985), 383-406. · Zbl 0615.05002 |
| [11] | N. Sloane, The Encyclopedia of Integer Sequences, 2018. Available athttps://oeis. org. · Zbl 1439.11001 |
| [12] | FindStat, 2018. Available athttp://findstat.org. |
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.
