Monday 11 January 2016

combinatorics - Notation for writing multinomial coefficient as sum of smaller multinomial coefficients



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?


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


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...