@@基础概念 ：容斥原理又称排容原理，在组合数学里，其说明若 A1...An 为有限的集合 ，则如下图 ，其中 |A| 表示 A 的基数（一个集合元素的个数）。例如在两个集合的情况时，我们可以将 |A| 和 |B| 相加 ，再减去其交集的基数 ，而得到其并集的基数。 摘自维基百科
：有 n 个球排成一行，你有 k 种颜色 ，要求给每一个球染色 ，相邻两个球颜色不可以相同，并且每种颜色至少使用一次 。
:和错排列问题相同 ，假设没有限制每种颜色至少使用一次 ，那么问题就很简单，答案就是 k(k-1)^n-1 。这些方案是由 恰好 使用了 i(i=0,1,2,?,k) 种颜色的方案组成的 ，那么设 fi 为恰好使用了 i 种颜色的方案数 ，可以得到
@@经典应用之斯特林数
:第一类Stirling数是 分正负 的，其绝对值是 n 个元素的项目分作 k 个环排列。常用的表示方法有 s(n,k) 等 。
换一个比较生活化的说法，就是有 n 个人分为 k 组 ，每组内再按照特定的顺序围圈的分组方法的数目 。例如 s(4,2) = 11 :
{A,B},{C,D}
{A,C},{B,D}
{A,D},{B,C}
{A},{B,C,D}
{A},{B,D,C}
{B},{A,C,D}
{B},{A,D,C}
{C},{A,B,D}
{C},{A,D,B}
{D},{A,B,C}
{D},{A,C,B}
给定 S(n,0)=1, S(1,1)=1 ，有 S(n,k) = S(n-1,k-1) + (n-1)S(n-1,k)
递推关系的说明 ：考虑第 n 个物品， n 可以单独构成一个非空循环排列 ，这样前 n-1 种物品构成 k-1 个非空循环排列 ，有 S(n-1,k-1) 中方法；也可以前 n-1 种物品构成 k 个非空循环排列，而第 n 个物品插入第 i 个物品的左边 ，这有 (n-1)S(n-1,k) 种方法。
哈密尔顿数学原理是图论中的一个重要概念 ，它是指一个图中存在一条经过每个顶点一次且仅一次的路径，这个路径称为哈密尔顿回路 。哈密尔顿图是指存在哈密尔顿回路的图 。哈密尔顿通路是指经过图中每个结点且仅经过一次的通路。半哈密尔顿图是指有哈密尔顿路径而没有哈密尔顿回路的图 。
在图论中 ，哈密尔顿数学原理对遍历问题有着重要贡献 。例如 ，欧拉遍历、强连通分量等都与哈密尔顿回路有关。
本文来自作者[谊疤距]投稿，不代表书宁号立场，如若转载，请注明出处：https://3g.shuningedu.com.cn/diyi/168.html
评论列表（3条）
我是书宁号的签约作者“谊疤距”
本文概览：@@基础概念 ：容斥原理又称排容原理，在组合数学里，其说明若 A1...An 为有限的集合 ，则如下图 ，其中 |A| 表示...
文章不错《组合数学、容斥原理》内容很有帮助