3
$\begingroup$

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.

  • 0
    @MatthewKahle I've replaced $k$ with $q$ to make the notation more standard, and linked to the definitions. Sorry about that!2011-12-14

1 Answers 1

2

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.$

  • 0
    @urpi: Yes, it's straightforward. It's well-known that the q-multinomial is the ordinary generating function for the inversion statistic on words where the letter $i$ appears $m_i$ times. The terms on the right-hand side arise from grouping together words according to their first letter: if the first letter is $i$, there must be $m_1 + m_2 + \cdots + m_{i-1}$ inversions involving that letter, and the rest follows easily. (This is surely very well known, but I don't know of a reference and am putting it in a tiny lemma in a paper I'm finishing up tonight....)2018-09-09