Partitions of a Set and Bell Numbers

Definition: Let S be a set. A partition of S is a collection of subsets of S, say S_1, S_2,\dots, S_n such that S=S_1\cup S_2 \cup \cdots \cup S_n and S_i \cap S_j=\emptyset whenever i\not=j for 1\leq i,j,\leq n.

In other words, any element of S is in exactly on of the subsets S_1, S_2,\dots, S_n.

Example: For any finite set X=\{1,\dots, n\}, we can always partition the set into singleton sets (1-sets or set with a single element), i.e. X=\{1\}\cup \{2\} \cup \cdots \cup \{n\}.

Example: Let X=\{1,\dots,30\} and
  1. [0] be the collection of integers in X of the form 3k.
  2. [1] be the collection of integers in X of the form 3k+1.
  3. [2] be the collection of integers in X of the form 3k+2.
You should convince yourself that this is a partition of X (this set is finite, so you may write out each set).
A special way of constructing partitions of sets is using equivalence relations.

Definition: Let \sim be a relation on a set X. An equivalence relation on X satisfies three conditions:
  1. Reflexive: For all x \in X, x\sim x.
  2. Symmetric: For all x,y \in X, if x\sim y, then y\sim x.
  3. Transitive: For all x,y,z \in X, if x\sim y and y\sim z, then x\sim z.
For each x\in X, the equivalence class containing x is the set [x]=\{y \in X\;:\; x\sim y\}.
Proposition: Let X be a set with an equivalence relation \sim. The set of equivalence classes defines a partition on X. Conversely, one can define an equivalence relation whose equivalence classes are the subsets in the partition.

Proof Let X be a set with an equivalence relation \sim.

(\Rightarrow): By \sim reflexive, each x\in X belongs to the subset [x]. Therefore, the union of equivalence classes is X. To show the equivalence classes are pairwise disjoint, we suppose that [x]\cap[y]\not=\emptyset, and show [x]=[y]. For if z \in [x]\cap[y], then x\sim z and y\sim z. By \sim symmetric, z\sim x. By \sim transitive, x \sim z and z \sim y implies x\sim y. Therefore, for any w \in [x], w\sim x and x \sim y implies y \in [y]. The reverse containment follows similarly.

(\Leftarrow): Suppose X has a partition into S_1, \dots, S_n. Define x\sim y if x and y both lie in S_i for some 1\leq i \leq n. Clearly, x\sim x since S_1, \dots, S_n is a partition and thus x is contained in some S_i. Let x \sim y, the x and y are contained in some S_i, so clearly, y and x are contained in S_i as well. Let x\sim y and y\sim z, then x and y are contained in some S_i and y and z are contained in some S_j. But y cannot be contained in two distinct sets S_i and S_j, thus i=j. Therefore, \sim is an equivalence relation.
Remark: For any partition of X, say X_1,X_2,\dots,X_n, we may define infinitely many partitions simply by tacking on copies of \emptyset to the list of subsets on the list. In the following exercises, we ignore this possibility.
In the following exercises, we compute the number of partitions of a set of size n for n=1,2,3,4. We say that the number of partitions of a set of size 0, i.e. \emptyset is 1 and clearly, the only partition of a set X=\{1\} is itself. As you complete these exercises, see if there are any patterns that you can use to help enumerate them.

Exercise 1: How many partitions of X=\{1,2\} exist?
Solution There are 2. The list is given as follows:
  1. \{1,2\}
  2. \{1\}\cup\{2\}

Exercise 2: How many partitions of X=\{1,2,3\} exist?
Solution There are 5. The list is given as follows:
  1. \{1,2,3\}
  2. \{1\}\cup\{2,3\}
  3. \{2\}\cup\{1,3\}
  4. \{3\}\cup\{1,2\}
  5. \{1\}\cup\{2\}\cup\{3\}

Exercise 3: How many partitions of X=\{1,2,3,4\} exist?
Solution There are 15. The list is given as follows:
  1. \{1,2,3,4\}
  2. \{1\}\cup\{2,3,4\}
  3. \{2\}\cup\{1,3,4\}
  4. \{3\}\cup\{1,2,4\}
  5. \{4\}\cup\{1,2,3\}
  6. \{1,2\}\cup\{3,4\}
  7. \{1,3\}\cup\{2,4\}
  8. \{1,4\}\cup\{2,3\}
  9. \{1\}\cup\{2\}\cup\{3,4\}
  10. \{1\}\cup\{3\}\cup\{2,4\}
  11. \{1\}\cup\{4\}\cup\{2,3\}
  12. \{2\}\cup\{3\}\cup\{1,4\}
  13. \{2\}\cup\{4\}\cup\{1,3\}
  14. \{3\}\cup\{4\}\cup\{1,2\}
  15. \{1\}\cup\{2\}\cup\{3\}\cup\{4\}
Definition: The number of partitions of a set with n elements is called the Bell number, often denoted B_n.

In the previous exercises, we have shown that B_0=1, B_1=1, B_2=2, B_3=5 and B_4=15.