The symmetric functions catalog

An overview of symmetric functions and related topics

2020-02-05

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.

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

Macdonald polynomials

In an upcoming paper, 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