Lesson 11

Another way to derive the formula: we need to choose \(n_{1}\) positions for symbol 1, from the remaining \(n-n_{1}\) positions — \(n_{2}\) positions for symbol 2, from the remaining \(n-n_{1}-n_{2}\) positions — \(n_{3}\) positions for symbol 3, and so on.

\[\begin{align*}\binom{n}{n_1}\binom{n-n_1}{n_2}\dotsb \binom{n-n_1-n_2-\dotsb-n_{t-1}}{n_t}=\\ =\frac{n!}{n_1!(n-n_1)!}\cdot \frac{(n-n_1)!}{n_2!(n-n_1-n_2)!}\cdot \frac{(n-n_1-n_2)!}{n_3!(n-n_1-n_2-n_3)!}\dotsb \frac{(n-n_1-\dotsb-n_{t-1})!}{n_t!0!}=\\ =\frac{(n_1+n_2+\dotsb+n_t)!}{n_1!n_2!\dotsb n_t!}\ .\end{align*}\]