组合数学常用公式汇总 - 已更新
- 小白整理,有误请大佬斧正
排列组合
排列
-
无其他限制下,从n个物体种选择r个出来的所有排列情况为\(A(^r_n)=\frac{n!}{(n-r)!}\) r>n时\(A(^r_n)=0\)
-
从n个物体种选择r个的圆排列为\(P(^r_n)=\frac{A(^r_n)}{r}\)
多重集的排列
-
设n种元素每种互不相同,每种元素都有\(\infty\)种(无限多重集),在这n种中取r个的排列为\(n^r\)
-
设n种元素每种互不相同,每种元素都有\(a_1,a_2,a_3...a_n\)种(有限多重集),在这n种中取r个,当\(min({a_1,a_2,...a_n})>=r\)时,排列数依然为\(n^r\)
-
设n种元素每种互不相同,每种元素都有\(a_1,a_2,a_3...a_n\)种(有限多重集),其全排列为\(\frac{(a_1+a_2+a_3+...+a_n)!}{{a_1}!{a_2}!...{a_n}!}\)
-
设n种元素每种互不相同,每种元素都有\(a_1,a_2,a_3...a_n\)种(有限多重集),在这n种中取r个,当\(min({a_1,a_2,...a_n})<r\)时,排列为\(\sum_{k_1+k_2+...+k_n=r}\frac{r!}{{k_1}!{k_2}!...{k_n}!}\)
组合
- 无限制下,从n个物体选择r个物体的组合为\(C(n,r)=\frac{n!}{r!(n-r)!}\), 亦写作\((^n_r)=\frac{n!}{r!(n-r)!}\), r>n时,\(C(n,r)=0\)
多重集的组合
-
设n种元素每种互不相同,每种元素都有\(\infty\)种(无限多重集),在这n种中取r个的组合为\((^{n+r-1}_{r})=(^{n+r-1}_{n-1})\)
-
设n种元素每种互不相同,每种元素都有\(a_1,a_2,a_3...a_n\)种(有限多重集),在这n种中取r个,当\(min({a_1,a_2,...a_n})>=r\)时,组合数为\((^{n+r-1}_{r})=(^{n+r-1}_{n-1})\)
-
设n种元素每种互不相同,每种元素都有\(a_1,a_2,a_3...a_n\)种(有限多重集),在这n种中取r个,当\(min({a_1,a_2,...a_n})<r\)时,组合为$$
组合数公式
- \(C(_n^k)=C(n-1,k)+C(n-1,k-1)\),杨辉恒等式
- \(C(_n^k)=C(n,n-k)\),对称性
- \(\sum_{i=0}^nC(n,i)=2^n\),单行和
- \(\sum_{i=0}^nC(n,i)^2=C(2n,n)\),单行平方和
- \(\sum_{i=0}^nC(_{k+i}^k)=C(_{n+k+1}^{k+1})\),斜\(60^\circ\)行和=反斜下一行对应值
- \(f(n)=\begin{cases} \sum_{i=0}^{n/2-1}C(n/2+i,2i+1)& \text n\equiv 0 \bmod 2\\ \sum_{i=0}^{(n-1)/2}C\bigg((n-1)/2+i,2i\bigg)& \text n\equiv 1 \bmod 2 \end{cases}\) , \(\big(30^\circ\)斜行和等于Fibonacci数列\(\big)\)
- \(C(n,i)=\frac{n-i+1}{i}C(n,i-1)\), 递推式
- \(C(n,m)\)的奇偶性:n&m=m为奇,否则为偶(lucas定理推论)
二项式定理
- \((a+b)^n=\sum_0^nC(_n^i)a^ib^{n-i}\)
鸽巢原理
- n+1只鸽子飞向n个鸽巢,一定存在两只鸽子飞向了同一个鸽巢
容斥原理
-
容斥原理的题常考虑反面
错排问题
- \(D_n=n!\big(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n\frac{1}{n!}\)
- 递推式推导
考虑在\(D_{n-1}\)中加入n来生成n个数的错排,数n可以与前面n-1个数任一交换即可,贡献为\((n-1)D_{n-1}\)
考虑在有1..n-1的一个序列,我们直接加入n来生成n的错排,可以在n-1个数任选一个数与n交换位置,然后剩下的n-2个数进行错排,这样就生成了n的错排,贡献为\((n-1)D_{n-2}\)
因此最终的递推式就是\(D_n=(n-1)(D_{n-1}+D_{n-2})\)
\(D_1=0,D_2=1,D_3=2,D_4=9...\)
- \(D_n=nD_{n-1}+(-1)^n\)
特殊计数序列
Fibonacci序列
- \(f_n=f_{n-1}+f_{n-2},n\geq3,f_1=f_2=1\)
- \(f_n=\frac{1}{\sqrt{5}}\big[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n\big]\)
- \(f_n\equiv 276601065(691504013^n-308495997^n)\bmod 10^9+9\),注意仅限模1e9+9的情况下。
- \(\sum_{i=1}^nf_i=f_{n+2}-1\),前缀和公式
- \(f_1+f_3+...+f_{2n-1}=f_{2n}\),奇数项前缀和公式
- \(f_2+f_4+..+f_{2n}=f_{2n+1}\),偶数项前缀和公式
- \(\sum_{i=1}^nf_i^2=f_nf_{n+1}\),平方和公式
- \(f_n^2=(-1)^{n+1}+f_{n-1}f_{n+1}\)
- \(f_{2n}=f_n(f_{n+1}+f_{n-1})\)
- \(f_n \equiv 0\bmod p\Rightarrow f_{nk} \equiv 0 \bmod p,\mbox{k为正整数}\)
- \(gcd(f_n, f_m) = f_{gcd(n, m)}\),
- 对于质数P, f[n] % P 有循环节, 如果5是模P的二次剩余,则循环节长度是P - 1的因子, 否则是2(P + 1)的因子; 类Fibonacci也类似。
- \(f_n=\sum_{i=0}^mC(n-1-i,i),m \leq n-1-m\),杨辉三角斜\(30^\circ\)度求和
catalan数
- \(C_n=\sum_{k=0}^{n-1}C_nC_{n-k-1},n \geq 2,C_0=C_1=1\)
- \(C_0=1,C_1=1,C_2=2,C_3=5,C_4=14,C_5=42,C_6=132,C_7=429,C_8=1430,C_9=4852\)...
- \(C_n=\frac{C(2n,n)}{n+1}=C(2n,n)-C(2n,n-1)\),注意组合数区分卡特兰数
- \(C_n=\frac{4n-2}{n+1}C_{n-1}\)
用于栈进出序列,二叉树的种类枚举、多边形分成三角形的个数、圆括弧插入公式中的方法数。。。
Stirling数
\(Stirling估计式:n!\sim\sqrt{2\pi n}{(\frac{n}{e})}^n\)
第一类Stirling数
- 正负,其绝对值的实际意义为n个元素的集合组成m个的圆排列的数目,\((n\geq m)\)
- 递推式:\(S_u(n,m)=S_u(n-1,m)+(n-1)S_u(n-1,m-1)\)
- 边界以及结论
\(S_u(0,0)=1\\S_u(n,0)=0\\S_u(n,1)=1\\S_u(n,n)=1\\S_u(n,n-1)=C(n,2)\\S_u(n,n-2)=2C(n,3)+3C(n,4)\\\sum_{i=0}^nS(n,i)=n!\)
第二类Stirling数
- n个元素组成拆成m个非空集合的方案数
- 递推式:\(S_2(n,m)=S_2(n-1,m-1)+mS_2(n-1,m)\)
- 边界以及结论
\(S_2(n,0)=0^n\\S_2(n,1)=1\\S_2(n,n)=1\\S_2(n,2)=2^{n-1}-1\\S_2(n,n-1)=C(n,2)\\S_2(n,n-2=C(n,3)+3C(n,4))\)
拆分数
- 整数n拆成r个正整数之和为n的r拆分数,记作\(P_r(n)\)
- \(P_1(n)=1,P_n(n)=1,P_{n-1}(n)=1,P_{n-2}(n)=2,P_{n-3}(n)=3\)
- \(P_2(n)=\big\lceil{\frac{n-1}{2}}\big\rceil,n \geq 2\)
- \(P_r(n)=\sum_{i=1}^r P_i(n-r)\)
装箱问题
- n个球放入r个盒子成为装箱问题
- 相同球n和相同盒子r,\(n \geq r\)
无空盒子 \(P_r(n)\)
可以有空盒子 \(\sum_{i=1}^rP_i(n)\)
- 相同球不同盒子
无空盒子 \(C(n-1,r-1)\)
可以有空盒子 \(C(n+r-1,r-1)\)
- 不同球相同盒子
无空盒子 \(S_2(n,r)\)
可以有空盒 \(\sum_{i=1}^rS_2(n,i)\)
- 不同球不同盒子
无空盒子 \(r!S_2(n,r)\)
可以有空盒子 \(r^n\)
生成函数
- \((1-x)^{-m}=\sum_0^\infty{x^i(^{m+i-1}_{m-1})}\)
burnside引理&polya定理
- 两者都是解决考虑旋转或是翻转等计数问题的理论
- burnside引理
设\(G={a_1,a_2,…a_g}\)是目标集\([1,n]\)上的置换群。每个置换都写成不相交循环的乘积。 是在置换\(a_k\)的作用下不动点的个数,也就是长度为1的循环的个数。通过上述置换的变换操作后可以相等的元素属于同一个等价类。若\(G\)将\([1,n]\)划分成\(l\)个等价类,则:
\[l=\frac{1}{\overline{|G|}}\sum_{i=1}^gc_1(a_i) \]\(\mbox{其中}c_1(a_i)\mbox{代表}a_i\mbox{中包含的一阶循环(不动点)的个数}\)
- polya定理
设\(G\)是n个对象的一个置换群, 用m种颜色染图这n个对象,则不同的染色方案数为:
\[\frac{1}{\overline{|G|}}\sum_{i=1}^gm^{c(\overline{p_i})}$$, 其中$G=\{\overline{p_1},\overline{p_2},...\overline{p_g}\}, c(\overline{p_i})\mbox{表示}\overline{p_i}\mbox{的循环节数(阶)}$\]
上一篇: 解组合数 C(n,m) 的四种方法
下一篇: 求组合数、求逆元素、求阶乘 O(n)
推荐阅读
-
NeurIPS 2022 | 最强斗地主AI!网易互娱AI Lab提出基于完美信息蒸馏的方法-完美信息蒸馏(PTIE) 在斗地主游戏中,非完美信息的引入主要是由于三位玩家均不能看到别人的手牌,对于任意一位玩家而言,仅可知道其余两位玩家当前手牌的并集,而难于精准判断每位玩家当前手牌。完美信息蒸馏的思路是针对这种非完美问题,构建一个第三方角色,该角色可以看到三位玩家的手牌,该角色在不告知每位玩家完美信息的情况下通过信息蒸馏的方式引导玩家打出当前情况下合理的出牌。 以强化学习常用的 Actor-Critic 算法为例,PTIE 在 Actor-Critic 算法的应用中可以利用 Critic 的 Value 输出作为蒸馏手段来提升 Actor 的表现。具体而言即在训练中 Critic 的输入为完美信息(包含所有玩家的手牌信息),Actor 的输入为非完美信息(仅包含自己手牌信息),此种情况下 Critic 给予的 Value 值包含了完美信息,可以更好地帮助 Actor 学习到更好的策略。 从更新公式上来看,正常的 Actor-Critic 算法 Actor 更新的方式如下: 在 PTIE 模式下,对于每个非完美信息状态 h,我们可以在 Critic 中构建对应的完美信息状态 D(h),并用 Critic 的输出来更新 Actor 的策略梯度,从而达到完美信息蒸馏的效果。 PTIE 框架的整体结构如下图所示: 无论是训练还是执行过程中智能体都不会直接使用完美信息,在训练中通过蒸馏将完美信息用于提升策略,从而帮助智能体达到一个更高的强度。 PTIE 的另一种蒸馏方式是将完美信息奖励引入到奖励值函数的训练中,PerfectDou 提出了基于阵营设计的完美信息奖励 node reward,以引导智能体学习到斗地主游戏中的合作策略,其定义如下: 如上所示,完美信息部分 代表 t 时刻地主手牌最少几步可以出完,在斗地主游戏中可以近似理解为是距游戏获胜的距离, 代表 t 时刻地主阵营和农民阵营距游戏获胜的距离之差, 为调节系数。通过此种奖励设计,在训练时既可以一定程度地引入各玩家的手牌信息(出完的步数需要知道具体手牌才能计算),同时也鼓励农民以阵营的角度做出决策,提升农民的合作性。 特征构建: PerfectDou 针对牌类游戏的特点主要构建了两部分特征:牌局状态特征和动作特征。其中牌局状态特征主要包括当前玩家手牌牌型特征、当前玩家打出的卡牌牌型特征、玩家角色、玩家手牌数目等常用特征,动作特征主要用于刻画当前状态下玩家的所有可能出牌,包括了每种出牌动作的牌型特征、动作的卡牌数目、是否为最大动作等特征。 牌型特征为 12 * 15 的矩阵,如下图所示: 该矩阵前 4 行代表对应每种卡牌的张数,5-12 行代表该种卡牌的种类和对应位置。 网络结构和动作空间设计 针对斗地主游戏出牌组合数较多的问题,PerfectDou 基于 RLCard 的工作上对动作空间进行了简化,对占比最大的两个出牌牌型:飞机带翅膀和四带二进行了动作压缩,将整体动作空间由 27472 种缩减到 621 种。 PerfectDou 策略网络结构如下图所示: 策略网络结构同样分为两部分:状态特征部分和动作特征部分。 在状态特征部分,LSTM 网络用于提取玩家的历史行为特征,当前牌局状态特征和提取后的行为特征会再通过多层的 MLP 网络输出当前的状态信息 embedding。 在动作特征部分,每个可行动作同样会经过多层 MLP 网络进行编码,编码后的动作特征会与其对应的状态信息 embedding 经过一层 MLP 网络计算两者间的相似度,并经由 softmax 函数输出对应的动作概率。 实验结果
-
组合数学常用公式汇总 - 已更新