Partitions into groups

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

the order in which objects are assigned to a group does not matter;
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
Counting the number of partitions into groups
More details
1. Multinomial coefficients and multinomial expansions
Solved exercises
1. Exercise 1
2. Exercise 2

Definition of partition into groups

Let , ,..., be objects. Let $g_{1}$ , $g_{2}$ , ..., $g_{k}$ be (with ) groups to which we can assign the 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:A partition of , ,..., into the groups $g_{1}$ , $g_{2}$ , ..., $g_{k}$ is one of the possible ways to assign the objects to the groups.

Example Consider three objects , 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, in Partition 1 is the same as .

Counting the number of partitions into groups

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

The number can be derived with the following sequential procedure:

First, we assign $n_{1}$ objects to the first group. There is a total of objects to choose from. The number of possible ways to choose $n_{1}$ of the objects is equal to the number of combinations of $n_{1}$ elements from . So there are
Then, we assign $n_{2}$ objects to the second group. There were 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 and
Then, we assign $n_{3}$ objects to the third group. There were 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 and
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 asTherefore, there are

Therefore, by the above sequential argument, the total number of possible partitions into the groups is

The number is often indicated as follows:and is called a multinomial coefficient.

Sometimes the following notation is also used:

Example The number of possible partitions of objects into groups of 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:where and the summation is over all the -tuples such that:

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]

How to cite

Please cite as:

Taboga, Marco (2021). "Partitions into groups", Lectures on probability theory and mathematical statistics. Kindle Direct Publishing. Online appendix. https://www.statlect.com/mathematical-tools/partitions.