Combinatorial interpretation of q-analog Stirling numbers of the second kind I understand that combinatorially we can interpret the Stirling numbers of the second kind as the number of partitions of $n$ into $k$ parts. I was wondering what combinatorial interpretation we could give the $q$-analog of the Stirling numbers of the second kind, $S_q(n,k)$?
Thanks for your help
 A: Let $\pi$ be a partition of $[n]$ into $k$ blocks; if the blocks are $B_1,\ldots,B_k$ with 
$$\min B_1<\min B_2<\ldots<\min B_k$$
I’ll write $\pi=B_1/B_2/\ldots/B_k$. We can encode $\pi$ by a restricted growth word (RG-word) $w(\pi)=w_1w_2\ldots w_n$, where $w_i=j$ if $i\in B_j$. We define inversions of RG-words in the usual way: an inversion of $w(\pi)$ is a pair $\langle i,j\rangle$ such that $i<j$ and $w_j<w_i$. I will call these inversions of $\pi$. (Equivalently, we can define an inversion of $\pi$ directly as a pair $\langle b,B_j\rangle$ such that $b>\min B_j$, but $b\in B_i$ for some $i<j$.) Let $\Pi(n,k)$ be the set of partitions of $[n]$ into $k$ blocks, and for $\pi\in\Pi(n,k)$ let $\operatorname{inv}(\pi)$ be the number of inversions of $\pi$. Then
$$S_q(n,k)=\sum_{\pi\in\Pi(n,k)}q^{\operatorname{inv}(\pi)}\;.$$
We can also define an analogue of the major index. Let $\pi=B_1/B_2/\ldots/B_k\in\Pi(n,k)$. For $i=1,\ldots,k-1$ let $d_i$ be the number of elements of $B_i$ that are greater than $\min B_{i+1}$; we define the descent multiset $D(\pi)$ to be
$$\left\{\!\!\left\{1^{d_1},2^{d_2},\ldots,(k-1)^{d_{k-1}}\right\}\!\!\right\}\;,$$
where the exponents are repetition factors. We then define the major index $\operatorname{maj}(\pi)$ of $\pi$ to be
$$\operatorname{maj}(\pi)=\sum_{i=1}^{k-1}id_i\;,$$
and it turns out that
$$S_q(n,k)=\sum_{\pi\in\Pi(n,k)}q^{\operatorname{maj}(\pi)}$$
as well.
You can find all of this and more in Bruce E. Sagan, A maj Statistic for Set Partitions [PDF]. A slightly different (equivalent) approach is taken in Yue Cai & Margaret A. Readdy, q-Stirling numbers: A new view, which discusses RG-words in detail. And I actually got most of it from Chapter $3$ of Johann Cigler’s lecture notes Elementare q-Identitäten.
