Question

I don't understand how to solve this question. It's from a textbook on Probability Theory by Jim Pitman. It's on the appendix section on counting.

a) Prove that for ko + k1 +K2 = n, the number of sequences of 0's, 1's, and 2's of length n which contain exactly ko 0's, ki l's and ka 2's is h (b) Generalize your formula to find the number of sequences of the numbers 0, 1, 2,..., m of length n in which the number j appears k, times. These (viii) kolk!k2! numbers are called multinomial coefficients.

Answer 1

$(a)~There~are~three~groups:~Group~1~consists~of~0's~with~size~k_0,\\ Group~2~consists~of~1's~with~size~k_1,~Group~3~consists~of~2's~with~size~k_2.\\ Here,~k_0+k_1+k_2=n.\\ Hence~total~no.~of~arrangements~k_0~0's,~k_1~1's~and~k_2~2's~i.e.~no.~of~sequences~of~0's,\\ 1s'~and~2's~of~length~n~which~contain~k_0~0's,~k_2~1's~and~k_2~2's=\binom{n}{k_0}\binom{n-k_0}{k_1}\\ =\frac{n!}{k_0!k_1!k_2!}~i.e.first~we~choose~k_0~places~from~n~places~where~we~place~0's~in~\binom{n}{k_0},\\ then~we~choose~k_1~places~from~remaining~n-k_0~places~where~we~place~1's~in~\binom{n-k_0}{k_1}~ways,\\ lastly~we~place~k_2~2's~in~remaining~n-k_0-k_1=k_2~places.\\ (b)~Suppose~there~are~(m+1)~groups~and~ith~group~has~k_i~size,\\ ~i=0,1,...,m~with~\sum_{i=0}^{m+1}k_i=n.\\ Then~total~no.~sequences~using~the~symbols~0,1,2,...,m\\ =\binom{n}{k_0}\binom{n-k_0}{k_1}...\binom{n-k_0-k_1-...-k_{m-1}}{k_{m-1}}=\frac{n!}{k_0!k_1!...k_{m}!}\\ ~where,~\sum_{i=0}^mk_i=n$