Special Issues

Refined Wilf-equivalences by Comtet statistics

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

    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:

  • 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.
  • Reader Comments
  • © 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)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(887) PDF downloads(225) Cited by(0)

Article outline

Figures and Tables

Figures(2)  /  Tables(2)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog