Improve this page

#A weighted Dyck path enumeration

In the expansion of chromatic quasisymmetric functions in the Gessel quasisymmetric fundamental basis, the following expression shows up, where \(\avec\) is the area sequence of a unit interval graph. The number of area sequences of length \(n\) is given by the \(n\)th Catalan number, and there is a natural correspondence between area sequences and Dyck paths in \(\DP(n).\)

Let \(\avec\) be an area sequence of length \(n\) and let \(X_{\avec}(q) \coloneqq \prod_{i=1}^n [a_i+1]_q,\) where we use the \(q\)-analogue \([n]_q = 1+q+q^2+\dotsb+q^{n-1}.\) Notice that \(X_{\avec}(q)\) defines a weight on the corresponding Dyck path. This weight is quite remarkable.

By using [Thm. 1, Fla06], we immediately get the following continued fraction: \[\sum_{n\geq 0} z^n \sum_{\avec \in \DP(n) } X_{\avec}(q) = \cfrac{1}{ 1 - \cfrac{z[1]_q}{ 1 - \cfrac{z[2]_q}{ 1 - \cfrac{z[3]_q}{ \cdots }}}}\]

#Perfect matchings

Let \(\setPM(n)\) be the set of perfect matchings on \([2n],\) placed in a circle. Let \(cr(M)\) denote the number of crossings. Let the Touchard–Riordan polynomials, see A067311, be defined as \[T_n(q) = \sum_{M \in \setPM(n)} q^{cr(M)}.\] Then \[T_n(q) = \sum_{\avec \in \catalan_n} X_{\avec}(q).\] This follows from [Rea79] who shows that \(\sum_{n \geq 0} z^n T_n(q)\) is given by the continued fraction expression above.

Another formula is \[(q-1)^m T_m(q) = \sum_{j=0}^{2m} (-1)^j \binom{2m}{j} q^{\binom{m-j+1}{2}},\] see [PR22] for a connection with certain sets of subspaces of \(F_q^{2m}.\)

Example (Table of \(T_n(q)\)).

Here is a table of the first few Touchard–Riordan polynomials. See A067311 for more information.

\( n \) \( T_n(q) \) \( 1 \) \( 1 \) \( 2 \) \( q+2 \) \( 3 \) \( q^3+3 q^2+6 q+5 \) \( 4 \) \( q^6+4 q^5+10 q^4+20 q^3+28 q^2+28 q+14 \) \( 5 \) \( q^{10}+5 q^9+15 q^8+35 q^7+70 q^6+117 q^5+165 q^4+195 q^3+180 q^2+120 q+42 \)

A perfect matching \(M \in \setPM(n)\) may be described as a list of \(n\) tuples, which we represent as an array. \[M= \begin{bmatrix} m_1 & m_3 & m_5 & \dotsc & m_{2n-1} \\ m_2 & m_4 & m_6 &\dotsc & m_{2n}, \end{bmatrix}\] where \(m_{2i-1} \lt m_{2i}\) for \(i\in [n]\) and \(m_{2i-1} \lt m_{2i+1}\) for all \(i \in [n-1].\) That is, the top row is strictly increasing, and the smallest entry in each column appears at the top. We write \((i,j) \in M\) whenever \(\binom{i}{j}\) appears as a column in \(M.\)

R. Gross and A. Šarković study a related Markov chain on chord diagrams where the chords match the sides of a \(2n\)-gon, rather than the vertices [GS26]. Gluing paired sides gives an orientable surface, and the chain swaps endpoints of two chords only when the genus is preserved. For fixed genus, the chain is irreducible except for the maximal-genus Bolza diagram, and its mixing time is polynomial in \(n.\)

#The Pfaffian

Perfect matchings are closely related to Pfaffians. Let \(A\) be a \(2n \times 2n\) skew-symmetric matrix. The Pfaffian of \(A\) is defined as \[\pfaff(A) \coloneqq \sum_{M \in \setPM(n)} (-1)^{cr(M)} \prod_{(i,j) \in M} a_{ij}.\] Then \(\pfaff(A)^2 = |A|.\) See [Ste90] for combinatorial applications of the Pfaffian.

#Projection to Dyck paths

There is a natural projection \(\psi\) from perfect matchings to Dyck paths.

Let \(a_i \coloneqq (2i-1) - m_{2i-1}\) be the area sequence of the matching \(M.\) This defines a map from \(\setPM(n)\) to \(\DP(n).\) One can show \(\psi\) is surjective and that \(\psi: \setPM(n) \to \DP(n)\) restricted to noncrossing perfect matchings is a bijection.

Example

The perfect matching \[\{ \{1, 6\}, \{2, 4\}, \{3, 11\}, \{5, 7\}, \{8, 9\}, \{10, 12\}\}\] is mapped to the area sequence \(0 1 2 2 1 1\) which is the Dyck path \(0 0 0 1 0 1 1 0 1 0 1 1.\)

Perfect matching on 12 vertices.

$ \emph{1} $           $ 10$ $ \emph{1} $         $ 8$   $ \emph{2} $       $ 5$     $ \emph{2} $     $ 3$       $ \emph{1} $   $ 2$         $ \emph{0} $ $ 1$          

#Acyclic orientations of unit interval graphs

Let \(AO(\avec)\) be the set of acyclic orientations on the unit interval graph with area sequence \(\avec.\) Furthermore, let \(\asc(\theta)\) be the number of edges oriented from smaller to larger vertex label. Then

Theorem (See [Sec. 9, AP18]).

\[X_\avec(q) = \sum_{\theta \in AO(\avec)} q^{\asc(\theta)}.\]

#Rook placements

Given an area sequence \(\avec\) of length \(n,\) we can complete the Dyck path to a Ferrers board. Let \(RP(\avec)\) be the set of non-attacking rook placements on this board, using \(n\) rooks. An inversion of a rook placement \(\pi\) is a square on the board with no rook above it, and no rook to its left. Let \(\inv(\pi)\) denote the number of such inversions.

Theorem (See, for example, [Sec. 9, AP18]).

\[X_\avec(q) = \sum_{\pi \in RP(\avec)} q^{\inv(\pi)}.\]

The fact that the number of rook placements factors nicely was first proved in [GJW75]. Another \(q\)-analogue of the above identity is due to A. Garsia and J. Remmel [GR86].

#Macdonald polynomials

P. Alexandersson and J. Uhlin prove that \[[\monomial_{1^{2n}}] \macdonaldE_{(n,n)}(\xvec;q,0) = [n]_q! T_n(q).\] This is [Prop. 5.9, AU20]; the formula appears as a conjecture in [Uhl19].

The same paper explains how this specialization sits inside the usual Macdonald hierarchy. For a partition \(\lambda,\) the polynomial \(\macdonaldE_\lambda(\xvec;q,0)\) agrees with \(\omega Q'_{\lambda'}(\xvec;q),\) where \(Q'_\lambda\) is the transformed Hall–Littlewood polynomial [Prop. 2.16, AU20]. It is also the coefficient of the highest power of \(t\) in the corresponding modified Macdonald polynomial \(\macdonaldH_\lambda(\xvec;q,t)\) [Sec. 2.8, AU20]. Thus the coefficient above can be viewed as a Touchard–Riordan specialization inside the modified Macdonald family. The cyclic-sieving statement for these specialized nonsymmetric Macdonald polynomials also has a fixed-content refinement: the coefficient \([\monomial_\nu]\macdonaldE_{n\lambda}(\xvec;q,0)\) is itself a cyclic-sieving polynomial for coinversion-free fillings of shape \(n\lambda\) and content \(\nu\) [Thm. 4.3, AU20].

#Catalan words and a PBW basis

P. Terwilliger uses Catalan words and a \(q\)-shuffle algebra to give closed-form expressions for I. Damiani’s recursively defined PBW basis for the positive part of \(U_q(\widehat{\mathfrak{sl}}_2)\) [Ter19]. This is a nearby use of Catalan-indexed words and \(q\)-weights, although the \(q\)-analogue in that setting is not the same as the Touchard–Riordan weight \(X_\avec(q)\) used above.

#Other references

See [CZ11] for connection with Hermite polynomials and \(q\)-Fibonacci numbers.

E. Bagno and D. Garber define symmetric functions that enumerate set partitions by positions \(i\) for which \(i\) and \(i+1\) lie in the same block [BG26]. They prove hook-Schur positivity, with the hook coefficients given by Touchard–Riordan polynomials; in the noncrossing case the coefficients form the Motzkin triangle.

Bibliography

  1. [AP18]Per Alexandersson and Greta Panova. LLT polynomials, chromatic quasisymmetric functions and graphs with cycles. Discrete Mathematics, 341(12):3453–3482, December 2018.
    .bib
    @article{AlexanderssonPanova2018,
  doi = {10.1016/j.disc.2018.09.001},
  url2 = {https://doi.org/10.1016/j.disc.2018.09.001},
  year  = {2018},
  month = dec,
  publisher = {Elsevier {BV}},
  volume = {341},
  number = {12},
  pages = {3453--3482},
  author = {Per Alexandersson and Greta Panova},
  title = {{LLT} polynomials,  chromatic quasisymmetric functions and graphs with cycles},
  journal = {Discrete Mathematics}
}
  2. [AU20]Per Alexandersson and Joakim Uhlin. Cyclic sieving, skew Macdonald polynomials and Schur positivity. Algebraic Combinatorics, 3(4):913–939, 2020.
    .bib
    @article{AlexanderssonUhlin2020,
     author = {Alexandersson, Per and Uhlin, Joakim},
     title = {Cyclic sieving, skew {M}acdonald polynomials and {S}chur positivity},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {3},
     number = {4},
     year = {2020},
     pages = {913-939},
     doi = {10.5802/alco.123},
     language = {en},
     url2 = {alco.centre-mersenne.org/item/ALCO_2020__3_4_913_0/}
}
  3. [BG26]Eli Bagno and David Garber. Touchard-Riordan Polynomials and Schur-positivity of Set Partitions. arXiv:2606.13149v1, 2026.
    .bib
    @article{BagnoGarber2026x,
  author = {Eli Bagno and David Garber},
  title = {Touchard-{R}iordan {P}olynomials and {S}chur-positivity of {S}et
    {P}artitions},
  year = {2026},
  eprint = {2606.13149v1},
  url = {https://arxiv.org/abs/2606.13149v1},
  journal = {arXiv e-prints},
  journalref = {EPTCS 445, 2026, pp. 1-9},
  doi = {10.4204/EPTCS.445.1}
}
  4. [CZ11]Johann Cigler and Jiang Zeng. A curious $q$-analogue of Hermite polynomials. Journal of Combinatorial Theory, Series A, 118(1):9–26, January 2011.
    .bib
    @article{CiglerZeng2011,
  doi = {10.1016/j.jcta.2010.09.001},
  url2 = {https://doi.org/10.1016/j.jcta.2010.09.001},
  year = {2011},
  month = jan,
  publisher = {Elsevier {BV}},
  volume = {118},
  number = {1},
  pages = {9--26},
  author = {Johann Cigler and Jiang Zeng},
  title = {A curious $q$-analogue of {H}ermite polynomials},
  journal = {Journal of Combinatorial Theory,  Series A}
}
  5. [Fla06]Philippe Flajolet. Combinatorial aspects of continued fractions. Discrete Mathematics, 306(10-11):992–1021, May 2006.
    .bib
    @article{Flajolet2006,
  doi = {10.1016/j.disc.2006.03.020},
  url2 = {https://doi.org/10.1016/j.disc.2006.03.020},
  year = {2006},
  month = may,
  publisher = {Elsevier {BV}},
  volume = {306},
  number = {10-11},
  pages = {992--1021},
  author = {Philippe Flajolet},
  title = {Combinatorial aspects of continued fractions},
  journal = {Discrete Mathematics}
}
  6. [GR86]Adriano M. Garsia and Jeffrey B. Remmel. ${Q}$-counting rook configurations and a formula of Frobenius. Journal of Combinatorial Theory, Series A, 41(2):246–275, 1986.
    .bib
    @article{GarsiaRemmel1986,
title = {${Q}$-counting rook configurations and a formula of {F}robenius},
journal = {Journal of Combinatorial Theory, Series A},
volume = {41},
number = {2},
pages = {246--275},
year = {1986},
issn = {0097-3165},
doi = {10.1016/0097-3165(86)90083-X},
url2 = {http://www.sciencedirect.com/science/article/pii/009731658690083X},
author = {Adriano M. Garsia and Jeffrey B. Remmel}
}
  7. [GJW75]Jay R. Goldman, J. T. Joichi and Dennis E. White. Rook theory. I. Rook equivalence of Ferrers boards. Proceedings of the American Mathematical Society, 52(1):485–485, January 1975.
    .bib
    @article{GoldmanJoichiWhite1975,
  doi = {10.1090/s0002-9939-1975-0429578-4},
  url2 = {https://doi.org/10.1090/s0002-9939-1975-0429578-4},
  year = {1975},
  month = jan,
  publisher = {American Mathematical Society ({AMS})},
  volume = {52},
  number = {1},
  pages = {485--485},
  author = {Jay R. Goldman and J. T. Joichi and Dennis E. White},
  title = {Rook theory. {I}. {R}ook equivalence of {F}errers boards},
  journal = {Proceedings of the American Mathematical Society}
}
  8. [GS26]Renan Gross and Anela Šarković. Polynomial mixing for polygonal side matchings. arXiv:2607.02410, 2026.
    .bib
    @article{GrossSarkovic2026x,
  author = {Renan Gross and An{\dj}ela {\v{S}}arkovi{\'c}},
  title = {Polynomial mixing for polygonal side matchings},
  year = {2026},
  eprint = {2607.02410},
  url = {https://arxiv.org/abs/2607.02410},
  journal = {arXiv e-prints}
}
  9. [PR22]Amritanshu Prasad and Samrith Ram. Splitting subspaces and a finite field interpretation of the Touchard–Riordan formula. arXiv:2205.11076, 2022.
    .bib
    @article{PrasadRam2022x,
Author = {Amritanshu Prasad and Samrith Ram},
Title = {Splitting subspaces and a finite field interpretation of the {T}ouchard--{R}iordan Formula},
Year = {2022},
Eprint = {2205.11076},
  url = {https://arxiv.org/abs/2205.11076},
journal = {arXiv e-prints}
}
  10. [Rea79]Ronald C. Read. The chord intersection problem. Annals of the New York Academy of Sciences, 319(1):444–454, May 1979.
    .bib
    @article{Read1979,
  doi = {10.1111/j.1749-6632.1979.tb32822.x},
  url2 = {https://doi.org/10.1111/j.1749-6632.1979.tb32822.x},
  year = {1979},
  month = may,
  publisher = {Wiley},
  volume = {319},
  number = {1},
  pages = {444--454},
  author = {Ronald C. Read},
  title = {The chord intersection problem},
  journal = {Annals of the New York Academy of Sciences}
}
  11. [Ste90]John R. Stembridge. Nonintersecting paths, pfaffians, and plane partitions. Advances in Mathematics, 83(1):96–131, September 1990.
    .bib
    @article{Stembridge1990,
  doi = {10.1016/0001-8708(90)90070-4},
  url2 = {https://doi.org/10.1016/0001-8708(90)90070-4},
  year = {1990},
  month = sep,
  publisher = {Elsevier {BV}},
  volume = {83},
  number = {1},
  pages = {96--131},
  author = {John R. Stembridge},
  title = {Nonintersecting paths,  pfaffians,  and plane partitions},
  journal = {Advances in Mathematics}
}
  12. [Ter19]Paul Terwilliger. Using Catalan words and a q-shuffle algebra to describe a PBW basis for the positive part of ${U}_q(sl^2)$. Journal of Algebra, 525:359–373, May 2019.
    .bib
    @article{Terwilliger2019,
  doi = {10.1016/j.jalgebra.2019.02.010},
  url2 = {https://doi.org/10.1016/j.jalgebra.2019.02.010},
  year = {2019},
  month = may,
  publisher = {Elsevier {BV}},
  volume = {525},
  pages = {359--373},
  author = {Paul Terwilliger},
  title = {Using {C}atalan words and a q-shuffle algebra to describe a {PBW} basis for the positive part of ${U}_q(sl^2)$},
  journal = {Journal of Algebra}
}
  13. [Uhl19]Joakim Uhlin. Combinatorics of Macdonald polynomials and cyclic sieving. TRITA-SCI-GRU. KTH, Mathematics (Div.), 2019.
    .bib
    @mastersthesis{Uhlin2019,
   author = {Joakim Uhlin},
   school = {KTH, Mathematics (Div.)},
   title = {Combinatorics of {M}acdonald polynomials and cyclic sieving},
   series = {TRITA-SCI-GRU},
   type = {M.S Thesis},
   url = {http://kth.diva-portal.org/smash/record.jsf?pid=diva2%3A1282825},
   urn = {urn:nbn:se:kth:diva-241919},
   number = {2019:008},
   year = {2019},
   month = jan
}

I use cookies to detect website issues and track search terms.