Counting Set Partitions
Lesson · Intermediate
Combinatorics
A set partition divides a set of distinct elements into nonempty, disjoint groups whose union is the entire set.
For example, the number of ways to divide people as shown is
When partitioning a set into groups of specified sizes:
• All group sizes are different: simply choose the elements of each group. No additional division is needed because each group is identified by its size.
• Some group sizes are equal: divide by the factorial of the number of groups of each repeated size.
There are 4 students, a, b, c, d. Find the number of ways to split them into two groups in each of the following cases.
a) One group has 1 member and the other has 3 members
The four possibilities are
b) Each group has 2 members
Incorrect:
We need to divide by 2! because the order of the two groups does not matter.
Therefore, the correct answer is
Suppose 13 people are divided into groups of sizes:
We could first choose the groups:
But the three groups of size 2 are indistinguishable, so divide by
The two groups of size 3 are also indistinguishable, so divide by
Thus,
Ten people are divided into five pairs. Alice and Bob cannot be in the same pair. How many pairings are possible?
The total number of pairings is
If Alice and Bob are paired together, the remaining 8 people can be paired in
ways.
Therefore,
Twelve people are divided into three unlabeled groups of 4. Alice and Bob must be in the same group. How many partitions are possible?
Choose the other two members of Alice and Bob's group:
The remaining 8 people must be divided into two groups of 4:
Therefore,
Suppose n distinct objects are partitioned into groups with sizes
Suppose among these sizes:
• one size occurs m₁ times
• another size occurs m₂ times
• and so on
Then the number of partitions is