3
$\begingroup$

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

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Why don't we take into consideration partitioning three-elements set into three groups say ({1},{2},{3}) ? $\endgroup$
    – Pasato
    Commented Jul 1, 2014 at 15:21
  • $\begingroup$ Because you explicitly stipulated $k\lt n$. $\endgroup$
    – whuber
    Commented Jul 1, 2014 at 15:42
  • $\begingroup$ Right. Thanks for answering whuber. Have you any idea how to solve it "algebraically" using binomial coefficients? $\endgroup$
    – Pasato
    Commented Jul 1, 2014 at 16:16
  • $\begingroup$ 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. $\endgroup$
    – whuber
    Commented Jul 1, 2014 at 16:30
  • $\begingroup$ 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 $\endgroup$
    – Pasato
    Commented Jul 1, 2014 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.