组合数学入门

1 多重组合数

\[\dbinom{n}{a_1,a_2,...a_k}=\dfrac{n!}{a_1!a_2!...a_k!} \]

其中 \(\sum\limits_{i=1}^ka_i=n\)

2 组合数一些性质

\[C(n+m,n)=C(n+m,m)\\ C(n,m)=C(n-1,m-1)+C(n-1,m)\\ C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+...+C(n,0)\\ C(n,l)C(l,r)=C(n,r)C(n-r,l-r)\\ C(n,0)+C(n,1)+...C(n,n)=2^n\\ C(n,0)-C(n,1)+C(n,2)-...=0\\ C(r,r)+C(r+1,r)+...+C(n,r)=C(n+1,r+1)\\ (1+x)^n=\sum\limits_{k=0}^nC(n,k)x^{n-k}=\sum\limits_{k=0}^nC(n,k)x^k \]

3 例题

3.1

求 \(\sum\limits_{k=0}^nC(n,k)^2\)

上式为：

\[\sum\limits_{k=0}^nC(n,k)\times C(n,n-k)=C(2n,n) \]

最后是考虑了它的组合意义。

技巧：考虑组合意义。

3.2

\(\sum\limits_{k=1}^nk^2C(n,k)\)

技巧：二项式求导

一下皆为对 \(x\) 求导。

对 \((1+n)^n\) 求导可以得到：

\[n(1+x)^{n-1}=\sum\limits_{k=0}^nkC(n,k)x^{k-1}\\ nx(1+x)^{n-1}=\sum\limits_{k=0}^nkC(n,k)x^k\\ \]

再次求导可以得到：

\[n((1+x)^{n-1}+(n-1)x(1+x)^{n-2})=\sum\limits_{k=0}^nk^2C(n,k)x^{k-1} \]

取 \(x=1\) ，式子变成了：

\[\sum\limits_{k=1}^nk^2C(n,k)=n(n+1)2^{n-2} \]

3.3

题目：洛谷6620

\(\sum\limits_{k=0}^nf(k)\times x^k\times C(n,k)\)

其中 \(f(x)=\sum\limits_{i=0}^ma_ix^i\)

简述思路：把 \(f(x)\) 拆开，像 \(3.2\) 一样求导即可。

4 组合数问题

\(C(n,m)\bmod k\)

• \(nm\le 10^7\) 直接用杨辉三角形递推就可以。\(k\) 的大小无关。

• \(n \le 10^9,m\le 10^4,k\le 10^9\)

  注意到 \(C_n^m\) 分子和分母上都只有 \(m\) 项，所以我们可以在 \(O(m)\) 的时间复杂度内算出这个东西，但是关于逆元的问题，我们需要关注 \(k\) 是否是质数，如果不是质数，我们就把 \(m\) 分解质因数，然后用中国剩余定理去合并就可以了。

• \(n\le 10^{10},m\le10^{10}\)

  我们利用卢卡斯定理：

  则 \(C(n,m)\bmod k=C(n\%k,m\%k)\times C(n/k,m/k)\bmod k\)

  我们预处理出阶乘和阶乘的逆元，就可以了。

• \(n,m\le 10^9\)

  我们先关注：\(C_n^m\bmod p^k,p^k\le 10^5\)，考虑这个我们怎么做。我们用扩展卢卡斯定理，一种和扩展卢卡斯没有任何关系的算法，我们把 \(n!=p^y\times x_1\) ，其中左边的式子是在 \(\bmod p^k\) 下的结果，同理，令 \(m!=x_2\times p^{y_2},(n-m)!=x_3\times p^{y_3}\)， 所以我们把组合数拆出来，就是一个 \(\frac{x_1}{x_2\times x_3}\times p^{y_1-y_2-y_3}\)，左边可以直接用逆元来做，对于右边 \(y_1-y_2-y_3\ge k\) 那么说明这个组合数是模数的倍数，否则，我们把右边的式子乘到左边的式子，在用逆元去做就可以了。

  我们解决如何算 \(x\times p^y=n!\) ，保证 \(p^y\le 10^5\) ，显然，我们把阶乘展开，分别摸 \(p^k\) 再相乘，这个东西是有循环节的。所以我们考虑分治，每 \(p^k\) 个 \(k\) 数处理一下，令 \(fac_i=x,x\times p^y=i!\)，发现 \(fac_i=i!,i\le p,fac_p=fac_{p-1}\)。所以 \(fac\) 我们可以直接预处理出来，注意这里是预处理第一个循环节，即 \(1,...p^k\)，我们采用如下方式预处理：假设有 \(fac_{i-1}\) ，我们对 \(i\) 进行质因数分解，然后与 \(fac_{i-1}\) 合并得到 \(fac_{i}\) 。同时我们处理一下 \(y\) 的大小，记在 \(cnt\) 里。代码：

  int p,k,pk;
  
  fac[0]=1;
  cnt[0]=0;
  for(int i=1;i<=pk;i++){
      int j=i;cnt[i]=cnt[i-1];
      while(j%p==0) j/=p,cnt[i]++;
      fac[i]=fac[i-1]*j%pk; 
  }
  

  我们把他的循环节展开，会发现除了最后一个位置之外，其余所有的位置 \(x,y\) 都相同，且最后一个位置除了 \(x\) 之外也相同，刨去 \(p^k\) 最后一个位置剩下的是 \(r!\) ，其中 \(r\) 是循环节的个数。于是我们可以递归的处理。

  以下我们先处理循环节多出来的那一部分，再处理循环节，最后处理最后的位置。代码：

  inline pair<int,int> solve(int n){
      if(n<=pk) return make_pair(fac[n],cnt[n]);
      int l=n%pk;
      int x=fac[l],y=cnt[l];
      int r=n/pk;
      x=1ll*ksm(fac[pk],r,pk)%pk;
      y=y+cnt[pk]*r;
      (x,y)+=solve(r);
      return (x,y);
  }
  

  注意倒数第三行是伪代码。

  我们把 \(k\) 质因数分解，做上面这个工作，然后用中国剩余定理合并，就可以了。

5 例题

5.1

需要我们把 \(x\) 拆成 \(k\) 个组合数的和使得这些组合数的和加起来等于 \(k\) 。\(x\le 10^9,k\le 10^3\)

我们把 \(x\) 拆成 \(x=1+1+....x-k+1\) ，然后最后是 \(C(x-k+1,1)\) ，前面都是 \(C(q,q)\) ，这个题就做完了。

5.2

比较 \(C(n_1,m_1),C(n_2,m_2)\) 大小关系。其中 \(n_1,n_2,m_1,m_2\le 10^6\) 。

我们这里的技巧是用对数比较大小。我们用 \(C(n,m)\) 举例子，这里 \(C(n,m)=\frac{n!}{m!(n-m)!}\) ，那么 \(\ln C(n,m)=\ln n!-\ln m!-\ln (n-m)!\)，而 \(\ln i!=\ln (i-1)!+\ln i\) ，所以这个题就可以做了。

5.3

找到 \(k\) 个不同的组合数，要求找到的组合数 \(C(a,b)\) ，满足 \(0\le b\le a\le n\) ，求最大的和。

发现最下面最中间最大，然后次大的只可能是他周围的 \(4\) 个数之中，所以我们建一个堆，注意需要判断每个数是否被加入堆。我们就可以 \(k\log k\) 的复杂度搞定。

5.4

小葱选择了四个整数 \(n,p,k,r\) ，他希望知道 \((\sum\limits_{i=0}^{\infty}C_{nk}^{ik+r})\bmod p\) 的值。

其中 \(n\le 10^9,p\le 10^9 0\le r< k\le 50\)。

我们设 \(f(n,r)=\sum\limits_{i=0}^{\infty}C_{nk}^{ik+r}\) ，我们通过用杨辉三角不断展开组合数会得到：\(C_n^m=\sum\limits_{i=0}^kC_{n-k}^{m-i}\times C_k^i\)，我们把左边这个式子展开 \(k\) 次，得到 ：

\[f(n,r)=\sum\limits_{i=0}^{\infty}\sum\limits_{j=0}^k C_{(n-1)k}^{ik+r-j}\times C_k^j\\ =\sum\limits_{j=0}^kC_k^j\sum\limits_{i=0}^{\infty}C_{(n-1)k}^{ik+r-j}\\ =\sum_{j=0}^kC_k^j f(n-1,r-j) \]

然后我们构造一个矩阵，用矩阵快速幂，这个题就做完了。时间复杂度 \(k^3\log n\)。

注：\(f_{i,j}=\sum\limits_{k}^mf_{i-1,k}\times val_{k,j}\) 这样的式子都可以用矩阵来优化，明显这是一个矩阵乘法的形式。所以满足矩阵乘法形式的式子都可以用矩阵快速幂优化。并且矩阵构造方法唯一。

那么我们加强以下数据，如果 \(k\le 1000\) 这个题怎么做。

如果 \(k\le 100000\) 怎么做。

zhx没有讲。我也不会做。有一些知识还没有讲。

5.5

给定 \(n,m,k\) ，对于所有 \(0\le i\le n,0\le j\le min(i,m)\) 有多少 \((i,j)\) 满足 \(C(i,j)\) 为 \(k\) 的倍数。其中 \(n,m\le 10^{18}\) ，\(k\le 100,k\in Prime\)。

我们考虑用卢卡斯定理。

那什么情况下 \(C_{n_i}^{m_i}\) \(\bmod p=0\) 呢？因为不可能含有 \(p\) 这个因子，所以只能是 \(C_{n_i}^{m_i}=0\) ，我们考虑用所有的方案减去不合法方案数，考虑计数所有 \(C_n^m\not \equiv 0\bmod p\) ，即 \(\forall m_i\le n_i\) ，我们考虑用数位 dp 去完成计数这个事情。

6 抽屉原理

把 \(kn+1\) 个物品放到 \(n\) 个抽屉里面，至少有一个抽屉里面有 \(k+1\) 个物品。

6.1

给定 \(n\) 个数，要求从中选出任意多个数，使得他们的和为 \(c\) 的倍数。其中 \(c\le N\le 10^5\) 。

我们考虑鸽巢原理，设 \(sum_i\) 为前 \(i\) 个数的前缀和 \(\bmod c\) 的结果，根据鸽巢原理，一定存在 \(i,j\) ，使得 \(sum_i\equiv sum_j\bmod k\) ，则中间这些数加起来 \(\bmod k\) 等于 \(0\) 。

平面上有 \(n\) 个点 \((x_i,y_i)\)，用三个 \(L\times L\) 去覆盖所有点，问最小的 \(L\) ，\(n\le 5\times 10^4\)

我们构造出围住这些点的最小矩形，然后发现这个矩阵每一条边都有一个点，由鸽巢原理可以知道，一定存在一个正方形可以覆盖两个点，我们枚举这个正方形位置，把被覆盖的点去掉。重复上述过程两遍，最后看是否能覆盖。

7 容斥原理

$ |A_1\cup A_2...\cup A_n|= \sum\limits_{B\subseteq{A_1,A_2,...A_n}}(-1)^{|B|+1}\times |\cap_{A_i\in B}A_i|$

7.1

询问 \(1-N\) 当中有多少个数可以表示成 \(x^y,y>1\) 的形式。其中 \(N\le 10^{18}\)。

我们考虑枚举 \(y\) 而不是 \(x\) ，其中 \(y\le 64\) ，并且 \(2^{64}>10^{18}\) ，我们考虑对应每一个 \(y\) 计数所有的 \(x\) ，用对数做一下最可以，现在考虑算重，可以用莫比乌斯函数来容斥，这个题就做完了。

7.2

\(n\times m\) 的棋盘，要求有至少 \(r\) 行 \(c\) 列染成了黑色，剩下格子随意黑白，问方案数。

我们有 \(C_n^r\times C_m^c\times 2^{(n-r)\times (m-c)}\)

问题是这个方案会被算重。

扩展容斥原理：从多个集合的交出发，需要关注每一种情况被算了多少次，把容斥系数算出来。

\(r+1\) 行被多算了多少次：\(r\)，所以需要减去 \(r\times C_{n}^{r+1}\times C_{m}^{c}\)

\(r+2\) 行被少算了了多少次：\(|C_{r+2}^r-r\times C_{r+1}^r|\) 次。所以需要加上 \(|C_{r+2}^r-r\times C_{r+1}^r|\times C_{n}^{r+2}\times C_m^c\)。

以此类推，算出所有的方案数，就可以容斥了。直接 \(n^2\) 算系数就可以。行如何容斥与列如何容斥是没有关系的。

7.3

网格中每步可以走 \((0...Mx,0...My)\) 中任意非零向量，有 \(k\) 中向量不能走，分别是 \((k_i,k_i)\) ，\(k_i\) 一定是 \(10\) 的倍数，求从 \((0,0)\) 走到 \((Tx,Ty)\) 走 \(R\) 步的方案数。

我们考虑如果没有 \(k\) 的限制，发现 \(x\) 和 \(y\) 实际上是独立的。这里我们可以有两个 dp，设 \(f_{i,x}\) 表示走了 \(i\) 步走到了 \(x\) ，\(g_{i,y}\) 同理，这样，当我们用 \(f_{R,T_x}\) 乘上 \(g_{R,T_y}\) 就是所有的方案，考虑减去所有不合法的方案数，这里我们考虑用容斥，\(h_{i,z}\) 表示走 \(i\) 步，这 \(i\) 步全部走到了 \((10z,10z)\) 的方案数。

我们枚举一个 \(i\) 表示至少走了 \(i\) 步不合法的方案数，再枚举这 \(i\) 步走到了 \((10z,10z)\) ，那么这时的方案数为 \(h_{i,z}\times f_{R-i,T_x-10z}\times g_{R-i,T_y-10z}\times C_R^i\times (-1)^i\)

这样容斥就可以了。这样就做完了。

7.4

给定左视图，和正视图，问有多少种可能情况。

我们首先发现，我们交换两个列方案数是不变的，所以我们首先可以按照左视图正视图的大小从小到大排序，这样对答案没有影响。

之后我们会发现，对于正视图上一段，左视图上一段，这段中的大小是相等的，我们可以用容斥去计数这样的一个矩形，用总方案减去不合法方案就可以。

我们考虑再扩展那么一段，发现之后的区域变成了一个 \(L\) 形，我们一样可以对这个区域做容斥。

发现之后所有的区域都是一个 \(L\) 形，那么这个题就做完了。

8 Burnside 引理

8.1 群

满足四个条件的集合成为一个群：

定义了乘法后，满足封闭性，结合律，幺元，逆元，这样的集合成为一个群。

即：

\[a,b\in S，ab\in S\\ a(bc)=(ab)c\\ \exists e\in S,\forall b\in S,eb=be=b\\ \forall a\in S,\exist b \in S,s.t.ab=e \]

在上面的基础上，如果满足交换律，那么这种群被称作阿贝尔群。

8.2 置换群

对 \(n\) 的全排列进行交换操作的群。我们用循环节的方式去描述一个置换，比如 \((1,2,3)(4,5)\)，相当于：

\[1\to 2\\ 2\to 3\\ 3 \to 1\\ 4\to 5\\ 5\to 4 \]

置换群的集合里有多个置换，注意上面的排列代表的是位置而不是数。置换之间的乘法定义为两个置换之间的结合。置换群幺元定义为 \((1)(2)(3)...(n)\) 。轨道指有多少个括号。

8.3 Burnside 引理

要对 \(n\) 个元素用 \(m\) 种颜色染色。对应置换群为 \(S\) ，一种颜色方案通过置换群中的置换得到的颜色看做一类。

则方法数为 \(\frac{\sum\limits_{s\in S} m^{\eta(s)}}{|S|}\) 其中 \(\eta(s)\) 为置换 \(s\) 的轨道数。

这里计数是一个轨道内颜色要求一样。

在做 \(Burnside\) 的题时需要：

• 置换群的构造。
• 轨道数的计算。

8.4 例题

8.4.1

\(n\) 个点排成一圈，用 \(m\) 中颜色染色。计数方案数。

• 置换群为转 \(k\) 次对应的 \(n\) 个置换群。
• 注意到这个题每个轨道内元素个数是一样多的，我们只需要知道某一个轨道内有多少个元素就知道有多少个轨道，我们考虑把所有标号减 \(1\) ，发现如果转 \(i\) 次，置换的第一个轨道中的元素为 \(0,i,2i...\) 我们需要找到一个最小的 \(k\) ，满足 \(n|ki\) ，这个 \(k\) 应该为 \(\frac{n}{\gcd(n,i)}\)，所以轨道长度为 \(k=\frac{n}{\gcd(n,i)}\) 所以一共有 \(\gcd(n,i)\) 个轨道。

8.4.2

我们有一个迷宫，一开始是一个 \(n\) 变形，然后每一次扩展都会沿所有最外层的边增加一个正 \(n\) 边形，一共扩展 \(k-1\) 次。如果有重叠，那么只保留一个就可以。

我们只考虑 \(4\) 边形的情况。我们可以这样写（一下我们考虑 \(k=2\))：

\((1)^{16}\) 代表我们有 \(16\) 个大小为 \(1\) 的轨道，而 \(90\) 度的时候，我们有 \((4)^4\) ，\(180\) 度时 \((2)^8\) ，\(270\) 度时 \((4)^4\) 。

发现边数为 \(4k^2\) ，所以我们的置换群为 \((1)^{4k^2},(4)^{k^2},(2)^{2k^2},(4)^{k^2}\)。

注意到 Burnside 引理中每个轨道中染同一种颜色，应用到这个题里面，每一个轨道中所有的边要么选，要么不选，所以式子的值为：

\[\frac{C_{4k^2}^r+C_{k^2}^{\frac r 4}+C_{2k^2}^{\frac r 2}+C_{k^2}^{\frac r 4}}{4} \]

如果不整除，这种方案就是 \(0\) 。

8.5 立体图 Burnside 引理

给定正方体，这个正方体。

要求用 \(m\) 种颜色对 \(6\) 个面染色，旋转可视为一种情况。

置换群：

• 不转。\((1)^{16}\)

• 选择两个相对的面中心点的连线作为旋转轴，即面面旋转。可以转 \(90,180,270\) 度

  • \(90:(1)^2(4)^1\)

  • \(180:(1)^2(2)^2\)

  • \(270:(1)^2(4)^1\)

  一共有 \(3\) 个旋转轴。

• 棱棱旋转 只能是 \(180\) 度，有 \(6\) 种选择方法，为 \((2)^3\)。

• 点点旋转，数量为 \(4\) ，为 \(120,240\) 度。无论哪个，都是 \((3)^2\)。

我们考虑怎么算答案，不难发现，答案为：

\[\frac{m^6+(m^3+m^4+m^3)\times 3+m^3\times 6+(m^2+m^2)\times 4}{24} \]

不过这样十分麻烦，下面引出一种通用的计算置换群的方法。

8.6 扩展

我们用 \(m\) 种颜色给面染色，用 \(k\) 种颜色给棱染色，用 \(r\) 种颜色给点染色。那正方体距离，一共有 \(6\) 个面，\(12\) 条棱，\(8\) 个点。

• 不转 数量为 \(1\)
• 面面 数量为 \(3\)，因为要发生重合，所以不妨把这个正多面体展开，发现转的角度实际上是它其中一个面的一个中心角的倍数。
• 棱棱 角度一定为 \(180\) ，数量为棱数除以 \(2\) 。
• 点点 找到点后观察其邻面的数量，不妨设为 \(q\) ，那么这个旋转的角度一定是 \(\frac {360} q\) 的倍数。

我们先不管置换，我们考虑换一个例子：正方体变为正 \(12\) 面体。

\(20\) 个点，\(12\) 个面，\(30\) 条棱，\(5\) 边形。

• 不转 角度为 \(0\) 数量为 \(1\)
• 面面 角度为 \(72,144,216,288\) 数量为 \(6\)
• 棱棱 角度 \(180\) 数量 \(15\)
• 点点 角度 \(120,240\) 数量 \(10\)

至此，旋转的角度和数量都是可以推的。

回到正方体，关注置换数量：

• 不转：面：\((1)^6\) 棱 \((1)^{12}\) 点 \((1)^8\)。

我们引入循环节，即每一种转法转几次会复原。实际上这个循环节是置换群轨道长度。

那么对于每一种情况，不管是面，棱，还是点，除去不动的地方，对于剩下的，除以循环节，就是轨道数。

这里直接放上正 \(4\) 面体和正 \(6\) 面体的表。

8.7 再次扩展

外角和公式：任意一个多面体所有外角之和等于 \(720\) 度。这里外角指的是对于所有的点，以这个点为顶点的角之和与 \(360\) 度的差称作这个点的外角。所以如果我们要计数足球上的点，发现其每个点的外角相等，足球上每一个点与两个正六边形和一个正五边形，所以可以得到足球有 \(60\) 个点。我们现在需要计数有多少条边，有多少个五边形，多少个六边形。发现点数除以 \(5\) 就是五边形个数，所以五边形有 \(12\) 个。

每个五边形周围有 \(5\) 个六边形，每个六边形会被 \(3\) 个五边形算到，所以一共有 \(20\) 个六边形。计数所有的面的边数，然后每一条边会算两次，所以一共有 \(90\) 条边。我们现在需要列表，任然是旋转，角度，循环节，数量，五边形面，六边形面，棱，点。在上面的基础上，再分类讨论一些东西，就做完了。这里直接放上表。

9 生成函数

我们称 \(f(x)=\sum\limits_{i=1}^ng(i)x^i\) 为数列 \(g\) 的生成函数。

其中 \(g(x)=1+kx+k^2x^2+...=\frac{1}{1-kx}\)

9.1

求用 \(1,2,3\) 分的邮票贴出多少不同的方案。

\[(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6...) \]

容易发现：

\[1+x+x^2+...=\frac 1 {1-x}\\ \]

所以上面的式子变成：

\[\frac{1}{1-x}\times \frac{1}{1-x^2}\times \frac{1}{1-x^3} \]

9.2 斐波那契通项公式

令 \(F(x)=\sum\limits_{i=0}f_ix^i\)

那么 \(F(x)-xF(x)=(\sum\limits_{i=0}f_ix^{i+2})+x=x^2F(x)+x\)

那么我们有 \(F(x)=\frac{x}{1-x-x^2}\)。

我们对这个式子因式分解。我们用待定系数法，设分解完之后为 \(\frac{c}{1-ax}+\frac{1}{1-bx}\)

把上面这个式子通分之后列方程可以得到 \(a,b,c,d\) 的解，这样我们可以得到它的同行公式：

\[F(x)=-\frac{1}{\sqrt{5}}\times \frac{1}{1-\frac{1-\sqrt 5}{2}x}+\frac{1}{\sqrt 5}\times \frac{1}{1-\frac{1+\sqrt 5}{2}x} \]

所以我们可以得到：

\[f_x=-\frac{1}{\sqrt{5}}\times (\frac{1}{1-\frac{1-\sqrt 5}{2}x})^x+\frac{1}{\sqrt 5}\times (\frac{1}{1-\frac{1+\sqrt 5}{2}x})^x \]

9.3 线性常系数齐次递推关系

对于一个数列 \(a\) 来说，如果其满足 \(a_n+c_1a_{n-1}+c_2a_{n-2}+...+c_ka_{n-k}=0\)

那么称其特征多项式为：

\[x^k+c_1x^{k-1}+c_2x^{k-1}+...c_k=0 \]

我们可以解出上面这个方程的根，一定有 \(k\) 个根。

• 如果根两两不同，那么 \(a_n=\sum\limits_{i=1}^kl_ix_i^n\)

  其中 \(l\) 数组被初始值决定。

• 如果有 \(r\) 个根是一样的，其余根两两不同，那么 \(a_n=(l_1+l_2n+l_3n^2+...l_rn^{r-1})x_1^n+x_2^n+...x_k^n\)

需要有一个次数不大于 \(r\) 的多项式。

9.4 例题

9.4.1

有 \(n\) 种糖果，每一种 \(m_i\) 个，至少吃掉 \(a\) 个，至多 \(b\) 个，求吃掉糖果方案数。

我们考虑生成函数，不难发现，这个东西的生成函数为 \(f(x)=\frac{\prod\limits_{i=1}^n(1-x^{m_i})}{(1-x)^n}\)

对于 \(x_i\) 的系数，我们发现分子可以 \(2^{10}\) 暴力展开，分母相当于 \((1+x+x^2+...)^n\) 的生成函数，那么对于 \(x_j\) ，它的系数是把 \(j\) 分解成 \(n\) 个整数和的方案数，为 \(C_{j+n-1}^{j}\) 个，这里已经考虑了顺序的情况。

这个题就做完了。