# What's the reasoning for this recurrence on $q$-multinomial coefficients?

I'm familiar with the recurrence for binomial coefficients based on Pascal's triangle. However, in general, there is the recurrence for $q$-multinomial coefficients given by $$\binom{n}{m_1,m_2,\dots,m_r}_q=\binom{n-1}{m_1-1,m_2,\dots,m_r}_q+q^{m_1}\binom{n-1}{m_1,m_2-1,\dots,m_r}_q+\cdots$$ $$\hspace{1.8in}\cdots+q^{m_1+\cdots+m_{r-1}}\binom{n-1}{m_1,m_2,\dots,m_r-1}_q.$$

How can one derive that this recurrence is true?

Just in case, here are the relevant definitions for $q$-multinomial and $q$-factorial.

-
I know what ${n \choose m_1, m_2, \dots, m_3}$ means, but I'm not sure what it means when you put a subscript $k$. Could you add a definition? –  Matthew Kahle Dec 14 '11 at 21:47
@MatthewKahle I've replaced $k$ with $q$ to make the notation more standard, and linked to the definitions. Sorry about that! –  Ann Veal Dec 14 '11 at 21:55

Notice the "modular" factorization (keep in mind $n=m_1+m_2+\cdots+m_r$):

$$[n]_q=[m_1]_q+q^{m_1}[m_2]_q+q^{m_1+m_2}[m_3]_q+\cdots+q^{m_1+\cdots+m_{r-1}}[m_r]_q. \tag{a}$$

Basically what we've done is taken $[n]_q=q^0+q^1+q^2+\cdots+q^{n-1}$ and partitioned it into the first $m_1$ terms, the second $m_2$ terms, and so on to the last $m_r$ terms, and then factored out the highest power of $q$ from each cell of the partition until we're left with a linear combination of the analog terms $[m_i]_q$, $i=1,\dots,r$. Now take $(a)$ and divide both sides by $[n]_q$, then multiply by the $q$-multinomial and distribute the multiplication through to obtain

$$\frac{[m_1]_q}{[n]_q}{n\choose m_1,\dots,m_r}+\cdots+\frac{q^{m_1+\cdots+m_{r-1}}[m_r]_q}{[n]_q}{n\choose m_1,\dots,m_r}. \tag{b}$$

Use the relation $[a]_q!=[a]_q\cdot[a-1]_q$ in the $q$-factorials implicit in each term's $q$-multinomial;

$$\small \binom{n}{m_1,m_2,\dots,m_r}_q=\binom{n-1}{m_1-1,m_2,\dots,m_r}_q+\cdots q^{m_1+\cdots+m_{r-1}}\binom{n-1}{m_1,m_2,\dots,m_r-1}_q.$$

Here's an example to better illustrate $(a)$. Set $n=9, m_{1,2,3}=2,3,4$. Then

$$[9]_q=\color{Red}{1+q}+\color{Green}{q^2+q^3+q^4}+\color{Blue}{q^5+q^6+q^7+q^8}$$

$$=(\color{Red}{1+q})+q^2(\color{Green}{1+q+q^2})+q^5(\color{Blue}{1+q+q^2+q^3})$$

$$=[2]_q+q^2[3]_q+q^{2+3}[4]_q.$$

-
Many thanks anon! –  Ann Veal Dec 15 '11 at 22:40