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.
Let , ,..., be objects. Let , , ..., be (with ) groups to which we can assign the objects. objects can be assigned to group , objects can be assigned to group and so on. , , ..., are such that:A partition of , ,..., into the groups , , ..., is one of the possible ways to assign the objects to the groups.
Example Consider three objects , and and two groups and , with There are three possible partitions of the three objects into the two groups:Note that the order of objects belonging to a group does not matter, so, for example, in Partition 1 is the same as .
Denote by the number of possible partitions into the groups (where group contains objects). How much is in general?
The number can be derived with the following sequential procedure:
First, we assign objects to the first group. There is a total of objects to choose from. The number of possible ways to choose of the objects is equal to the number of combinations of elements from . So there are
Then, we assign objects to the second group. There were objects, but have already been assigned to the first group. So, there are objects left, that can be assigned to the second group. The number of possible ways to choose of the remaining objects is equal to the number of combinations of elements from . So there are and
Then, we assign objects to the third group. There were objects, but have already been assigned to the first two groups. So, there are objects left, that can be assigned to the third group. The number of possible ways to choose of the remaining objects is equal to the number of combinations of elements from . So there are and
An so on, until we are left with 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
The following sections contain more details about partitions.
The multinomial coefficient is so called because it appears in the multinomial expansion:where and the summation is over all the -tuples such that:
Below you can find some exercises with explained solutions.
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?
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
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?
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
Most of the learning materials found on this website are now available in a traditional textbook format.