×

Equidistribution of set-valued statistics on standard Young tableaux and transversals. (English) Zbl 1532.05176

Summary: As a natural generalization of permutations, transversals of Young diagrams play an important role in the study of pattern avoiding permutations. Let \(\mathcal{T}_{\lambda}(\tau)\) and \(\mathcal{ST}_{\lambda}(\tau)\) denote the set of \(\tau\)-avoiding transversals and \(\tau\)-avoiding symmetric transversals of a Young diagram \(\lambda\), respectively. In this paper, we are mainly concerned with the distribution of the peak set and the valley set on standard Young tableaux and pattern avoiding transversals. In particular, we prove that the peak set and the valley set are equidistributed on the standard Young tableaux of shape \(\lambda /\mu\) for any skew diagram \(\lambda /\mu\). The equidistribution enables us to show that the peak set is equidistributed over \(\mathcal{T}_{\lambda}(12 \cdots k\tau)\) (resp. \(\mathcal{ST}_{\lambda}(12 \cdots k\tau))\) and \(\mathcal{T}_{\lambda}(k\cdots 21\tau)\) (resp. \(\mathcal{ST}_{\lambda}(k\cdots 21\tau))\) for any Young diagram \(\lambda\) and any permutation \(\tau\) of \(\{k+1, k+2, \ldots, k+m\}\) with \(k, m\geq 1\). Our results are refinements of the result of J. Backelin et al. [Adv. Appl. Math. 38, No. 2, 133–148 (2007; Zbl 1127.05002)] which states that \(|\mathcal{T}_{\lambda}(12\cdots k\tau) |=|\mathcal{T}_{\lambda}(k\cdots 21\tau)|\) and the result of M. Bousquet-Mélou and E. Steingrímsson [J. Algebr. Comb. 22, No. 4, 383–409 (2005; Zbl 1085.05002)] which states that \(|\mathcal{ST}_{\lambda}(12\cdots k \tau) |=| \mathcal{ST}_{\lambda}(k\cdots 21 \tau)|\). As applications, we are able to
confirm a recent conjecture posed by S. H. F. Yan et al. [ibid. 58, No. 1, 69–94 (2023; Zbl 1518.05003)] which asserts that the peak set is equidistributed over \(12 \cdots k\tau\)-avoiding involutions and \(k \cdots 21\tau\)-avoiding involutions;
prove that alternating involutions avoiding the pattern \(12 \cdots k\tau\) are equinumerous with alternating involutions avoiding the pattern \(k \cdots 21\tau\), paralleling the result of J. Backelin et al. [loc. cit.] for permutations, the result of Bousquet-Mélou and Steingrímsson [loc. cit.] for involutions, and the result of S. H. F. Yan [Electron. J. Comb. 20, No. 3, Research Paper P58, 19 p. (2013; Zbl 1298.05013)] for alternating permutations.

MSC:

05E10 Combinatorial aspects of representation theory
05A05 Permutations, words, matrices
05C30 Enumeration in graph theory

Software:

bs3np

References:

[1] Aguiar, M.; Nyman, K.; Orellana, R., New results on the peak algebra, J. Algebraic Comb., 23, 149-188 (2006) · Zbl 1107.20009
[2] Babson, E.; West, J., The permutations \(123 p_4 \ldots p_m\) and \(321 p_4 \ldots p_m\) are Wilf-equivalent, Graphs Comb., 16, 373-380 (2000) · Zbl 0988.05008
[3] Backelin, J.; West, J.; Xin, G., Wilf-equivalence for singleton classes, Adv. Appl. Math., 38, 133-148 (2007) · Zbl 1127.05002
[4] Barnabei, M.; Bonetti, F.; Silimbani, M., Restricted involutions and Motzkin paths, Adv. Appl. Math., 47, 102-115 (2011) · Zbl 1225.05242
[5] Barnabei, M.; Bonetti, F.; Castronuovo, N.; Silimbani, M., Pattern avoiding alternating involutions, Enumer. Comb. App., 3, 1, Article #S2R4 pp. (2023) · Zbl 1512.05008
[6] Billera, L. J.; Hsiao, S. K.; van Willigenburg, S., Peak quasisymmetric functions and Eulerian enumeration, Adv. Math., 176, 248-276 (2003) · Zbl 1027.05105
[7] Bloom, J.; Saracino, D., On bijections for pattern-avoiding permutations, J. Comb. Theory, Ser. A, 116, 1271-1284 (2009) · Zbl 1181.05002
[8] Bloom, J.; Saracino, D., Another look at bijections for pattern-avoiding permutations, Adv. Appl. Math., 45, 2010, 395-409 (2010) · Zbl 1194.05001
[9] Bloom, J., A refinement of Wilf-equivalence for patterns of length 4, J. Comb. Theory, Ser. A, 124, 166-177 (2014) · Zbl 1283.05012
[10] Bóna, M., On a family of conjectures of Joel Lewis on alternating permutations, Graphs Comb., 30, 521-526 (2014) · Zbl 1296.05002
[11] Bóna, M.; Homberger, C.; Pantone, J.; Vatter, V., Pattern-avoiding involutions: exact and asymptotic enumeration, Australas. J. Comb., 64, 88-119 (2016) · Zbl 1333.05018
[12] Bousquet-Mélou, M.; Steingrímsson, E., Decreasing subsequences in permutations and Wilf equivalence for involutions, J. Algebraic Comb., 22, 383-409 (2005) · Zbl 1085.05002
[13] Chan, J. H.C., An infinite family of inv-Wilf-equivalent permutation pairs, Eur. J. Comb., 44, 57-76 (2015) · Zbl 1302.05001
[14] Chen, W. Y.C.; Deng, E. Y.P.; Du, R. R.X.; Stanley, R. P.; Yan, C. H., Crossings and nestings of matchings and partitions, Trans. Am. Math. Soc., 359, 1555-1575 (2007) · Zbl 1108.05012
[15] Chen, J. N.; Chen, W. Y.C.; Zhou, R. D.P., On pattern avoiding alternating permutations, Eur. J. Comb., 40, 11-25 (2014) · Zbl 1297.05010
[16] Dokos, T.; Dwyer, T.; Johnson, B. P.; Sagan, B. E.; Selsor, K., Permutation patterns and statistics, Discrete Math., 312, 2760-2775 (2012) · Zbl 1248.05004
[17] Dukes, W. M.B.; Jelínek, V.; Mansour, T.; Reifegerste, A., New equivalences for pattern avoiding involutions, Proc. Am. Math. Soc., 137, 457-465 (2009) · Zbl 1169.05002
[18] Guibert, O., Combinatoire des permutations à motifs exclus, en liaison avec mots, cartes planaires et tableaux de Young (1995), LaBRI, Université Bordeaux 1, PhD thesis
[19] Jaggard, A. D., Prefix exchanging and pattern avoidance by involutions, Electron. J. Comb., 9, 2, R16 (2003) · Zbl 1045.05002
[20] Knuth, D. E., The art of computer programming, sorting and searching, vol. 3 (1973), Addison-Wesley · Zbl 0302.68010
[21] Lewis, J. B., Alternating, pattern-avoiding permutations, Electron. J. Comb., 16, N7 (2009) · Zbl 1158.05302
[22] Lewis, J. B., Pattern avoidance for alternating permutations and Young tableaux, J. Comb. Theory, Ser. A, 118, 1436-1450 (2011) · Zbl 1231.05286
[23] Lewis, J. B., Generating trees and pattern avoidance in alternating permutations, Electron. J. Comb., 19, P21 (2012) · Zbl 1243.05011
[24] Mansour, T., Restricted 132-alternating permutations and Chebyshev polynomials, Ann. Comb., 7, 201-227 (2003) · Zbl 1020.05002
[25] Petersen, T. K., Enriched P-partitions and peak algebras, Adv. Math., 209, 61-610 (2007) · Zbl 1111.05097
[26] Schocker, M., The peak algebra of the symmetric group revisited, Adv. Math., 192, 259-309 (2005) · Zbl 1132.20009
[27] Simion, R.; Schmidt, F., Restricted permutations, Eur. J. Comb., 6, 383-406 (1985) · Zbl 0615.05002
[28] Stanley, R. P., Alternating permutations and symmetric functions, J. Comb. Theory, Ser. A, 114, 436-460 (2007) · Zbl 1118.05002
[29] Stanley, R. P., Enumerative combinatorics, vol. 2 (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0928.05001
[30] Stembridge, J. R., Enriched P-partitions, Trans. Am. Math. Soc., 349, 763-788 (1997) · Zbl 0863.06005
[31] Strehl, V., Enumeration of alternating permutations according to peak sets, J. Comb. Theory, Ser. A, 24, 238-240 (1978) · Zbl 0373.05005
[32] Sundaram, S., The Cauchy identity for \(S p(2 n)\), J. Comb. Theory, Ser. A, 53, 209-238 (1990) · Zbl 0707.05005
[33] Warren, D.; Seneta, E., Peaks and Eulerian numbers in a random sequence, J. Appl. Probab., 33, 101-114 (1996) · Zbl 0845.60035
[34] Xin, G.; Zhang, T. Y.J., Enumeration of bilaterally symmetric 3-noncrossing partitions, Discrete Math., 309, 2497-2509 (2009) · Zbl 1206.05022
[35] Xu, Y.; Yan, S. H.F., Alternating permutations with restrictions and standard Young tableaux, Electron. J. Comb., 19, 2, P49 (2012) · Zbl 1253.05143
[36] Yan, S. H.F., On Wilf equivalence for alternating permutations, Electron. J. Comb., 20, 3, P58 (2013) · Zbl 1298.05013
[37] Yan, S. H.F.; Ge, H.; Zhang, Y., On a refinement of Wilf-equivalence for permutations, Electron. J. Comb., 22, 1, Article P1.20 pp. (2015) · Zbl 1307.05004
[38] Yan, S. H.F.; Wang, L.; Zhou, R. D.P., On refinements of Wilf-equivalence for involutions, J. Algebraic Comb., 58, 69-94 (2023) · Zbl 1518.05003
[39] Zhou, R. D.P.; Yan, S. H.F., Combinatorics of exterior peaks on pattern avoiding symmetric transversals, Ann. Comb.
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.