Partitions

Partitions

Abstractly, a combination is equivalent to partitioning a set into two subsets, one containing k objects and the other containing the n-k remaining objects. In general, the set S = {1, 2, ... , n } can be partitioned into r subsets. Let $n_1, n_2, \ldots, n_r$ be nonnegative integers such that

$\sum_{p = 1}^r n_p = n.$

Consider the following iterative algorithm that leads to a partition of S. First, we select a subset of $n 1$ elements from S. Having chosen the first subset, we select a second subset containing $n 2$ elements from the remaining $n - n 1$ elements. We continue this procedure by successively choosing subsets of $n p$ elements from the remaining $n - n_1 - \cdots - n_{p-1}$ elements, until no element remains. This algorithm yields a partition of S into r subsets, with the p-th subset containing exactly $n p$ elements.

We wish to count the number of such partitions. We know that there are $\frac{n!}{n_1!(n-n_1)!}$ ways to form the first subset. Examining our algorithm, we see that there are

$\frac{(n - n_1 - \cdots - n_{p-1})!}{n_p!(n - n_1 - \cdots - n_p)!}$

ways to form the p-th subset. Using the counting principle, the total number of partitions is then given by

$\frac{n!}{n_1! n_2! \cdots n_r!} .$

This expression is called a multinomial coefficient.

Example: A die is rolled nine times. We wish to compute the number of outcomes for which every odd number appears three times. The number of distinct sequences in which one, three, and five each appear three times is equal to the number of partitions of {1, 2, ... , 9} into three subsets of size three, namely

$\frac{9!}{3! 3! 3!} = 1680 .$

In the above analysis, we assume that the cardinality of each subset is fixed. Suppose instead that we are interested in counting the number of ways to pick the cardinality of the subsets that form the partition. Specifically, we wish to compute the number of ways integers $n_1, n_2, \ldots, n_r$ can be selected such that every integer is nonnegative and

$\sum_{p = 1}^r n_p = n$ .

We can visualize the number of possible assignments as follows. Picture n balls space out on a straight line and consider r-1 vertical markers, each of which can be put between two consecutive balls, before the first ball, or after the last ball. For instance, if there are five balls and two markers then one possible assignement is illustrated below.

The number of objects in the first subset corresponds to the number balls before the first marker. Similarly, the number of objects in the p-th subset is equal to the number of balls between the p-th marker and the preceding one. Finally, the number of objects in the last subset is simply the number of balls after the last marker. In the figure, the integer assignment is

$(n 1, n 2, n 3) = (0,2,3).$

Two consecutive markers imply that the corresponding subset is empty. There is a natural bijection between an integer assignment and the graphical representation depicted above. To count the number of possible integer assignments, it then suffices to compute the number of ways to position the markers and the balls. In particular, there are n + r - 1 positions, n balls, and r - 1 markers. The number of ways to assign the markers is equal to the number of n-combinations of n + r - 1 elements,

$\frac{(n + r - 1)!}{n!(r-1)!} .$

Example - Sampling with Replacement, without Ordering: An urn contains r balls numbered one through r. A ball is drawn from the urn and its number is recorded. The ball is then returned to the urn. This procedure is repeated a total of n times. The outcome of this experiment is a table that contains the number of times each ball has come in sight. We are interested in computing the number of distinct outcomes. This is equivalent to counting the ways a set with n elements can be partitioned into r subsets. The number of possible outcomes is therefore given by

$\frac{(n + r - 1)!}{n!(r-1)!} .$

Extracted from http://en.wikibooks.org/wiki/Probability. Reproduced under the GNU Free Documentation License

GMAT Tutorials