背景：
现在给出一种关于分类的基本定义，即\(\require{AMSmath} \genfrac{\{}{\}}{0}{0}{n}{m}\)用于表征将一个具有n个元素的集合分割为m个非空且无交集的集合共具备的种类数
问题：
证明上述种类数与第二类斯特林数之间的等式关系。
解构：
根据第二类斯特林数的基本等式关系，有：
$$
\genfrac{\{}{\}}{0}{0}{n+1}{m}
= m\genfrac{\{}{\}}{0}{0}{n}{m}+
\genfrac{\{}{\}}{0}{0}{n-1}{m}
$$
基本思路：
将递推的通项公式抓住，再来探讨第二类斯特林数对此类分配方案数表征的准确性：
现在的目的是研究从n个元素的集合分出m个非空不相交的子集的总方案数是否为\(\genfrac{\{}{\}}{0}{0}{n}{m}\)？
取这n个元素中的n-1个构成一个集合，将其分为m个非空不相交的子集的总方案数为\(\genfrac{\{}{\}}{0}{0}{n-1}{m}\)。那么现在的问题转移至探讨剩余的一个元素的分配问题？
显然，剩余的那个元素可放置在这m个集合中的任意一个，所以存在的方案数为\(m\genfrac{\{}{\}}{0}{0}{n-1}{m}\)。
另一方面，上述探讨遗漏了一个方面：上述分配方式导致的一个结果是遗失了m个子集中存在空集，而最后一个元素又恰好放置在该空集中的情况！
而上述情况的方案数恰好为将n-1个元素分为m-1个非空不交叉的子集的种类数，即\(\genfrac{\{}{\}}{0}{0}{n-1}{m-1}\)
由此，我们间接完成了第二类斯特林数的基本加和公式的证明
$$
\genfrac{\{}{\}}{0}{0}{n}{m}
= m\genfrac{\{}{\}}{0}{0}{n-1}{m} +
\genfrac{\{}{\}}{0}{0}{n-1}{m-1}
$$
既然递推通项公式已被证明出，那么现在唯一剩下的需要做的是找到一个正确的出发点。
显然\(\genfrac{\{}{\}}{0}{0}{1}{1}
= 1\genfrac{\{}{\}}{0}{0}{-1}{1} +\genfrac{\{}{\}}{0}{0}{0}{0}=1\)
至此，我们完成了全部的论证工作！
发表评论