

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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




share|cite|improve this answer
Many thanks anon! – Ann Veal Dec 15 '11 at 22:40

Your Answer


