组合数学习笔记-JZTXT

一些式子

\[(1+x)^\alpha=\sum_{i=0}\binom{\alpha}{i}x^i\\ \binom n k=\frac n k \binom {n-1}{k-1}\\ \binom n k=\binom n{k-1}+\binom {n-1}{k-1}\\ \binom n m =(-1)^m \binom {m-n-1} m\\ \binom n kk^{\underline m}=\binom {n-m}{k-m}n^{\underline m}\\ \sum_{i=0}^n \binom i m=\binom {n+1}{m+1}\\ \sum_{i=0}^n \binom {i+m} i=\binom {n+m+1} n\\ \sum_{i=0}^n (-1)^i\binom n i =\binom {n-m}m=(-1)^m\binom {n-1}m\\ \sum_{k}\binom r {m+k} \binom s {n-k}=\binom {r+s}{n+m}\\ \sum_{k=0}\binom {r-k} m\binom {s+k} n=\binom{r+s+1}{n+m+1} \]

高阶差分

我们记多项式中左移操作为 \(E\)，即 \(E^kf(x)=f(x+k)\)，则 \(\Delta f(x)=f(x+1)-f(x)=Ef(x)-f(x),\Delta =E-1\)。

然后高阶差分即为：\((E-1)^k=\sum_{i=0}^k\binom n k(-1)^{k-i}E^i\)。

牛顿级数

一个 \(\operatorname{deg}=n\) 的多项式 \(f\) 都可以表示成下降幂的形式

\[f(x)=\sum_{i=0}^na_i'x^{\underline{i}}=\sum_{i=0}^nc_i\binom x i \]

其中 \(c_i=a_i'\times i!\) 。

对这个东西 \(x_0=0\) 进行高阶差分，得到：

\[\sum_{k=0} \binom n k(-1)^{n-k}(\sum_{i=0}^kc_i\binom k i)=\Delta^n f(n)=c_n \]

换成一般多项式：

\[\sum_{k=0} \binom n k(-1)^{n-k}(\sum_{i=0}^ka_i\binom k i)=\Delta^n f(n)=n!a_n \]

还有一个长得跟泰勒展开差不多的式子：

\[f(x)=\sum_{k=0}^\infty \frac {(x-x_0)^{\underline{k}}}{k!}\Delta^kf(x_0)=\sum_{k=0}^\infty \binom {x-x_0}{k}\Delta^kf(x)\\ =\sum_{k=0}^\infty \binom {x-x_0} k(\sum_{i=0}^k\binom k i(-1)^{k-i}E^i)=\sum_{i=0}^n\binom{x-x_0} k\sum_{i=0}^k\binom k i(-1)^{k-i}f(i)=\sum_{i=0}^nf(i)\binom x i\binom{n-x}{n-i} \]

证明时取 \(x_0=0\)，随便推几下就可以了。

ARC033D

高桥君有一个未知的 \(N\) 次多项式 \(P(x)\)，只知道 \(P(x)\)在\(x=0,1,2,3\cdots N\) 时的值。高桥君希望知道当 \(x=T\) 时，多项式的值。结果对 \(10^9+7\) 取模。

\(1\le n\le 5\times 10^6,1\le T\le 10^9\)

我们用这个东西推一下：

\[f(T)=\sum_{i=0}^nf(i)\binom T i\binom {n-T}{n-i}\\ =\sum_{i=0}^nf(i)\binom T i(-1)^{n-i}\binom {T-i-1}{n-i}\\ =\sum_{i=0}^nf(i)(-1)^{n-i} \frac{T!\times (T-i-1)!}{i!\times (T-i)!\times (T-n-1)!\times (n-i)!}\\ =\sum_{i=0}^n\frac{f(i)(-1)^{n-i} \frac{T!}{i!\times (T-i)\times (n-i)!}}{(T-n-1)!} \]

然后 \(i!,(n-i)!\) 的逆元可以预处理，\(\frac{T!}{T-i}\) 可以预处理 \(T-n\sim T\) 的前后缀积，做到 \(O(n)\) 复杂度。

组合数

P5824 十二重计数法

有 \(n\) 个球和 \(m\) 个盒子，要全部装进盒子里。
还有一些限制条件，那么有多少种方法放球？（与放的先后顺序无关）

限制条件分别如下：

\(\text{I}\)：球之间互不相同，盒子之间互不相同。
\(\text{II}\)：球之间互不相同，盒子之间互不相同，每个盒子至多装一个球。
\(\text{III}\)：球之间互不相同，盒子之间互不相同，每个盒子至少装一个球。
\(\text{IV}\)：球之间互不相同，盒子全部相同。
\(\text{V}\)：球之间互不相同，盒子全部相同，每个盒子至多装一个球。
\(\text{VI}\)：球之间互不相同，盒子全部相同，每个盒子至少装一个球。
\(\text{VII}\)：球全部相同，盒子之间互不相同。
\(\text{VIII}\)：球全部相同，盒子之间互不相同，每个盒子至多装一个球。
\(\text{IX}\)：球全部相同，盒子之间互不相同，每个盒子至少装一个球。
\(\text{X}\)：球全部相同，盒子全部相同。
\(\text{XI}\)：球全部相同，盒子全部相同，每个盒子至多装一个球。
\(\text{XII}\)：球全部相同，盒子全部相同，每个盒子至少装一个球。

由于答案可能很大，所以要对 \(998244353\) 取模。

我们一个一个来考虑：

\(\text{I}\)：球之间互不相同，盒子之间互不相同。

每个球有 \(m\) 种选择，答案为 \(m^n\)

\(\text{II}\)：球之间互不相同，盒子之间互不相同，每个盒子至多装一个球。

答案为 \(m^\underline n\)
\(\text{III}\)：球之间互不相同，盒子之间互不相同，每个盒子至少装一个球。

枚举有至少多少盒子是空的，答案为

\(\sum_{i=0}^m\binom m i(-1)^i(m-i)^n\)

\(\text{IV}\)：球之间互不相同，盒子全部相同。

枚举空盒子，答案为 \(\sum_{i=0}^m {n\brace m}\)

\(\text{V}\)：球之间互不相同，盒子全部相同，每个盒子至多装一个球。

就是 \([n\le m]\)

\(\text{VI}\)：球之间互不相同，盒子全部相同，每个盒子至少装一个球。

就是 \(n\brace m\)

\(\text{VII}\)：球全部相同，盒子之间互不相同。

先增加 \(m\) 个球，插版法，答案为 \(\binom {n+m-1}{m-1}\)。

\(\text{VIII}\)：球全部相同，盒子之间互不相同，每个盒子至多装一个球。

就是选择 \(n\) 个盒子，答案为 \(\binom m n\)

\(\text{IX}\)：球全部相同，盒子之间互不相同，每个盒子至少装一个球。

插板法，答案为 \(\binom {n-1}{m-1}\)。

\(\text{X}\)：球全部相同，盒子全部相同。

考虑组合意义，相当于划分数，答案为

\[[x^n]1\times (1+x+x^2+\ldots)\times (1+x^2+x^4+\ldots)\times \ldots(1+x^m+x^{2m}+\ldots)\\ =[x^n]\prod_{i=1}^m \frac 1 {1-x^i} \]

然后对于这个，我们先求逆，然后取 \(\ln\) ，并将其展开，得到：

\[\sum_{i=1}^m\ln(1-x^i)=\sum_{i=1}^m(-\sum_{j=1}\frac {x^{ij}}j)\\ =-\sum_{i=1}^m\sum_{j=1}\frac {1}{j}x^{ij} \]

在模 \(x^{n+1}\) 意义下，有效值只有 \(O(n\ln n)\) 个，我们对每个位置暴力修改，然后 \(exp\) 后求逆即可。

有个叫付公主的背包的题也差不多。

\(\text{XI}\)：球全部相同，盒子全部相同，每个盒子至多装一个球。

答案也为 \([n\le m]\)。

\(\text{XII}\)：球全部相同，盒子全部相同，每个盒子至少装一个球。

先令 \(n\gets n-m\)，然后就是 \(\text X\) 的情况。

AGC001E
有 \(n\) 个数对 \((a_i, b_i)\)，求出

\[\sum_{i=1}^{n}\sum_{j=i + 1}^{n}{a_i+b_i+a_j+b_j \choose a_i+a_j} \]
答案对 \(10 ^ 9 + 7\) 取模。

\(1\le a_i,b_i\le 2000,1\le n\le 10^5\)

我们考察组合意义：从 \((-a_i,-b_i)\) 走到 \((a_j,b_j)\) 的方案数，dp 即可，然后减去自己贡献后除 \(2\) 即可。

斯特林数

第一类斯特林数：\(n\brack m\)，把阶为 \(n\) 集合分割为 \(k\) 个非空轮换的个数

第二类斯特林数：\(n\brace m\)，把阶为 \(n\) 集合分割为 \(k\) 个非空子集的个数

递推公式：

\[{n\brack m}={n-1\brack m-1}+(n-1)\times {n-1\brack m}\\ {n\brace m}={n-1\brace m-1}+m\times {n-1\brace m}\\ \]

斯特林数和上升下降幂：

\[x^\overline n=\sum_{k=0}{n\brack k}x^k\\ x^n=\sum_{k=0}{n\brace k}x^\underline k\\ x^\underline n=\sum_{k=0}^n{n\brack k}(-1)^{n-k}x^k\\ x^n=\sum_{i=0}^n{n\brace k}(-1)^{n-k}x^\overline k \]

证明鸽了，大概是归纳法。

P5395 第二类斯特林数·行

第二类斯特林数\(\begin{Bmatrix} n \\m \end{Bmatrix}\)表示把\(n\)个不同元素划分成\(m\)个相同的集合中（不能有空集）的方案数。
给定\(n\)，对于所有的整数\(i\in[0,n]\)，你要求出\(\begin{Bmatrix} n \\i \end{Bmatrix}\)。
由于答案会非常大，所以你的输出需要对\(167772161\)（\(2^{25}\times 5+1\)，是一个质数）取模。

我们来推一下式子：

\[m^n=\sum_{k=0}^n{n\brace k} m^\underline k=\sum_{k=0}^n{n\brace k}k!\binom m k \\ \]

然后 \(n\ge m\) 二项式反演一下，得到：

\[{n\brace m}m!=\sum_{k=0}^{m}\binom m k k^n(-1)^{m-k}\\ {n\brace m}=\sum_{k=0}^{m}\frac {k^n(-1)^{m-k}}{(m-k)!k!}\\ =\sum_{k=0}^m \frac {k^n}{k!}\times \frac {(-1)^{m-k}}{(m-k)!} \]

相当与 \(\frac {k^n} {k!}\) 和 \(\frac {(-1)^k}{k!}\) 卷积，NTT 解决。

P5408 第一类斯特林数·行

第一类斯特林数\(\begin{bmatrix}n\\ m\end{bmatrix}\)表示将\(n\)个不同元素构成\(m\)个圆排列的数目。
给定\(n\)，对于所有的整数\(i\in[0,n]\)，你要求出\(\begin{bmatrix}n\\ i\end{bmatrix}\)。
由于答案会非常大，所以你的输出需要对\(167772161\)（\(2^{25}\times 5+1\)，是一个质数）取模。

还是来推式子：

\[x^\overline n=\sum_{k=0}^n {n\brack k}x^k \]

所以如果我们知道了 \(x^\overline n\) 和 \((x+n)^\overline n\) ，我们就知道了 \(x^\overline{2n}\)。

然后问题在于在知道 \(x^\overline n\) 的情况下如何计算 \((x+n)^\overline n\)，记 \(f(x)=x^\overline n,[x^i]f_i=a_i\) 。

\[f(x+n)=\sum_{i=0}^n a_i(x+n)^i\\ =\sum_{i=0}^n a_i(\sum_{j=0}^i \binom i jx^{j}n^{i-j})\\ =\sum_{j=0}^n x^j\sum_{i=j}^n \binom i ja_in^{i-j}\\ =\sum_{j=0}^n\frac {x^j}{j!}\sum_{i=j}^na_ii!\frac{n^{i-j}}{(i-j)!}\\ 设 g(x)=a_{x} x!,g'(x)=g(n-x),h(x)=\frac {n^{x}}{x!}\\ =\sum_{j=0}^n\frac {x^j}{j!}\sum_{i=0}^{n-j}g(i+j)h(i)\\ =\sum_{j=0}^n\frac {x^j}{j!}\sum_{i=0}^{n-j}g'(n-i-j)h(i) \]

然后后面部分可以 NTT 算出来，然后再用一次 NTT 乘起来就行了。

鸽子

超几何函数：p 用没有，先不学了。