We want to find the number of possibilities to assign elements to multiple partitions of fixed sizes. Assume that there are $r$ partitions and each has a respective size $n_i$. $ N=\frac{n!}{n_1!n_2!\cdots n_r!} $ ![[partitions.png|center|400]] This is a generalization of the [[Binomial Coefficient]], in which there are just 2 partitions (e.g. heads of tails), and the size of the first partition is $k$. Therefore the number of partitions is also called “multinomial coefficient”. $ \begin{rcases} n_1=k \\ n_2=n-k \end{rcases} \frac{n!}{n_1!n_2!} = \frac{n!}{k!(n-k)!} $ ## Derivation We know from permutation that the number of combinations how $n$ elements can be ordered (i.e. [[Permutation]]) is $(n!)$. - *Permutations for a single split:* The same can be achieved by fixing the allocation of all elements to certain partitions. For this allocation the number possible orderings is the product of the permutations from each partition. $ \prod_r n_i! = n_1!n_2!\cdots n_r! $ - *Permutations for all splits:* When we multiply this by the number of possible allocations of elements to partitions $x$, we obtain the number of combinations overall $(n!)$. $ \begin{align} n! &= x*n_1!n_2!\cdots n_r! \\[6pt] x &= \frac{n!}{n_1!n_2!\cdots n_r!} \end{align} $ ## Multinomial Probabilities We have $r$ different partitions, and each draw has a probability $p_i$ to be allocated to a partition $i$. We want to know the probability for a certain partitioned outcome to occur. Similarly to the binomial probabilities, where we multiply the binomial coefficient with $p^k*(1-p)^{n-k}$, here we multiply the multinomial coefficient with all $p_i$. $ \mathbf P(n_1, n_2,\dots, n_r)= \frac{n!}{n_1!n_2!\cdots n_r!}*p_1^{n_1}*p_2^{n_2}*\cdots p_r^{n_r} $