Refined Wilf-equivalences by Comtet statistics

Shishuo Fu; Zhicong Lin; Yaling Wang; Shishuo Fu; Zhicong Lin; Yaling Wang

doi:10.3934/era.2021018

Electronic Research Archive

2021, Volume 29, Issue 5: 2877-2913. doi: 10.3934/era.2021018

Previous Article Next Article

Special Issues

Refined Wilf-equivalences by Comtet statistics

Shishuo Fu ^{1
,
,},
Zhicong Lin ^{2
,},
Yaling Wang ^{1
,}

1.
College of Mathematics and Statistics, Chongqing University, Huxi campus, Chongqing 401331, China
2.
Research Center for Mathematics and Interdisciplinary Sciences, Shandong University, Qingdao 266237, China

Received: 01 May 2020 Revised: 01 November 2020 Published: 15 March 2021
Primary: 05A05, 05A15, 05A19; Secondary: 05C05

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}} $.
- Catalan number,
- Schröder number,
- Wilf equivalence,
- pattern avoidance,
- separable permutation,
- bijective proof
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

Related Papers:

Abstract

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}} $.

References

[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.

Reader Comments

Your name:*

Email:*
© 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)