×

Symmetries of statistics on lattice paths between two boundaries. (English) Zbl 1327.05338

Summary: We prove that on the set of lattice paths with steps \(N = (0, 1)\) and \(E = (1, 0)\) that lie between two fixed boundaries \(T\) and \(B\) (which are themselves lattice paths), the statistics ‘number of \(E\) steps shared with \(B\)’ and ‘number of \(E\) steps shared with \(T\)’ have a symmetric joint distribution. To do so, we give an involution that switches these statistics, preserves additional parameters, and generalizes to paths that contain steps \(S = (0, - 1)\) at prescribed \(x\)-coordinates. We also show that a similar equidistribution result for path statistics follows from the fact that the Tutte polynomial of a matroid is independent of the order of its ground set. We extend the two theorems to \(k\)-tuples of paths between two boundaries, and we give some applications to Dyck paths, generalizing a result of E. Deutsch [Discrete Math. 179, No. 1–3, 253–256 (1998); corrigendum ibid. 187, No. 1–3, 297 (1998; Zbl 0890.05005)], to watermelon configurations, to pattern-avoiding permutations, and to the generalized Tamari lattice. Finally, we prove a conjecture of C. M. Nicolás [“Another bijection between 2-triangulations and pairs of non-crossing Dyck paths”, Discrete Math. Theor. Comput. Sci. Proc., AK, 697–708, (2009)] about the distribution of degrees of \(k\) consecutive vertices in \(k\)-triangulations of a convex \(n\)-gon. To achieve this goal, we provide a new statistic-preserving bijection between certain \(k\)-tuples of non-crossing paths and \(k\)-flagged semistandard Young tableaux, which is based on local moves reminiscent of jeu de taquin.

MSC:

05E10 Combinatorial aspects of representation theory
05C31 Graph polynomials
05A19 Combinatorial identities, bijective combinatorics
52C05 Lattices and convex bodies in \(2\) dimensions (aspects of discrete geometry)
05A15 Exact enumeration problems, generating functions
05B35 Combinatorial aspects of matroids and geometric lattices
05E05 Symmetric functions and generalizations

Citations:

Zbl 0890.05005
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Andrews, G. E.; Krattenthaler, C.; Orsina, L.; Papi, P., ad-Nilpotent \(b\)-ideals in \(sl(n)\) having a fixed class of nilpotence: combinatorics and enumeration, Trans. Amer. Math. Soc., 354, 10, 3835-3853 (2002) · Zbl 1041.17008
[2] Ardila, F., The Catalan matroid, J. Combin. Theory Ser. A, 104, 1, 49-62 (2003) · Zbl 1031.05030
[3] Banderier, C.; Flajolet, P., Basic analytic combinatorics of directed lattice paths, Theoret. Comput. Sci., 281, 1-2, 37-80 (2002), Selected papers in honour of Maurice Nivat · Zbl 0996.68126
[4] Benkart, G.; Sottile, F.; Stroomer, J., Tableau switching: algorithms and applications, J. Combin. Theory Ser. A, 76, 1, 11-43 (1996) · Zbl 0858.05099
[5] Bergeron, F.; Préville-Ratelle, L.-F., Higher trivariate diagonal harmonics via generalized Tamari posets, preprint available at · Zbl 1291.05213
[6] Bizley, M. T.L., Derivation of a new formula for the number of minimal lattice paths from \((0, 0)\) to \((k m, k n)\) having just \(t\) contacts with the line \(m y = n x\) and having no points above this line; and a proof of Grossman’s formula for the number of paths which may touch but do not rise above this line, J. Inst. Actuar., 80, 55-62 (1954) · Zbl 0055.00702
[7] Bonin, J.; de Mier, A.; Noy, M., Lattice path matroids: enumerative aspects and Tutte polynomials, J. Combin. Theory Ser. A, 104, 1, 63-94 (2003) · Zbl 1031.05031
[8] Brak, R.; Essam, J. W., Return polynomials for non-intersecting paths above a surface on the directed square lattice, J. Phys. A, 34, 49, 10763-10782 (2001) · Zbl 0996.82033
[9] Bousquet-Mélou, M.; Fusy, É.; Préville-Ratelle, L.-F., The number of intervals in the \(m\)-Tamari lattices, Electron. J. Combin., 18, 2 (2011), Paper 31, 26 pp · Zbl 1262.05005
[10] Chapman, R. J.; Chow, T. Y.; Khetan, A.; Moulton, D. P.; Waters, R. J., Simple formulas for lattice paths avoiding certain periodic staircase boundaries, J. Combin. Theory Ser. A, 116, 1, 205-214 (2009) · Zbl 1156.05005
[11] Crapo, H. H., The Tutte polynomial, Aequationes Math., 3, 211-229 (1969) · Zbl 0197.50202
[12] Deutsch, E., A bijection on Dyck paths and its consequences, Discrete Math., 179, 1-3, 253-256 (1998) · Zbl 0890.05005
[13] Deutsch, E., An involution on Dyck paths and its consequences, Discrete Math., 204, 1-3, 163-166 (1999) · Zbl 0932.05005
[14] Dress, A.; Koolen, J. H.; Moulton, V., On line arrangements in the hyperbolic plane, European J. Combin., 23, 5, 549-557 (2002) · Zbl 1023.52007
[15] Duchon, P., On the enumeration and generation of generalized Dyck words, Formal Power Series and Algebraic Combinatorics. Formal Power Series and Algebraic Combinatorics, Toronto, ON, 1998. Formal Power Series and Algebraic Combinatorics. Formal Power Series and Algebraic Combinatorics, Toronto, ON, 1998, Discrete Math., 225, 1-3, 121-135 (2000) · Zbl 0971.68090
[16] Elizalde, S., A bijection between 2-triangulations and pairs of non-crossing Dyck paths, J. Combin. Theory Ser. A, 114, 8, 1481-1503 (2007) · Zbl 1125.05006
[17] Elizalde, S.; Rubey, M., Symmetries of statistics on lattice paths between two boundaries, preprint · Zbl 1327.05338
[18] Gessel, I. M., A factorization for formal Laurent series and lattice path enumeration, J. Combin. Theory Ser. A, 28, 3, 321-337 (1980)
[19] Gessel, I. M.; Ree, S., Lattice paths and Faber polynomials, (Advances in Combinatorial Methods and Applications to Probability and Statistics. Advances in Combinatorial Methods and Applications to Probability and Statistics, Stat. Ind. Technol. (1997), Birkhäuser Boston: Birkhäuser Boston Boston, MA), 3-13 · Zbl 0882.05005
[20] Gessel, I. M.; Viennot, X. G., Binomial determinants, paths, and hook length formulae, Adv. Math., 58, 3, 300-321 (1985) · Zbl 0579.05004
[21] Gessel, I. M.; Viennot, X. G., Determinants, paths, and plane partitions (1989), available at
[22] Greene, C.; Kleitman, D. J., Strong versions of Sperner’s theorem, J. Combin. Theory Ser. A, 20, 1, 80-88 (1976) · Zbl 0361.05015
[23] Haglund, J., The \(q,t\)-Catalan Numbers and the Space of Diagonal Harmonics, University Lecture Series, vol. 41 (2008), American Mathematical Society: American Mathematical Society Providence, RI, With an appendix on the combinatorics of Macdonald polynomials · Zbl 1142.05074
[25] Irving, J.; Rattan, A., The number of lattice paths below a cyclically shifting boundary, J. Combin. Theory Ser. A, 116, 3, 499-514 (2009) · Zbl 1202.05006
[26] Jonsson, J., Generalized triangulations and diagonal-free subsets of stack polyominoes, J. Combin. Theory Ser. A, 112, 1, 117-142 (2005) · Zbl 1084.05017
[27] Korolyuk, Vladimir. S., On the discrepancy of empiric distributions for the case of two independent samples, Izv. Ross. Akad. Nauk Ser. Mat., 19, 81-96 (1955) · Zbl 0067.10501
[28] Krattenthaler, C., Watermelon configurations with wall interaction: exact and asymptotic results, J. Phys. Conf. Ser., 42, 1, 179 (2006)
[29] Loehr, N. A., Conjectured statistics for the higher \(q, t\)-Catalan sequences, Electron. J. Combin., 12, Article R9 pp. (2005), 54 pp · Zbl 1083.05006
[30] Nakamigawa, T., A generalization of diagonal flips in a convex polygon, Combinatorics and Optimization. Combinatorics and Optimization, Okinawa, 1996. Combinatorics and Optimization. Combinatorics and Optimization, Okinawa, 1996, Theoret. Comput. Sci., 235, 2, 271-282 (2000) · Zbl 0938.68880
[31] Nicolás, C. M., Another bijection between 2-triangulations and pairs of non-crossing Dyck paths, (21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009). 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), Discrete Math. Theor. Comput. Sci. Proc., AK (2009), Assoc. Discrete Math. Theor. Comput. Sci.: Assoc. Discrete Math. Theor. Comput. Sci. Nancy), 697-708 · Zbl 1391.05031
[32] Renault, M., Lost (and found) in translation: André’s actual method and its application to the generalized ballot problem, Amer. Math. Monthly, 115, 4, 358-363 (2008) · Zbl 1142.60004
[33] Serrano, L.; Stump, C., Maximal fillings of moon polyominoes, simplicial complexes, and Schubert polynomials, Electron. J. Combin., 19, 1 (2012), Paper 16, 18 pp · Zbl 1244.05239
[34] Stanley, R. P., Enumerative Combinatorics, vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62 (1999), Cambridge University Press: Cambridge University Press Cambridge, With a foreword by Gian-Carlo Rota and Appendix 1 by Sergey Fomin · Zbl 0928.05001
[35] Tutte, W. T., A contribution to the theory of chromatic polynomials, Canad. J. Math., 6, 80-91 (1954) · Zbl 0055.17101
[36] Wachs, M. L., Flagged Schur functions, Schubert polynomials, and symmetrizing operators, J. Combin. Theory Ser. A, 40, 2, 276-289 (1985) · Zbl 0579.05001
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.