We launch a systematic study of the refined Wilf-equivalences by the statistics $ {\mathsf{comp}} $ and $ {\mathsf{iar}} $, where $ {\mathsf{comp}}(\pi) $ and $ {\mathsf{iar}}(\pi) $ are the number of components and the length of the initial ascending run of a permutation $ \pi $, respectively. As Comtet was the first one to consider the statistic $ {\mathsf{comp}} $ in his book Analyse combinatoire, any statistic equidistributed with $ {\mathsf{comp}} $ over a class of permutations is called by us a Comtet statistic over such class. This work is motivated by a triple equidistribution result of Rubey on $ 321 $-avoiding permutations, and a recent result of the first and third authors that $ {\mathsf{iar}} $ is a Comtet statistic over separable permutations. Some highlights of our results are:
● Bijective proofs of the symmetry of the joint distribution $ ({\mathsf{comp}}, {\mathsf{iar}}) $ over several Catalan and Schröder classes, preserving the values of the left-to-right maxima.
● A complete classification of $ {\mathsf{comp}} $- and $ {\mathsf{iar}} $-Wilf-equivalences for length $ 3 $ patterns and pairs of length $ 3 $ patterns. Calculations of the $ ({\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}}) $ generating functions over these pattern avoiding classes and separable permutations.
● A further refinement of Wang's descent-double descent-Wilf equivalence between separable permutations and $ (2413, 4213) $-avoiding permutations by the Comtet statistic $ {\mathsf{iar}} $.
Citation: Shishuo Fu, Zhicong Lin, Yaling Wang. Refined Wilf-equivalences by Comtet statistics[J]. Electronic Research Archive, 2021, 29(5): 2877-2913. doi: 10.3934/era.2021018
We launch a systematic study of the refined Wilf-equivalences by the statistics $ {\mathsf{comp}} $ and $ {\mathsf{iar}} $, where $ {\mathsf{comp}}(\pi) $ and $ {\mathsf{iar}}(\pi) $ are the number of components and the length of the initial ascending run of a permutation $ \pi $, respectively. As Comtet was the first one to consider the statistic $ {\mathsf{comp}} $ in his book Analyse combinatoire, any statistic equidistributed with $ {\mathsf{comp}} $ over a class of permutations is called by us a Comtet statistic over such class. This work is motivated by a triple equidistribution result of Rubey on $ 321 $-avoiding permutations, and a recent result of the first and third authors that $ {\mathsf{iar}} $ is a Comtet statistic over separable permutations. Some highlights of our results are:
● Bijective proofs of the symmetry of the joint distribution $ ({\mathsf{comp}}, {\mathsf{iar}}) $ over several Catalan and Schröder classes, preserving the values of the left-to-right maxima.
● A complete classification of $ {\mathsf{comp}} $- and $ {\mathsf{iar}} $-Wilf-equivalences for length $ 3 $ patterns and pairs of length $ 3 $ patterns. Calculations of the $ ({\mathsf{des}}, {\mathsf{iar}}, {\mathsf{comp}}) $ generating functions over these pattern avoiding classes and separable permutations.
● A further refinement of Wang's descent-double descent-Wilf equivalence between separable permutations and $ (2413, 4213) $-avoiding permutations by the Comtet statistic $ {\mathsf{iar}} $.
| [1] |
Block decomposition of permutations and Schur-positivity. J. Algebraic Combin. (2018) 47: 603-622. 
|
| [2] | C. A. Athanasiadis, Gamma-positivity in combinatorics and geometry, Sém. Lothar. Combin., 77 (2018), Article B77i, 64 pp (electronic). |
| [3] | M. Barnabei, F. Bonetti and M. Silimbani, The descent statistic on $123$-avoiding permutations, Sém. Lothar. Combin., 63 (2010), B63a, 8 pp. |
| [4] |
Kazhdan-Lusztig polynomials for $321$-Hexagon-avoiding permutations. J. Algebraic Combin. (2001) 13: 111-136.
|
| [5] |
M. Bóna, Combinatorics of Permutations. With a Foreword by Richard Stanley, Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2004. doi: 10.1201/9780203494370
|
| [6] |
The number of Baxter permutations. J. Combin. Theory Ser. A (1978) 24: 382-394.
|
| [7] | A. Claesson and S. Kitaev, Classification of bijections between $321$-and $132$-avoiding permutations, Sém. Lothar. Combin., 60 (2008), B60d, 30 pp. |
| [8] |
Decompositions and statistics for $\beta(1,0)$-trees and nonseparable permutations. Adv. in Appl. Math. (2009) 42: 313-328.
|
| [9] | L. Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, Revised and enlarged edition, D. Reidel Publishing Co., Dordrecht, 1974. |
| [10] | S. Corteel, M. A. Martinez, C. D. Savage and M. Weselcouch, Patterns in inversion sequences I, Discrete Math. Theor. Comput. Sci., 18 (2016), Paper No. 2, 21 pp. |
| [11] |
Permutation patterns and statistics. Discrete Math. (2012) 312: 2760-2775.
|
| [12] | P. G. Doyle, Stackable and queueable permutations, preprint, arXiv: 1201.6580. |
| [13] |
Bijections for refined restricted permutations. J. Combin. Theory Ser. A (2004) 105: 207-219.
|
| [14] | D. Foata and M.-P. Schützenberger, Théorie Géométrique des Polynômes Eulériens, Lecture Notes in Mathematics, Vol. 138, Springer-Verlag, Berlin-New York, 1970. |
| [15] |
$k$-arrangements, statistics, and patterns. SIAM J. Discrete Math. (2020) 34: 1830-1853.
|
| [16] | S. Fu, Z. Lin and Y. Wang, A combinatorial bijection on di-sk trees, preprint, arXiv: 2011.11302. |
| [17] |
On two new unimodal descent polynomials. Discrete Math. (2018) 341: 2616-2626.
|
| [18] |
S. Fu and Y. Wang, Bijective proofs of recurrences involving two Schröder triangles, European J. Combin., 86 (2020), 103077, 18 pp. doi: 10.1016/j.ejc.2019.103077
|
| [19] | A. L. L. Gao, S. Kitaev and P. B. Zhang, On pattern avoiding indecomposable permutations, Integers, 18 (2018), A2, 23 pp. |
| [20] |
S. Kitaev, Patterns in Permutations and Words. With a Forewrod by Jeffrey B. Remmel, Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg, 2011. doi: 10.1007/978-3-642-17333-2
|
| [21] | D. E. Knuth, The Art of Computer Programming. Vol. 1. Fundamental Algorithms, 3$^{rd}$ edition, Addison-Wesley, Reading, MA, 1997. |
| [22] |
Permutations with restricted patterns and Dyck paths. Special Issue in Honor of Dominique Foata's 65th birthday, Adv. in Appl. Math. (2001) 27: 510-530.
|
| [23] |
On $\gamma$-positive polynomials arising in pattern avoidance. Adv. in Appl. Math. (2017) 82: 1-22.
|
| [24] |
A sextuple equidistribution arising in pattern avoidance. J. Combin. Theory Ser. A (2018) 155: 267-286.
|
| [25] | OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, http://oeis.org, 2020. |
| [26] |
T. K. Petersen, Eulerian numbers. With a Foreword by Richard Stanley, Birkhäuser Advanced Texts: Basler Lehrbücher, Birkhäuser/Springer, New York, 2015. doi: 10.1007/978-1-4939-3091-3
|
| [27] | M. Rubey, An involution on Dyck paths that preserves the rise composition and interchanges the number of returns and the position of the first double fall, Sém. Lothar. Combin., 77 (2016-2018), Art. B77f, 4 pp. |
| [28] |
Restricted permutations. European J. Combin. (1985) 6: 383-406.
|
| [29] |
Forbidden subsequences. Discrete Math. (1994) 132: 291-316.
|
| [30] |
The Eulerian distribution on involutions is indeed $\gamma$-positive. J. Combin. Theory Ser. A (2019) 165: 139-151.
|
| [31] |
Generating trees and the Catalan and Schröder numbers. Discrete Math. (1995) 146: 247-262.
|
Figures(2) / Tables(2)
Shishuo Fu, Zhicong Lin, Yaling Wang. Refined Wilf-equivalences by Comtet statistics[J]. Electronic Research Archive, 2021, 29(5): 2877-2913. doi: 10.3934/era.2021018
DownLoad: