Combinatorial Interpretation of $q$-analogue Stirling numbers?

Question

I have a recursive definition of the $q$-analogue of the Stirling numbers of the second kind. They are given by the recurrence $S_{q}(n,k) = [k]_{q}S_{q}(n-1,k) + q^{k-1}S_{q}(n-1,k-1)$, where $[k]_q=1+q+q^2+\cdots+q^{k-1}$ and the initial conditions are $S_q(n, 0)=S_q(0, n)=\delta_{0,n}$.

Is there some set that this class of numbers counts? I need to prove some identities, and it may be helpful for me to have a combinatorial interpretation.

Answer 1

Here’s an interpretation involving partitions. It’s my modification of an interpretation in Chapter $3$ of Johann Cigler’s lecture notes that applies to a slightly different $q$-analogue of Stirling numbers of the second kind.

Let $\{P_1^\pi,\ldots,P_k^\pi\}$ be a partition of $[n]$. For $i\in[k]$ let $a_i^\pi=\min P_i^\pi$; we will always assume that $a_1<\ldots<a_k$. An $i$-inversion of $\pi$ is a $b\in\bigcup_{j<i}P_j^\pi$ such that $b>a_i$, and $I(\pi,i)$ is the number of $i$-inversions of $\pi$. Let $w(\pi,i)=I(\pi,i)+i-1$; this is the smallest possible cardinality of $\bigcup_{j<i}P_j^\pi$, given $i$ and $I(\pi,i)$. Let $w(\pi)=\sum_{i\in[k]}w(\pi,i)$, and define the weight of $\pi$ to be $q^{w(\pi)}$. Let $\mathscr{P}(n,k)$ be the set of $k$-partitions of $[n]$, and define

$$p(n,k)=\sum_{\pi\in\mathscr{P}(n,k)}q^{w(\pi)}\;;$$

I claim that $p$ satisfies the recurrence

$$p(n,k)=q^{k-1}p(n-1,k-1)+[k]_qp(n-1,k)\;.\tag{1}$$

Proof: Let $\pi\in\mathscr{P}(n,k)$. If $P_k^\pi=\{n\}$, let $\tau=\{P_1^\pi,\ldots,P_{k-1}^\pi\}\in\mathscr{P}(n-1,k-1)$; it’s easy to check that $w(\pi)=w(\tau)+k-1$. Each $(k-1)$-partition of $[n-1]$ gives rise to such a $k$-partition of $[n]$, and the correspondence is bijective, so the members of $\mathscr{P}(n,k)$ having a part $\{n\}$ (which is necessarily the last part) contribute $q^{k-1}p(n-1,k-1)$ to $p(n,k)$.

Otherwise there is an $i\in[k]$ such that $n\in P_i^\pi\ne\{n\}$. Let $\tau$ be the partition of $[n-1]$ obtained from $\pi$ by removing $n$ from $P_i^\pi$; clearly $\tau\in\mathscr{P}(n-1,k)$. $I(\pi,j)=I(\tau,j)$ if $j\le i$, and $I(\pi,j)=I(\tau,j)+1$ if $j>i$, so $w(\pi)=w(\tau)+k-i$. Conversely, if $\tau\in\mathscr{P}(n-1,k)$, we can add $n$ to any part of $\tau$ to get an element of $\mathscr{P}(n,k)$, and the weight of that element is $q^{k-i}q^{w(\tau)}$ if we add $n$ to $P_i^\tau$. Thus, the total weight of the $k$ partitions of $[n]$ generated in this way from $\tau$ is $[k]_qq^{w(\tau)}$, and hence the members of $\mathscr{P}(n,k)$ not having $\{n\}$ as a part contribute $[k]_qp(n-1,k)$ to $p(n,k)$. This establishes the recurrence $(1)$. $\dashv$

The initial conditions $p(n,0)=p(0,n)=\delta_{n,0}$ are exactly what’s needed in order to make $(1)$ yield the correct values of $p(1,k)$ and $p(n,1)$, so $p(n,k)=S_q(n,k)$.

---

Stephen C. Milne, ‘Restricted Growth Functions, Rank Row Matchings of Partition Lattices, and $q$-Stirling Numbers’, Advances in Mathematics $\mathbf{43}$, $173$-$196$ ($1982$), has a different interpretation in terms of partitions. For $\pi\in\mathscr{P}(n,k)$ and $i\in[n]$ let $J(\pi,i)$ be the number of parts $P_j^\pi$ such that $j<i$ and $P_j^\pi$ contains a number smaller than $i$, and let $J(\pi)=\sum_{i\in[n]}J(\pi,i)$; then $$S_q(n,k)=\sum_{\pi\in\mathscr{P}(n,k)}q^{J(\pi)}\;.$$

---

A.M. Garsia and J.B. Remmel, ‘Q-Counting Rook Configurations and a Formula of Frobenius’, Journal of Combinatorial Theory, Series A $\mathbf{41}$, $246$-$276$ ($1986$) give $S_q(n,k)$ an interpretation involving the number of configurations of $n-k$ non-taking rooks on the staircase Ferrers board.

---

Michelle Wachs and Dennis White, ‘$p,q$-Stirling Numbers and Set Partitions’, Journal of Combinatorial Theory, Series A $\mathbf{56}$, $27$-$46$ ($1991$), have nice generalizations of the interpretations of Milne and of Garsia & Remmel.