In simple terms, a partition of a set means dividing the set into smaller groups, called subsets, in such a way that each element of the original set belongs to one and only one group. No two groups share any elements, and when all the groups are combined, they include every element from the original set. So, the groups do not overlap, and together they completely cover the original set. This idea is used in both mathematics and logic to organize or classify elements in a clear and structured way without repeating or leaving anything out.

In this Maths article we will look at partition of a set definition, examples, theorems and solved examples in detail.

Partition of a set 

One way of counting the number of students in your class would be to count the number of students in each row and to add these totals. Of course this problem is simple because there are no duplications, no person is sitting in two different rows. 

The basic counting technique that you used involves an extremely important first step, namely that of partitioning a set. The concept of a partition must be clearly understood before we proceed further. A collection of n distinct subsets, \(P_{1},P_{2}.....P_{n} \) of a set S that satisfy the following three requirements is referred to as a partition of a set, S.

= The empty set does not exist in P_{i}

\(\left [ P_{i} 0< i \leq n \right ]\)

= The union of the subsets must equal the entire original set.

\(\left [ P_{1} \cup P_{2} \cup ..\cup P_{n} = S\right ]\)

Any two unique sets' intersection is empty.

\(P_{a}\cap P_{b} = \left \{ \phi \right \}\)

For \( a \neq b\)

Where , \(n\geq a,b\geq 0\)

Example:1

Let S = \(\left \{ a, b, c, d, e, f, g, h \right \}\)

One probable partitioning is \(\left \{ a \right \}, \left \{ b,c,d \right \}, \left \{ e,f,g,h \right \}\)

Another probable partitioning is \(\left \{ a, b\right \}, \left \{c,d \right \}, \left \{ e,f,g,h \right \}\)

Example: 2

Let S = \(\left \{ 1,2,3 \right \}, n = \left | S \right | = 3\)

These are substitute partitions:

\(\phi , \left \{ 1,2,3 \right \}\)

\(\left \{ 1 \right \}, \left \{ 2,3 \right \}\)

\(\left \{ 1,2 \right \}, \left \{3 \right \}\)

\(\left \{ 1,3 \right \}, \left \{2 \right \}\)

\(\left \{ 1 \right \}, \left \{2 \right \},\left \{ 3 \right \}\)

\(B_{3} = 5\)

A partition of a set S means breaking it into smaller groups, called subsets, in a way that follows a few simple rules:

1. Each group is not empty—every subset has at least one element.
2. No group shares elements with another—the subsets do not overlap.
3. All the groups together make up the original set—every element from S appears in one of the groups.
4. Each element of S belongs to exactly one group—no repeats or missing elements.

Partition of a Set Examples 

Examples of Partition of a set are given below:

Example: 1 

\((A = \left \{ a, b, c, d \right \})\) of A partitions include

\(\left \{ \left \{ a \right \},\left \{ b \right \},\left \{ c,d \right \} \right \}\)

\(\left \{ \left \{ a, b \right \},\left \{ c,d \right \} \right \}\)

\(\left \{ \left \{ a \right \},\left \{b\right \}, \left \{ c \right \},\left \{ d \right \}\right \}\)

Example: 2

Here are two examples of partitions of the set of integers Z.

\(\left \{ \left \{ n |n \epsilon \mathbb{Z} \right \} \right \}\)

\(\left \{ \left \{ n |n \epsilon \mathbb{Z} | n < 0\right \},\left \{ 0 \right \},\left \{ n\epsilon \mathbb{Z} | 0< n \right \} \right \}\)

Example: 3

List all partitions of the set \(A = \left \{ a,b,c \right \}\)

\(\left \{ \left \{ a \right \}, \left \{ b \right \},\left \{ c \right \} \right \}, \left \{ \left \{ a,b \right \} ,\left \{ c \right \}\right \}, \left \{ \left \{ a,c \right \},\left \{ b \right \} \right \}, \left \{ \left \{ a \right \},\left \{ b,c \right \} \right \}, \left \{ \left \{ a,b,c \right \} \right \}\)

Example: 4

One possible partition of \(\left \{ 1,2,3,4,5,6 \right \}\) is

\(\left \{ 1,3 \right \} , \left \{ 2 \right \} , \left \{ 4,5,6 \right \}\)

Generating all Partitions of a Set

Generating all partitions of a set is a combinatorial technique used to systematically enumerate and list all possible ways to divide a set into non-empty subsets. 

For Example: Consider the set {1, 2, 3}

• Start with the initial partition, which contains the set itself as a single subset.

{{1, 2, 3}}

• Identify the first element of the set and create new partitions by placing it in different subsets of the previous partition. Place 1 in a new subset: {{1}, {2, 3}} Place 1 with the subset containing 2: {{1, 2}, {3}}. Place 1 with the subset containing 3: {{1, 3}, {2}}
• Move to the next element (2) and repeat the process of creating new partitions by placing it in different subsets. Place 2 in a new subset: {{1}, {2}, {3}}. Place 2 with the subset containing 3: {{1}, {2, 3}}
• Move to the last element (3) and create a new partition by placing it in a new subset: {{1}, {2}, {3}}
• After exhausting all elements, the process is complete. The resulting partitions are:

{{1, 2, 3}}

{{1}, {2, 3}}

{{1, 2}, {3}}

{{1, 3}, {2}}

{{1}, {2}, {3}}

Remember, to find the different ways of dividing a set into non-empty subsets we generate all partitions of a set.

Partition of a Set with 4 Elements

Let’s see the partitions of a set with four elements with a general example. Take the set, {A, B, C, D}. The possible partitions of this set are:

{{A, B, C, D}}

{{A}, {B, C, D}}

{{A, B}, {C, D}}

{{A, C}, {B, D}}

{{A, D}, {B, C}}

{{A}, {B}, {C, D}}

{{A}, {B, C}, {D}}

{{A}, {B, D}, {C}}

{{A}, {B}, {C}, {D}}

Bell Numbers

Bell numbers provide the total number of possible partitions for a set. They are represented by the symbol \(B_{n}\), where n is the set's cardinality.

For example:

S = \( \left \{ 1,2,3 \right \},n = \left | S \right | \) = 3

Alternate partitions are 

\(\phi ,\left \{ 1,2,3 \right \}\)

\(\left \{ 1 \right \},\left \{2,3 \right \}\)

\(\left \{ 1,2 \right \},\left \{3 \right \}\)

\(\left \{ 1,3 \right \},\left \{2 \right \}\)

\(\left \{ 1\right \},\left \{2 \right \},\left \{ 3 \right \}\)

Partition of a Set Examples 

Examples of Partition of a set are given below:

Example: 1 

\((A = \left \{ a, b, c, d \right \})\) of A partitions include

\(\left \{ \left \{ a \right \},\left \{ b \right \},\left \{ c,d \right \} \right \}\)

\(\left \{ \left \{ a, b \right \},\left \{ c,d \right \} \right \}\)

\(\left \{ \left \{ a \right \},\left \{b\right \}, \left \{ c \right \},\left \{ d \right \}\right \}\)

Example: 2

Here are two examples of partitions of the set of integers Z.

\(\left \{ \left \{ n |n \epsilon \mathbb{Z} \right \} \right \}\)

\(\left \{ \left \{ n |n \epsilon \mathbb{Z} | n < 0\right \},\left \{ 0 \right \},\left \{ n\epsilon \mathbb{Z} | 0< n \right \} \right \}\)

Example: 3

List all partitions of the set \(A = \left \{ a,b,c \right \}\)

\(\left \{ \left \{ a \right \}, \left \{ b \right \},\left \{ c \right \} \right \}, \left \{ \left \{ a,b \right \} ,\left \{ c \right \}\right \}, \left \{ \left \{ a,c \right \},\left \{ b \right \} \right \}, \left \{ \left \{ a \right \},\left \{ b,c \right \} \right \}, \left \{ \left \{ a,b,c \right \} \right \}\)

Example: 4

One possible partition of \(\left \{ 1,2,3,4,5,6 \right \}\) is

\(\left \{ 1,3 \right \} , \left \{ 2 \right \} , \left \{ 4,5,6 \right \}\)

Partition of set Theorems

Theorems Partition of a set are given below:

Theorem: 1

In the event where A is a finite set and \(\left \{ A_{1},A_{2},.....A_{n} \right \}\) is a partition of A, then

\(\left | A \right | = \left | A_{1} \right | + \left | A_{2} \right |+....+\left | A_{n} \right | = \sum_{k = 1}^{n}\left | A_{k} \right |\)

Theorem: 2

Given finite sets \(A_{1}, A_{2},A_{3} \) then

The inclusion-exclusion law of the two sets:

\(\left | A_{1}\cup A_{2} \right | = \left | A_{1} \right | + \left | A_{2} \right | - \left | A_{1} \cap A_{2}\right |\)

The inclusion-exclusion law of the three sets:

\(\left | A_{1}\cup A_{2} \cup A_{3}\right | = \left | A_{1} \right | + \left | A_{2} \right | +\left | A_{3} \right | - \left ( \left | A_{1} \cap A_{2}\right | + \left | A_{1} \cap A_{3} + \left | A_{2} \cap A_{3} + \left | A_{1}\cap A_{2} \cap A_{3}\right |\right |\right |\right )\)

More than three sets are covered by the inclusion-exclusion laws.

Cross Partition of a Set

Cross partition of a set is an advanced combinatorial technique that involves partitioning a set into disjoint subsets, allowing for the inclusion of empty subsets.

Example: Consider the set {A, B, C}

• Start by listing all possible subsets of the set, including the empty subset:

{}

{A}

{B}

{C}

{A, B}

{A, C}

{B, C}

{A, B, C}

• These subsets represent the potential partitions of the set. Each subset can be considered as a distinct subset in the cross partition.
• Combine the subsets in different ways, ensuring that they remain disjoint. You can include any combination of the subsets, including the empty subset.
• Some possible cross partitions of the set {A, B, C} are:

{{}, {A, B, C}}

{{A}, {B, C}}

{{B}, {A, C}}

{{C}, {A, B}}

{{A, B}, {C}}

{{A, C}, {B}}

{{B, C}, {A}}

{{A, B, C}, {}}

Each cross partition represents a distinct way of dividing the set into disjoint subsets, considering the inclusion of empty subsets as well.

Summary

• The partition of a set. a group of unrelated subsets of a given set. The original set must be equal to the union of the subsets.
• Bell numbers provide the total number of possible partitions for a set. They are represented by the symbol \(B_{n}\), where n is the set's cardinality.

Solved Examples

Problem: 1

What is the set that is the partition of the sample space obtained by rolling a die

Solution:

We need to know the partition of the sample space S in order to answer this question.

If all of the sets in a collection are unrelated to one another and their union is S, the collection is said to be a partition of the set S.

Union gives sample space \(S = \left \{ 1,2,3,4,5,6 \right \}\)
All of them are disjoint

In \(\left \{ \left ( 1,2,3,4 \right ) , \left ( 5,6 \right )\right \}\), no elements are common and the union gives the sample space.

Problem: 2

Show that \(\left \{ \left \{ 2n|n\epsilon \mathbb{Z} \right \} ,\left \{ 2n + 1| n\epsilon \mathbb{Z} \right \}\right \}\) is a partition of \(\mathbb{Z}\). Describe this partition using only words.

Solution:

All the even numbers are in the first subset, and all the odd integers are in the second subset; these two sets do not intersect, therefore they comprise the entire set of integers.

Problem: 3

Let S = \(\left \{ 1,2,3 \right \}\) Write all the possible partitions of S

Solution:

A partition of S is a grouping of nonempty sets that are not connected to one another, and their union is S. For s, there are 5 possible partitions.

 S = \(\left \{ 1,2,3 \right \}\)

\(\left \{ 1 \right \} , \left \{ 2 \right \} , \left \{ 3 \right \}\)

\(\left \{ 1,2 \right \} , \left \{ 3 \right \}\)

\(\left \{ 1,3 \right \} , \left \{ 2 \right \}\)

\(\left \{ 2,3 \right \} , \left \{ 1 \right \}\)

\(\left \{ 1,2,3 \right \}\)

If you want to score well in your math exam then you are at the right place. Here you will get weekly test preparation, live classes, and exam series. Download the Testbook App now to prepare a smart and high-ranking strategy for the exam