『算法-ACM竞赛-数学-数论』 组合数+卢卡斯定理+扩展卢卡斯定理 (2)
『算法-ACM 竞赛-数学-数论』 组合数+卢卡斯定理+扩展卢卡斯定理 (2)
一、无重复元素的排列组合定义
排列，英文名为 Permutation，是指从某元素集合中取出指定个数的元素进行排序
组合，英文名为 Combination，是指从某元素集合中仅仅取出指定个数的元素，不考虑排序
从有 n 个不同元素的集合任取 r 个元素的排列方式有：
$P(n, r) = n*(n-1)…(n-r+1) = n! / (n-r)!,特别地 P(n,n) = n!$
从有 n 个不同元素的集合任取 r 个元素的组合方式有：
$C(n, r) = P(n, r) / r! = n! / ( (n-r)! * r!)，特别地C(n,n) = 1$
二、多重集合（multiset）的排列组合
设多重集合 $S = { n1 * a1, n2 * a2, …, nk * ak }\ \ \ \ \ n = n1 + n2 + … + nk$
即集合 S 中含有 n1 个元素 a1， n2 个元素 a2，…，nk 个元素 ak，ni 被称为元素 ai 的重数，k 成为多重集合的类别数
在 S 中任选 r 个元素的排列称为 S 的 r 排列，当 r = n 时，有公式
$P(n; n1a1, n2a2, …, nkak) = n! / (n1! * n2! * … nk!)$
在 S 中任选 r 个元素的组合称为 S 的 r 组合，当 r<=任意 ni 时，有公式
$C(n; n1a1, n2a2, …, nk*ak) = C(k+r-1, r)$
由公式可以看出多重集合的组合只与类别数 k 和选取的元素 r 有关，与总数无关！
三、多重集合问题的转化例子
例 1：线性方程 x1 + x2 + … + xk = r 一共有多少组非负整数解？
解答：上述不定方程的非负整数解对应于下述排列
1…101…1 01…1 0 …… 01…1
x1 个 x2 个 x3 个 …… xk 个
其中 k-1 个 0 将 r 个 1 分成 k 段， 每段含 1 的个数分别为 x1, x2, …, xk,
很明显这个排列是多重集合 S = { r _ 1， （k-1）_ 0 }的全排列
即：P(r+k-1; r*1, (k-1)*0) = (r+k-1)! / ( r! * (k-1)! ) = C( r+k-1, r),即从 k 类元素中选 r 个的种类
例二：某车站有 6 个入口处，每个入口处每次只能进一个人， 一组 9 个人进站的方案有多少？
解答：进站方案可以表示为
1 011 011 01 011 01
g1 g2 g3 g4 g5 g6
其中 1 表示不同的人， 而 0 表示门框, 6-1= 5 个门框将序列分为六段,
则任意进站方案可表示成上面 14 个元素 S = { 5 _ 1, 1 _ p1, 1 _ p2, …, 1 _ p9 }的一个排列
即：P(5+9;51, 1p1, 1p2, …, 1p9) = 14! / ( 5! _ 1! _ …. 1! ) = 14! / 5!
例三、求从（0,0）点到（m,n）点的非降路径数
解答：无论哪条路径，必须在 x 方向上走 m 步，y 方向上走 n 步，将非降路径数与多重集合 S = { m _ x, n _ y } 的排列建立一一对应关系，所以格路总数为 P(m+n; mx, ny) = (m+n)! / ( m! * n! ) = C(m+n, n) = C(m+n, m)
一般地，设 c>=a, d>=b,则由(a,b)到(c,d)的非降路径数为 C(c-a+d-b, c-a)
扩展问题： 在上例基础上若设 m<n,求点（0,1）到点(m,n)不接触对角线 y=x 的非降路径数据（接触包括穿过）
解答：从（0,1）到(m,n)的非降路径，有的接触 y=x，有的不接触，对于每条接触 y=x 的非降路径，做(0,1)关于 y=x 的对称点(1,0)到(m,n)的对称非降路径，容易看出从（0,1）到（m,n）接触 y=x 的非降路径与 （1,0）到(m,n)的非降路径（必穿过 y=x）一一对应，
故所求的非降路径数为 C(m+n-1, m) - C(m+n-1, m-1)
例四、将 r 个相同的小球放入 n 个不同的盒子，总共有多少种方案？
解答：该问题可以转化为 r 个相同的小球与 n-1 个相同的盒壁的排列问题
1…1 0 1…1 0 1…1 0 …… 0 1…1
其中有 n-1 个 0 分成 n 段,每段表示不同的盒子， 每段中 1 的个数表示该盒子里放入的小球总数，总共 r 个 1
即：P( r+n-1; r*1, (n-1)*0 ) = (r+n-1)! / ( r! * (n-1)! ) = C( r+n-1, r)
例五、求集合 X = { 1,2，…, n }的不含相邻整数的 k 元子集个数
解答：任意一个 X 的 k 元子集 s 都可以对应于一个由 0,1 组成的有序 n 重组（a1 a2 … an）,其中 ai = 1 当 i 属于 s，否则 ai = 0，当 i 不属于 s，由于 s 中不含相邻整数，所以在此 n 重组中没有两个 1 是相邻的，所以子集 s 是与这样的 n 重组 S = { k*1, (n-k)*0 }之间是一一对应的，由于任意两个 1 彼此不相邻，故可以把（n-k）个 0 依次排列，然后在（n-k+1）个空隙中插入 k 个 1，所以从（n-k+1）个空隙中选择 k 个位置来放置 1，有 C(n-k+1, k) 种选法，这也是原问题所对应的答案。
四、母函数
生成函数（母函数）有普通生成函数和指数生成函数： 1.普通生成函数用于解决多重集的组合问题
2.指数型母函数用于解决多重集的排列问题
母函数可以解决递归数列的通项问题：斐波那契数列、卡特兰数列等
普通母函数：
构造母函数 G(x), G(x) = a0 + a1x + a2 + a3* +….+ an*， 则称 G(x)是数列 a0,a1…an 的母函数。
通常普通母函数用来解多重集的组合问题，其思想就是构造一个函数来解决问题，一般过程如下：
1.建立模型：
物品 n 种,每种数量分别为 k1,k2,..kn 个，每种物品又有一个属性值 p1,p2,…pn,(如本题的字母价值)，求属性值和为 m 的物品组合方法数。（若数量 ki 无穷 也成立，即对应下面式子中第 ki 项的指数一直到无穷）
2.构造母函数：
G(x)=(1++…)(1+++…)…(1+++…) （一）
=a0 + a1x + a2 + a3* +….+ akk* (设 kk=k1·p1+k2·p2+…kn·pn) （二）
G(x)含义： ak 为属性值和为 k 的组合方法数。
母函数利用的思想： 1.把组合问题的加法法则和幂级数的乘幂对应起来。
2.把离散数列和幂级数对应起来，把离散数列间的相互结合关系对应成为幂级数间的运算关系，最后由幂级数形式来 确定离散数列的构造。
代码实现：
求 G(x)时一项一项累乘。先令 G=1=(1+0x+0+…0*),再令 G=G*(1++…)得到形式(二)的式子…最后令 G=G*(1+++…)。
下面是指数型母函数的定义：
对于上面的问题“假设有 8 个元素，其中 a1 重复 3 次，a2 重复 2 次，a3 重复 3 次。从中取 r 个组合，求其组合数。”：
（感谢 3Dnn 同学指出，下图的 28/3! 应该改为 26/3!）