exercise in probability Consider the situation where n items are to be partitioned into $k < n$ distinct subsets. 
The
multinomial coefficients. provide the number of distinct partitions where $n_1$ items are in group $1$, $n_2$ are in group $2$, . . . , $n_k$ are in group $k$. Prove that the total number of distinct partitions equals $k^n$ 
I apologise for not using any symbolic notation, don't know how to do it yet.
I assume we need to use binomial coefficient to get the left-hand side of the equation i.e $(x+y)^n$. So it basically boils down to proving $x+y = k$. 
 A: The question needs to be modified in order for the assertion to be true.  We need to understand a "$k$-partition" of an $n$-set $S$ to be an ordered $k$-tuple of not necessarily distinct subsets
$$\pi = (S_0, S_1, \ldots, S_{k-1})$$
for which


*

*$S_0\cup S_1\cup \cdots \cup S_{k-1} = S$ and

*$S_i\cap S_j = \emptyset$ for all $i\ne j$.
For instance, the $2$-partitions of $S=\{1,2,3\}$ ($k=2, n=3$) are
$$(\{1,2,3\},\emptyset),\quad (\emptyset, \{1,2,3\}), \\
(\{1,2\},\{3\}), \quad(\{3\}, \{1,2\}), \\
(\{1,3\},\{2\}), \quad(\{2\}, \{1,3\}), \\
(\{2,3\},\{1\}), \quad(\{1\}, \{2,3\})$$
of which there are indeed $k^n=2^3=8$.
(Note that the $S_i$ are not necessarily distinct under this definition. For instance, one ordered $3$-partition of $\{1,2,3,4\}$ is $(\{1,2,3,4\}, \emptyset, \emptyset)$ for which $S_1=S_2$.)
One way to obtain the claimed result is to observe there is a one-to-one correspondence between all such partitions and the functions from $S$ to $\{0, 1,2,\ldots, k-1\}$.  The function associated with $\pi$ is
$$f_\pi(i) = j\text{ iff }i \in S_j.$$
That is, its value at $i$ is the position of the subset in which $i$ is located.  Conversely, any such function $f$ determines a partition $\pi_f$ where $S_j = f^{-1}(j)$ consists of all elements $i$ for which $f(i)=j$ ($j=0, 1, \ldots, k-1$).
A simple way to count all such functions is to think of how you would write one of them down.  To do so, create a list of $n$ blanks, one for each element of $S$.  Write the value of $f$ (a digit between $0$ and $k-1$) in each blank.  In this way the number of such functions is seen to equal the number of length-$n$ strings that can be formed from an alphabet of $k$ characters.  Equivalently, it counts all the integers that can be written using $n$ base-$k$ digits.  For example, the strings corresponding to the $2$-partitions of $\{1,2,3\}$ as listed above, in the same order, are
$$000, 111;\ 001, 110;\ 010, 101;\ 100, 011.$$
Read as binary numbers, these are $0,7;1,6;2,5;4,3$, which when ordered form the sequence from $0$ through $2^3-1$ inclusive.
The result is now easy to obtain.

Another method begins with the multinomial generating function
$$f(x_0,x_1,\ldots, x_{k-1}) = (x_0+x_1+\cdots+x_{k-1})^n.$$
Expanding this requires selecting an $x_0$ from certain of the $n$ terms $ (x_0+x_1+\cdots+x_{k-1})$, an $x_1$ from certain other terms, and so on. That process corresponds to an ordered partition of the terms and all such ordered partitions have to be considered.  Each monomial $x_0^{j_0}x_1^{j_1}\cdots x_{k-1}^{j_{k-1}}$ in the expanded result has total degree $n$ and its coefficient counts the number of times $j_0$ copies of $x_0$ appear, $j_1$ copies of $x_1$, and so on.  The sum of the coefficients therefore counts the total number of $k$-partitions. For example, with $k=2$ and $n=3$ we find
$$\eqalign{
\left(x_0+x_1\right)^3 &= x_0x_0x_0 + x_1x_1x_1 + x_0x_0x_1+x_1x_1x_0 + x_0x_1x_0 + x_1x_0x_1 + x_1x_0x_0 + x_0x_1x_1 \\ &=x_0^3+3 x_1 x_0^2+3 x_1^2 x_0+x_1^3}$$
with the sum of coefficients $1+3+3+1=2^3$.  (Compare the patterns of subscripts on the first line to the previous two ways of describing the $2$-partitions of $\{1,2,3\}$.)
That sum is easily obtained in general by setting $x_1=x_2=\cdots=x_k=1$.  Another way to compute it is to evaluate $f(1,1,\ldots,1)$, immediately producing the desired formula.
