这个页面大量使用了 OI Wiki：组合数学(OI Wiki 镜像：组合数学) 中的内容。
做一件事，第一类做法有 x 种，第二类做法有 y 种，一共有 x+y 种做法。
做一件事分两步，第一步做法有 x 种，第二步做法有 y 种，做完第一步之后才能做第二步，做完两步一共有 x×y 种做法。
从 n 个不同元素中，任取 m（m≤n，m 与 n 均为自然数，下同）个元素按照一定的顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列；
从 n 个不同元素中取出 m(m≤n) 个元素的所有排列的个数，叫做从 n 个不同元素中取出 m 个元素的排列数，用符号 Anm（或者是 Pnm）表示。
排列的计算公式如下：
Anm=n(n−1)(n−2)⋯(n−m+1)=(n−m)!n!
n! 代表 n 的阶乘，即 6!=1×2×3×4×5×6。
公式可以这样理解：n 个人选 m 个来排队 (m≤n)。第一个位置可以选 n 个，第二位置可以选 n−1 个，以此类推，第 m 个（最后一个）可以选 n−m+1 个，得：
Anm=n(n−1)(n−2)⋯(n−m+1)=(n−m)!n!
全排列：n 个人全部来排队，队长为 n。第一个位置可以选 n 个，第二位置可以选 n−1 个，以此类推得：
Ann=n(n−1)(n−2)⋯3×2×1=n!
全排列是排列数的一个特殊情况。
从 n 个不同元素中，取出 m(m≤n) 个元素有很多种取法。这些取法的数量，叫做从 n 个不同元素中取出 m 个元素的组合数。用符号 Cnm 来表示。
组合数计算公式
Cnm=m!Anm=m!(n−m)!n!
如何理解上述公式？我们考虑先从 n 个人中选择 m(m≤n) 个出来排成一列，排列的数量是 Anm。
这些排列中，如果把人员构成相同的排列分为一组，显然每组里有 Amm 个排列，一共有 m!Anm 组，即 Cnm 组。
组合数也常用 (mn) 表示，读作「n 选 m」，即 Cnm=(mn)。实际上，后者表意清晰明了，美观简洁，因此现在数学界普遍采用 (mn) 的记号而非 Cnm。
Cnm=Cn−1m−1+Cn−1m
考虑选择的 m 个人中，是否包括了 1 号：
- 如果包括了 1 号，则还需要在剩下的 (n−1) 个人中选择 (m−1) 个人，一共有 Cn−1m−1 种方案。
- 如果没包括 1 号，则还需要在剩下的 (n−1) 个人中选择 (m) 个人，一共有 Cn−1m 种方案。
两类情况，按加法原理加在一起即可得到 Cnm。
|
11 11 2 11 3 3 11 4 6 4 1 |
C00C10 C11C20 C21 C22C30 C31 C32 C33C40 C41 C42 C43 C44 |
(a+b)n=i=0∑n(in)an−ibi
请大家一定要区分 多重组合数 与 多重集的组合数！两者是完全不同的概念！
多重集是指包含重复元素的广义集合。设 S={n1⋅a1,n2⋅a2,⋯,nk⋅ak} 表示由 n1 个 a1，n2 个 a2，…，nk 个 ak 组成的多重集，S 的全排列个数为
∏i=1kni!n!=n1!n2!⋯nk!n!
相当于把相同元素的排列数除掉了。具体地，你可以认为你有 k 种不一样的球，每种球的个数分别是 n1,n2,⋯,nk，且 n=n1+n2+…+nk。这 n 个球的全排列数就是 多重集的排列数。
多重集的排列数常被称作 多重组合数。我们可以用多重组合数的符号表示上式：
(n1,n2,⋯,nkn)=∏i=1kni!n!
可以看出，(mn) 等价于 (m,n−mn)，只不过后者较为繁琐，因而不采用。
设 S={n1⋅a1,n2⋅a2,⋯,nk⋅ak} 表示由 n1 个 a1，n2 个 a2，…，nk 个 ak 组成的多重集。那么对于整数 r(r<ni,∀i∈[1,k])，从 S 中选择 r 个元素组成一个多重集的方案数就是 多重集的组合数。这个问题等价于 x1+x2+⋯+xk=r 的非负整数解的数目，可以用插板法解决，答案为
(k−1r+k−1)
考虑这个问题：设 S={n1⋅a1,n2⋅a2,⋯,nk⋅ak,} 表示由 n1 个 a1，n2 个 a2，…，nk 个 ak 组成的多重集。那么对于正整数 r，从 S 中选择 r 个元素组成一个多重集的方案数。
这样就限制了每种元素的取的个数。同样的，我们可以把这个问题转化为带限制的线性方程求解：
∀i∈[1,k], xi≤ni, i=1∑kxi=r
于是很自然地想到了容斥原理。容斥的模型如下：
- 全集：i=1∑kxi=r 的非负整数解。
- 属性：xi≤ni。
于是设满足属性 i 的集合是 Si，Si 表示不满足属性 i 的集合，即满足 xi≥ni+1 的集合（转化为上面插板法的问题三）。那么答案即为
∣∣∣∣∣∣i=1⋂kSi∣∣∣∣∣∣=∣U∣−∣∣∣∣∣∣i=1⋃kSi∣∣∣∣∣∣
根据容斥原理，有：
∣∣∣∣∣∣i=1⋃kSi∣∣∣∣∣∣==i∑∣∣∣Si∣∣∣−i,j∑∣∣∣Si∩Sj∣∣∣+i,j,k∑∣∣∣Si∩Sj∩Sk∣∣∣−⋯+(−1)k−1∣∣∣∣∣∣i=1⋂kSi∣∣∣∣∣∣i∑(k−1k+r−ni−2)−i,j∑(k−1k+r−ni−nj−3)+i,j,k∑(k−1k+r−ni−nj−nk−4)−⋯+(−1)k−1(k−1k+r−∑i=1kni−k−1)
拿全集 ∣U∣=(k−1k+r−1) 减去上式，得到多重集的组合数
Ans=p=0∑k(−1)pA∑(k−1k+r−1−∑AnAi−p)
其中 A 是充当枚举子集的作用，满足 ∣A∣=p, Ai<Ai+1。
- 递归：fn=(n−1)×(f(n−1)+f(n−2))。
- 容斥：Dn=n!−n!Σk=1nk!−1k−1=n!Σk=0nk!−1k。
n 个人全部来围成一圈，所有的排列数记为 Qnn。考虑其中已经排好的一圈，从不同位置断开，又变成不同的队列。
所以有
Qnn×n=Ann⟹Qn=nAnn=(n−1)!
由此可知部分圆排列的公式：
Qnr=rAnr=r×(n−r)!n!
由于组合数在 OI 中十分重要，因此在此介绍一些组合数的性质。
(mn)=(n−mn)(1)
相当于将选出的集合对全集取补集，故数值不变。（对称性）
(kn)=kn(k−1n−1)(2)
由定义导出的递推式。
(mn)=(mn−1)+(m−1n−1)(3)
组合数的递推式（杨辉三角的公式表达）。我们可以利用这个式子，在 O(n2) 的复杂度下推导组合数。
(0n)+(1n)+⋯+(nn)=i=0∑n(in)=2n(4)
这是二项式定理的特殊情况。取 a=b=1 就得到上式。
i=0∑n(−1)i(in)=[n=0](5)
二项式定理的另一种特殊情况，可取 a=1,b=−1。式子的特殊情况是取 n=0 时答案为 1。
i=0∑m(in)(m−im)=(mm+n) (n≥m)(6)
拆组合数的式子，在处理某些数据结构题时会用到。
i=0∑n(in)2=(n2n)(7)
这是 (6) 的特殊情况，取 n=m 即可。
i=0∑ni(in)=n2n−1(8)
带权和的一个式子，通过对 (3) 对应的多项式函数求导可以得证。
i=0∑ni2(in)=n(n+1)2n−2(9)
与上式类似，可以通过对多项式函数求导证明。
l=0∑n(kl)=(k+1n+1)(10)
通过组合分析一一考虑 S={a1,a2,⋯,an+1} 的 k+1 子集数可以得证，在恒等式证明中比较常用。
(rn)(kr)=(kn)(r−kn−k)(11)
通过定义可以证明。
i=0∑n(in−i)=Fn+1(12)
其中 F 是斐波那契数列。