2024-03-18

## 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 of size $\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[2]_q}{ 1 - \cfrac{z^3[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 appear at the top. We write $(i,j) \in M$ whenever $\binom{i}{j}$ appear as a column in $M.$

### 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}. \]We have that $\pfaff(A)^2 = |A|.$ See [Ste90] for combinatorial appliactions 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 *non-crossing* 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.$

1 | 10 | |||||

1 | 8 | |||||

2 | 5 | |||||

2 | 3 | |||||

1 | 2 | |||||

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 [Section 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 e.g. [Section 9, AP18]).**\[ X_\avec(q) = \sum_{\pi \in RP(\avec)} q^{\inv(\pi)}. \]

The fact that the number or rook placements factors nicely was first proved in [GJW75]. Another $q$-analog of the above identity is due to Garsia and Remmel, [GR86],

### Macdonald polynomials

In [Prop. 5.9, AU20] J. Uhlin and I prove that

\[ [\monomial_{1^{2n}}] \macdonaldE_{(n,n)}(\xvec;q,0) = [n]_q! T_n(q). \]This formula appear as a conjecture in [Uhl19].

## Other references

See [CZ11] for connection with Hermite polynomials and $q$-Fibonacci numbers.

## References

- [AP18] Per Alexandersson and Greta Panova. LLT polynomials, chromatic quasisymmetric functions and graphs with cycles. Discrete Mathematics, 341(12):3453–3482, December 2018.
- [AU20] Per Alexandersson and Joakim Uhlin. Cyclic sieving, skew Macdonald polynomials and Schur positivity. Algebraic Combinatorics, 3(4):913-939, 2020.
- [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.
- [Fla06] Philippe Flajolet. Combinatorial aspects of continued fractions. Discrete Mathematics, 306(10-11):992–1021, May 2006.
- [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.
- [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.
- [PR22] Amritanshu Prasad and Samrith Ram. Splitting subspaces and a finite field interpretation of the Touchard–Riordan formula. arXiv e-prints, 2022.
- [Rea79] Ronald C. Read. The chord intersection problem. Annals of the New York Academy of Sciences, 319(1):444–454, May 1979.
- [Ste90] John R. Stembridge. Nonintersecting paths, pfaffians, and plane partitions. Advances in Mathematics, 83(1):96–131, September 1990.
- [Uhl19] Joakim Uhlin. Combinatorics of Macdonald polynomials and cyclic sieving. 2019.