StatLect
Index > Mathematical tools

Partitions into groups

A partition of n objects into k groups is one of the possible ways of subdividing the n objects into k groups ($kleq n$). The rules are:

  1. the order in which objects are assigned to a group does not matter;

  2. each object can be assigned to only one group.

The following subsections give a slightly more formal definition of partition into groups and deal with the problem of counting the number of possible partitions into groups.

Table of Contents

Definition of partition into groups

Let a_1, a_2,..., a_n be n objects. Let $g_{1}$, $g_{2}$, ..., $g_{k}$ be k (with $kleq n$) groups to which we can assign the $n $ objects. $n_{1}$ objects can be assigned to group $g_{1}$, $n_{2}$ objects can be assigned to group $g_{2}$ and so on. $n_{1}$, $n_{2}$, ..., $n_{k} $ are such that:[eq1]A partition of a_1, a_2,..., a_n into the k groups $g_{1}$, $g_{2}$, ..., $g_{k}$ is one of the possible ways to assign the n objects to the k groups.

Example Consider three objects a_1, a_2 and $a_{3}$ and two groups $g_{1}$ and $g_{2}$, with[eq2] There are three possible partitions of the three objects into the two groups:[eq3]Note that the order of objects belonging to a group does not matter, so, for example, [eq4] in Partition 1 is the same as [eq5].

Counting the number of partitions into groups

Denote by [eq6] the number of possible partitions into the k groups (where group i contains $n_{i}$ objects). How much is [eq7] in general?

The number [eq8] can be derived with the following sequential procedure:

  1. First, we assign $n_{1}$ objects to the first group. There is a total of n objects to choose from. The number of possible ways to choose $n_{1}$ of the n objects is equal to the number of combinations of $n_{1}$ elements from n. So there are [eq9]

  2. Then, we assign $n_{2}$ objects to the second group. There were n objects, but $n_{1}$ have already been assigned to the first group. So, there are $n-n_{1}$ objects left, that can be assigned to the second group. The number of possible ways to choose $n_{2}$ of the remaining $n-n_{1}$ objects is equal to the number of combinations of $n_{2}$ elements from $n-n_{1}$. So there are [eq10]and[eq11]

  3. Then, we assign $n_{3}$ objects to the third group. There were n objects, but $n_{1}+n_{2}$ have already been assigned to the first two groups. So, there are $n-n_{1}-n_{2}$ objects left, that can be assigned to the third group. The number of possible ways to choose $n_{3}$ of the remaining $n-n_{1}-n_{2}$ objects is equal to the number of combinations of $n_{3}$ elements from $n-n_{1}-n_{2}$. So there are [eq12]and[eq13]

  4. An so on, until we are left with $n_{k}$ objects and the last group. There is only one way to form the last group, which can also be written as[eq14]Therefore, there are[eq15]

Therefore, by the above sequential argument, the total number of possible partitions into the k groups is[eq16]

The number [eq17] is often indicated as follows:[eq18]and [eq19] is called a multinomial coefficient.

Sometimes the following notation is also used:[eq20]

Example The number of possible partitions of $4$ objects into $2$ groups of $2$ objects is[eq21]

More details

The following sections contain more details about partitions.

Multinomial coefficients and multinomial expansions

The multinomial coefficient is so called because it appears in the multinomial expansion:[eq22]where $nin U{2115} $ and the summation is over all the k-tuples [eq23] such that:[eq24]

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

John has a basket of fruit containing one apple, one banana, one orange and one kiwi. He wants to give one fruit to each of his two little sisters and two fruits to his big brother. In how many different ways can he do this?

Solution

John needs to decide how to partition 4 objects into 3 groups, where the first two groups will contain one object and the third one will contain two objects. The total number of partitions is[eq25]

Exercise 2

Ten friends want to play basketball. They need to divide into two teams of five players. In how many different ways can they do this?

Solution

They need to decide how to partition 10 objects into 2 groups, where each group will contain 5 objects. The total number of partitions is[eq26]

The book

Most of the learning materials found on this website are now available in a traditional textbook format.