Rational Parking Functions and Catalan Numbers

详细信息    查看全文

• 作者：Drew Armstrong ; Nicholas A. Loehr ; Gregory S. Warrington
• 关键词：rational parking functions ; q ; t ; Catalan numbers ; rational Catalan numbers ; diagonal harmonics ; Shuffle Conjecture
• 刊名：Annals of Combinatorics
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：20
• 期：1
• 页码：21-58
• 全文大小：1,468 KB
• 参考文献：1.Anderson J.: Partitions which are simultaneously t 1- and t 2-core. Discrete Math. 248, 237–243 (2002)CrossRef MathSciNet MATH
  2.Armstrong D.: Hyperplane arrangements and diagonal harmonics. J. Combin. 4(2), 157–190 (2013)CrossRef MathSciNet MATH
  3.Armstrong D., Hanusa C.R.H., Jones B.C.: Results and conjectures on simultaneous core partitions. European J. Combin. 41, 205–220 (2014)CrossRef MathSciNet MATH
  4.Armstrong, D., Rhoades, B., Williams, N.: Rational associahedra and noncrossing partitions. Electron. J. Combin. 20, #P54 (2013)
  5.Armstrong D., Loehr N.A., Warrington G.S.: Sweep maps: a continuous family of sorting algorithms. Adv. Math. 284, 159–185 (2015)CrossRef MathSciNet
  6.Assaf, S.: Dual equivalence graphs and a combinatorial proof of LLT and Macdonald positivity. arXiv:​1005.​3759 (2010)
  7.Bizley M.T.L.: Derivation of a new formula for the number of minimal lattice paths from (0, 0) to (km, kn) having just t contacts with the line my =  nx 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)MathSciNet
  8.Borel A.: Sur la cohomologie des espaces fibrés principaux et des espaces homogènes de groupes de Lie compacts. Ann. of Math. 2(57), 115–207 (1953)CrossRef MathSciNet
  9.Cayley A.: A theorem on trees. Quart. J. Math. 23, 376–378 (1889)
  10.Chevalley C.: Invariants of finite groups generated by reflections. Amer. J. Math. 77, 778–782 (1955)CrossRef MathSciNet MATH
  11.Dvoretsky A., Motzkin T.: A problem of arrangements. Duke Math. J. 14, 305–313 (1947)CrossRef MathSciNet
  12.Egge E., Loehr N., Warrington G.S.: From quasisymmetric expansions to Schur expansions via a modified inverse Kostka matrix. European J. Combin. 31(8), 2014–2027 (2010)CrossRef MathSciNet MATH
  13.Haglund J., Garsia A.: A proof of the q, t-Catalan positivity conjecture. Discrete Math. 256, 677–717 (2002)CrossRef MathSciNet MATH
  14.Garsia A., Haiman M.: A remarkable q, t-Catalan sequence and q-Lagrange inversion. J. Algebraic Combin. 5, 191–244 (1996)CrossRef MathSciNet MATH
  15.Gorsky E., Mazin M.: Compactified Jacobians and q, t-Catalan numbers I. J. Combin. Theory Ser. A 120, 49–63 (2013)CrossRef MathSciNet MATH
  16.Gorsky E., Mazin M.: Compactified Jacobians and q, t-Catalan numbers II. J. Algebraic Combin. 39, 153–186 (2014)CrossRef MathSciNet MATH
  17.Gorsky, E., Mazin, M., Vazirani, M.: Affine permutations and rational slope parking functions. Trans. Amer. Math. Soc. (to appear)
  18.Gorsky E., Negut A.: Refined knot invariants and Hilbert schemes. J. Math. Pures Appl. (9) 104(3), 403–435 (2015)CrossRef MathSciNet
  19.Haglund J.: The q, t-Catalan Numbers and the Space of Diagonal Harmonics. American Mathematical Society, Providence, RI (2008)MATH
  20.Haglund J.: Conjectured statistics for the q, t-Catalan numbers. Adv. Math. 175, 319–334 (2003)CrossRef MathSciNet MATH
  21.Haglund J., Haiman M., Loehr N., Remmel J., Ulyanov A.: A combinatorial formula for the character of the diagonal coinvariants. Duke Math. J. 126, 195–232 (2005)CrossRef MathSciNet MATH
  22.Haglund J., Loehr N.A.: A conjectured combinatorial formula for the Hilbert series for diagonal harmonics. Discrete Math. 298, 189–204 (2005)CrossRef MathSciNet MATH
  23.Haiman M.: Conjectures on the quotient ring by diagonal invariants. J. Algebraic Combin. 3, 17–76 (1994)CrossRef MathSciNet MATH
  24.Haiman M.: Vanishing theorems and character formulas for the Hilbert scheme of points in the plane. Invent. Math. 149, 371–407 (2002)CrossRef MathSciNet MATH
  25.Hikita T.: Affine Springer fibers of type A and combinatorics of diagonal coinvariants. Adv. Math. 263, 88–122 (2014)CrossRef MathSciNet MATH
  26.Konheim A.G., Weiss B.: An occupancy discipline and applications. SIAM J. Appl. Math. 14, 17–76 (1966)CrossRef
  27.Kreweras G.: Sur les partitions non croisées d’un cycle. Discrete Math. 1, 333–350 (1972)CrossRef MathSciNet MATH
  28.Lascoux A., Leclerc B., Thibon J.-Y.: Ribbon tableaux, Hall-Littlewood functions, quantum affine algebras, and unipotent varieties. J. Math. Phys. 38(2), 1041–1068 (1997)CrossRef MathSciNet MATH
  29.Leclerc B., Thibon J.-Y.: Littlewood-Richardson coefficients and Kazhdan-Lusztig polynomials. In: Koike, K., Kashiwara, M., Okada, S., Terada, I., Yamada H.-F., (eds.) Combinatorial Methods in Representation Theory, pp. 155–220. Kinokuniya, Tokyo (2000)
  30.Loehr N.A.: Bijective Combinatorics. Chapman and Hall/CRC Press, Boca Raton (2011)MATH
  31.Loehr, N.A.: Conjectured statistics for the higher q, t-Catalan sequences. Electron. J. Combin. 12, #R9 (2005)
  32.Loehr N.A., Warrington G.S.: A continuous family of partition statistics equidistributed with length. J. Combin. Theory Ser. A 116, 379–403 (2009)CrossRef MathSciNet MATH
  33.Macdonald, I.: Symmetric Functions and Hall Polynomials. Second edition. Oxford University Press, New York (1995)
  34.MacMahon, P.: Combinatory Analysis. Cambridge University Press, Cambridge (1918) Reprinted by Chelsea, New York, 3rd edition (1984)
  35.Mazin M.: A bijective proof of Loehr-Warrington’s formulas for the statistics \({ctot_{\frac{q}{p}}}\) and \({mid_{\frac{q}{p}}}\) . Ann. Combin. 18(4), 709–722 (2014)CrossRef MathSciNet MATH
  36.Oblomkov, A., Yun, Z.: Geometric representations of graded and rational Cherednik algebras. arXiv:​1407.​5685 (2014)
  37.Pak I., Postnikov A.: Enumeration of trees and one amazing representation of S n . In: Stanton, D. (ed) Eighth International Conference on Formal Power Series and Algebraic Combinatorics, pp. 385–389. University of Minnesota, Minneapolis (1996)
  38.Raney G.N.: Functional composition patterns and power series reversion. Trans. Amer. Math. Soc. 94, 441–451 (1960)CrossRef MathSciNet MATH
  39.Riordan J.: Ballots and trees. J. Combin. Theory 6, 408–411 (1969)CrossRef MathSciNet MATH
  40.Sagan B.: The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions. Springer, New York (2001)CrossRef
  41.Stanley R.P.: Enumerative Combinatorics. Volume 2. Cambridge University press, Cambridge (1999)CrossRef MATH
  42.Stanley, R.P.: Parking functions and noncrossing partitions. Electron. J. Combin. 4(2), #R20 (1997)
  43.Stein, W.A. et al.: SAGE Mathematics Software (Version 5.5). The SAGE Development Team (2012) http://​www.​sagemath.​org .
  44.Tignol J.-P.: Galois’ Theory of Algebraic Equations. World Scientific Publishing, Singapore (2001)CrossRef MATH
  45.Warrington, G.S.: SAGE worksheet for rational Catalan and rational parking function conjectures. available online (2014) http://​www.​cems.​uvm.​edu/​~gswarrin/​research/​RPF.​sws .
  46.Weyl H.: The Classical Groups, Their Invariants and Representations. 2nd. ed., Princeton Univ. Press, Princeton, N.J. (1946)MATH
  
• 作者单位：Drew Armstrong (1)
  Nicholas A. Loehr (2) (3)
  Gregory S. Warrington (4)
  
  1. Department of Mathematics, University of Miami, Coral Gables, FL, 33146, USA
  2. Department of Mathematics, Virginia Tech, Blacksburg, VA, 24061-0123, USA
  3. Mathematics Department, United States Naval Academy, Annapolis, MD, 21402-5002, USA
  4. Department of Mathematics and Statistics, University of Vermont, Burlington, VT, 05401, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  
• 出版者：Birkh盲user Basel
• ISSN：0219-3094

文摘

The “classical” parking functions, counted by the Cayley number (n+1) n−1, carry a natural permutation representation of the symmetric group S _n in which the number of orbits is the Catalan number \({\frac{1}{n+1} \left( \begin{array}{ll} 2n \\ n \end{array} \right)}\). In this paper, we will generalize this setup to “rational” parking functions indexed by a pair (a, b) of coprime positive integers. These parking functions, which are counted by b a−1, carry a permutation representation of S _a in which the number of orbits is the “rational” Catalan number \({\frac{1}{a+b} \left( \begin{array}{ll} a+b \\ a \end{array} \right)}\). First, we compute the Frobenius characteristic of the S _a -module of (a, b)-parking functions, giving explicit expansions of this symmetric function in the complete homogeneous basis, the power-sum basis, and the Schur basis. Second, we study q-analogues of the rational Catalan numbers, conjecturing new combinatorial formulas for the rational q-Catalan numbers \({\frac{1}{[a+b]_{q}} {{\left[ \begin{array}{ll} a+b \\ a \end{array} \right]}_{q}}}\) and for the q-binomial coefficients \({{{\left[ \begin{array}{ll} n \\ k \end{array} \right]}_{q}}}\). We give a bijective explanation of the division by [a+b] _q that proves the equivalence of these two conjectures. Third, we present combinatorial definitions for q, t-analogues of rational Catalan numbers and parking functions, generalizing the Shuffle Conjecture for the classical case. We present several conjectures regarding the joint symmetry and t = 1/q specializations of these polynomials. An appendix computes these polynomials explicitly for small values of a and b.