集合的划分个数的讨论.md
给定$n(n\ge1)$元集合$A$，若能求出$A$的全部划分，也就求出了$A$上的所有等价关系，要求出$A$的全部划分，可以建立下面的数学模型
将$n$个不同的球放入$r$个相同的盒中去，并且要求无空盒，问有多少种不同的放法？这里要求$n\ge r$
不同的放球放法数为$n$元集$A$的不同的划分数，要求不同的放球放法数，需要靠组合数学中的第二类斯特林(Stirling)数
设$\begin{Bmatrix}n\\r\end{Bmatrix}$表示将$n$个不同的球放入$r$个相同的盒中的方案数，称$\begin{Bmatrix}n\\r\end{Bmatrix}$为第二类斯特林数，它有下面的性质
- $\begin{Bmatrix}n\\0\end{Bmatrix}=0,\begin{Bmatrix}n\\1\end{Bmatrix}=1,\begin{Bmatrix}n\\2\end{Bmatrix}=2^{n-1}-1,\begin{Bmatrix}n\\n-1\end{Bmatrix}=C_n^2,\begin{Bmatrix}n\\n\end{Bmatrix}=1$
- 满足如下的递推公式
上述递推公式可以理解为“将$n$个小球放入$r$个相同的盒中”等于“将$n-1$个小球放入$r-1$个相同的盒中，并将第$n$个小球放入第$r$个盒中”或者“将$n-1$个小球放入$r$个相同的盒中，并将第$n$个小球任取$r$个盒子中的一个放入”
于是，$n$元集合的总划分数为
$$ \sum_{i=1}^n{\begin{Bmatrix}n\\i\end{Bmatrix}} $$