Search
STATLECT > 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.

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

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:

  1. Exercise set 1 (combinatorial problems involving partitions)

by
About | Contacts | Privacy and terms of use | Sitemap