# 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$.

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

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

2. $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.

• Why don't we take into consideration partitioning three-elements set into three groups say ({1},{2},{3}) ? Commented Jul 1, 2014 at 15:21
• Because you explicitly stipulated $k\lt n$.
– whuber
Commented Jul 1, 2014 at 15:42
• Right. Thanks for answering whuber. Have you any idea how to solve it "algebraically" using binomial coefficients? Commented Jul 1, 2014 at 16:16
• Yes I do; but if you are primarily concerned with mathematical methods of solution, then please consider posting your question on Mathematics with a clear indication of what methods you want help with.
– whuber
Commented Jul 1, 2014 at 16:30
• I've just hoped for some other way as I'am probably not entirely able to follow your solution .. If you'd be so kind to post it I would highly appreciate it Commented Jul 1, 2014 at 17:06