Notation for writing multinomial coefficient as sum of smaller multinomial coefficients

355 Views Asked by At

This question is an attempt to extend the Pascal triangle's hockey stick identity to multinomial coefficients as asked in question Hockey-Stick Theorem for Multinomial Coefficients.

Consider the following recursive relation:

$$\binom{n_1+n_2+\cdots+n_t}{n_1,n_2,\cdots,n_t}=\sum_{\text{For all nonzero $x_j$ except last}}\binom{n_1+n_2+\cdots+n_t-1}{n_1,\cdots,n_j-1,\cdots,n_t}+ \binom{n_1+n_2+\cdots+n_t-1}{n_1,n_2,\cdots,n_t-1}_{\text{$n_t$ being last non-zero $x_j$}}$$

where $$\binom{n_1+n_2+\cdots+n_t}{n_1,n_2,\cdots,n_t}=\frac{(n_1+n_2+\cdots+n_t)!}{n_1! n_2! \cdots n_t!} $$ Example: \begin{eqnarray} \binom{6}{3,1,2}&=&\binom{5}{2,1,2}+\binom{5}{3,0,2}+\binom{5}{3,1,1}\\ &=&\binom{5}{2,1,2}+\binom{5}{3,0,2}+\left\{ \binom{4}{2,1,1}+\binom{4}{3,0,1}+\binom{4}{3,1,0} \right\}\\ &=&\binom{5}{2,1,2}+\binom{5}{3,0,2}+\binom{4}{2,1,1}+\binom{4}{3,0,1}+ \left\{\binom{3}{2,1,0}+\binom{3}{3,0,0} \right\}\\ &=&\binom{5}{2,1,2}+\binom{5}{3,0,2}+\binom{4}{2,1,1}+\binom{4}{3,0,1}+ \binom{3}{2,1,0}+\left\{\binom{2}{2,0,0} \right\}\\ \end{eqnarray} How may I write the following line in compact sigma notation?

$$\binom{6}{3,1,2}=\binom{5}{2,1,2}+\binom{5}{3,0,2}+\binom{4}{2,1,1}+\binom{4}{3,0,1}+ \binom{3}{2,1,0}+\binom{2}{2,0,0}$$

How to write it for general form?

1

There are 1 best solutions below

0
On BEST ANSWER

$$\binom{n_1+n_2+\cdots+n_t}{n_1,n_2,\cdots,n_t}=1+\sum_{i=2}^t \sum_{j=1}^{i-1} \sum_{k=1}^{n_i} \binom{ n_1+n_2+\cdots+n_{i-1}+k }{n_1,n_2,\cdots,n_j-1,\cdots,n_{i-1},k }$$