Discrete Mathematics: Partitions

Partitions

1. How many ways are there to partition a set $S$ with $N$ elements into 2 nonempty subsets $S_1$ and $S_2$ such that $S_1 \cup S_2 = S$?



Example. $N=5$



\[ \boxed{S(N,2) = 2^{N-1} - 1} \]

2. How many ways are there to partition a set $S$ with $N$ elements into $2$ nonempty subsets $S_1$ and $S_2$ such that $S_1 \cup S_2 = S$ and neither subset is allowed to be a singleton?



Example. $N=5$



\[ \boxed{2^{N-1} - N - 1} \]

3. How many ways are there to partition a set $S$ with $N$ elements into 3 nonempty subsets $S_1, S_2,$ and $S_3$ such that $S_1 \cup S_2 \cup S_3 = S$? Hint: Use the Inclusion-Exclusion Principle


$$ \left| \bigcap_{i=0}^{K} A_i^c \right| = |T| - \sum_{i=0}^{K} |A_i| $$ $$ + \sum_{0 \le i_1 < i_2 \le K} |A_{i_1} \cap A_{i_2}| - \ldots $$ $$ + (-1)^{K} \sum_{0 \le i_1 < \ldots < i_{K} \le K} \left| A_{i_1} \cap \cdots \cap A_{i_{K}} \right| $$


where \(T\) is the set of all ways of assigning each element of the \(N\)-element set to one of the subsets \(S_1,S_2,\) or \(S_3\), and \(A_i\) is the set of assignments in which the \(i\)-th subset is empty.




Example. $N=5$



\[ \boxed{S(N,3) = \frac{3^N - 3\cdot 2^N + 3}{6}} \]

4. How many ways are there to partition a set $S$ with $N$ elements into $K$ nonempty subsets $S_1, S_2, \ldots, S_K$ such that $S_1 \cup S_2 \cup \cdots \cup S_K = S$? Hint: Use the Inclusion-Exclusion Principle


$$ \left| \bigcap_{i=1}^{K} A_i^c \right| = |T| - \sum_{i=1}^{K} |A_i| $$ $$ + \sum_{1 \le i_1 < i_2 \le K} |A_{i_1} \cap A_{i_2}| - \ldots $$ $$ + (-1)^{K} \sum_{1 \le i_1 < \ldots < i_{K} \le K} \left| A_{i_1} \cap \cdots \cap A_{i_{K}} \right| $$


where \(T\) is the set of all ways of assigning each element of the \(N\)-element set to one of the subsets \(S_1,S_2,\dots,S_K\), and \(A_i\) is the set of assignments in which the \(i\)-th subset is empty.




Example. $N=5, K=4$



\[ \boxed{ S(N,K) = \frac{1}{K!} \left( \sum_{j=0}^{K} (-1)^j \binom{K}{j}(K-j)^N \right) } \]


\(N \backslash K\)	\(0\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)
\(0\)	\(1\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)
\(1\)	\(0\)	\(1\)	\(0\)	\(0\)	\(0\)	\(0\)
\(2\)	\(0\)	\(1\)	\(1\)	\(0\)	\(0\)	\(0\)
\(3\)	\(0\)	\(1\)	\(3\)	\(1\)	\(0\)	\(0\)
\(4\)	\(0\)	\(1\)	\(7\)	\(6\)	\(1\)	\(0\)
\(5\)	\(0\)	\(1\)	\(15\)	\(25\)	\(10\)	\(1\)
\(6\)	\(0\)	\(1\)	\(31\)	\(90\)	\(65\)	\(15\)




5. How many ways are there to partition a set $S$ with $N$ elements into nonempty subsets $S_1, S_2, \ldots, S_m$ such that $S_1 \cup S_2 \cup \cdots \cup S_K = S$, where $K$ is not fixed?



Example. $N=5$



$$ \boxed{ B_N = \sum_{k=0}^{N} S(N,k) } $$


\(N\)	\(0\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)
\(B_N\)	\(1\)	\(1\)	\(2\)	\(5\)	\(15\)	\(52\)	\(203\)	\(877\)	\(4140\)



6. How many ways are there to partition a set $S$ with $N$ elements into $K$ nonempty subsets $S_1, S_2, \ldots, S_K$ such that each subset $S_i$ consists of elements that are consecutive when ordered? Hint: Consider the gaps between the elements.



Example. $N=5, K=3$



$$ \boxed{\binom{N-1}{K-1}} $$

7. How many ways are there to partition a set $S$ with $N$ elements into $K$ nonempty subsets $S_1, S_2, \ldots, S_K$ such that two fixed elements $A$ and $B$ lie in different subsets?



Example. $N=5, K=3$



$$ \boxed{ S(N,K) - S(N-1,K) } $$

8. How many ways are there to partition a set $S$ with $JK$ elements into $K$ nonempty subsets $S_1, S_2, \dots, S_K$ such that all subsets have equal size?



Example. $N=6, K=3$



\[ \boxed{ \frac{1}{K!} \binom{JK}{J} \binom{JK-J}{J} \binom{JK-2J}{J} \cdots \binom{2J}{J} \binom{J}{J} = \frac{(JK)!}{(J!)^K\,K!} } \]