第二类Stirling数对有限集合的覆盖近似计数的应用

在近似算法领域,集合覆盖计数是研究的比较早和比较透彻的问题之一。文中结合第二类Stirling数,提出了一种构造有限集合上的集合覆盖的算法,并且讨论了它的正确性。该算法简单有效,可以在有限的计算资源下求得一个有限集合的覆盖计数的下界。

有限集合上的划分与覆盖

关于有限集合上的划分与覆盖,一般很少讨论和研究。本文根据集合的划分与覆盖的定义,利用容斥定理和集合理论,给出了有限集合上的划分与等价关系、完全覆盖与相容关系的关系,以及有限集合上的划分数和完全覆盖数的计算公式。