Guichard-Combinatorics-Graph-Theory · Problem 1.5.4

Fundamentals

Mathematics — Probability · multinomial-coefficients

Problem

Let M=∑i=1nmiM = \sum_{i=1}^{n} m_i. If ki<0k_i < 0 for some ii, let's say (Mk1 k2 … kn)=0\binom{M}{k_1\, k_2\, \ldots\, k_n} = 0. Prove that (Mm1 m2 … mn)=∑i=1n(M−1m1 m2 … (mi−1) … mn).\binom{M}{m_1\, m_2\, \ldots\, m_n} = \sum_{i=1}^{n} \binom{M-1}{m_1\, m_2\, \ldots\, (m_i-1)\, \ldots\, m_n}. Note that when n=2n=2 this becomes (Mm1 m2)=(M−1(m1−1) m2)+(M−1m1 (m2−1)).\binom{M}{m_1\, m_2} = \binom{M-1}{(m_1-1)\, m_2} + \binom{M-1}{m_1\, (m_2-1)}. As noted above in equation 1.5.1, when n=2n=2 we are really seeing ordinary binomial coefficients, and this can be rewritten as (Mm1)=(M−1m1−1)+(M−1m1),\binom{M}{m_1} = \binom{M-1}{m_1-1} + \binom{M-1}{m_1}, which of course we already know.

Browse the problem library