Skip to main content
Source Link
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

There is a nice generalization to Catalan objects as follows.

Acyclic orientations of unit-interval graphs

Note that for the complete graph on $n$ vertices, the number of acyclic orientations weighted by ascents (edges oriented from smaller to larger label) is given by $[n]_q!$. Now, there are a Catalan number of unit interval graphs, which can be indexed by area sequences. The complete graph has area sequence $(0,1,2,\dotsc,n-1)$. The weighted sum over acyclic orientations of an unit interval graph with area sequence $(a_1,\dotsc,a_n)$ is given by the product $[a_1+1]_q\dotsb [a_n+1]_q$.

Summing all these polynomials over all $(n+1)^{-1}\binom{2n}{n}$ area sequences of length $n$ gives the $n$th Touchard-Riordan polynomial, which is defined as the sum over all perfect matchings of $2n$ vertices on a circle, weighted by $q$ to the number of crossings.

Perfect matchings

In particular, $[n]_q!$ is the sum over all perfect matchings on $2n$ vertices, where vertices $1,2,\dotsc,n$ are matched with $n+1,n+2,\dotsc,2n$.

Rook placements on Ferrers board

Let $a$ be an area sequence. A Ferrers board with row lengths given by $a_i+n-i$ for $i=1,\dotsc,n$ allows for $[a_1+1]_q\dotsb [a_n+1]_q$ different ways to place $n$ non-attacking rooks, and the weight is now given by rook inversions.

I have some more info and references here.

Post Made Community Wiki by Per Alexandersson