斯特林数与斯特林反演

第一类斯特林数

定义：

$\Large {n \brack m} $ 表示 \(n\) 个元素分成 \(m\) 个环的方案数

显然：

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

理解：考虑从 \(n?1\) 个元素推过来，如果两个空环肯定是不符合的空一个环则单独成环，如果 \(n?1\) 的时候就没有空环就任意放在一个元素前

性质：

1：

\[n!=∑_{i=0}^{n}\limits {n\brack i} \]

理解： 其实本质就是置换，一个环则为一组轮换，每种排列都会对应着唯一 一种置换

2：

\[x^{\underline{n}}=∑_{i=0}^n\limits {n\brack i}(?1)^{n?i}x^i \]

使用归纳法即可：

\[ x^{\underline {n+1}}=(x?n)x^{\underline{n}}\\ =(x?n)∑_{i=0}^n\limits {n\brack i}(?1)^{n?i}x^i\\ =∑_{i=0}^n\limits {n\brack i}(?1)^{n?i}x^{i+1}?n∑_{i=0}^{n+1}\limits {n\brack i}(?1)^{n?i}x^i\\ =∑_{i=1}^{n+1}\limits {n\brack i?1}(?1)^{n?i+1}x^i+n∑_{i=0}^{n+1}\limits {n\brack i}(?1)^{n?i+1}x^i\\ =∑_{i=1}^{n+1}\limits({n\brack i?1}+n?{n\brack i})(?1)^{n?i+1}x^i\\ =∑_{i=0}^{n+1}\limits {n+1\brack i}(?1)^{n+1?i}x^i \]

类似地，我们可以证明：

\[x^{\overline{n}}=∑^n_{i=0}\limits {n\brack i}x^i \]

证明类上，不再赘述。

第二类斯特林数

定义：

\(\Large {n\brace m}\) 表示 \(n\) 个有区别的小球丢进 \(m\) 个无区别的盒子，无空盒子的方案数

显然：

\[{n\brace m}={n?1\brace m?1}+m?{n?1\brace m} \]

理解： 考虑从 \(n?1\) 个小球推过来，如果两个空盒子肯定是不符合的空一个盒子则只能放到那个空盒子里面了，如果 \(n?1\) 的时候就没有空箱子就随便放。

性质：

\[m^n=∑_{i=0}^n\limits {n\brace i}?i!?C(m,i) \]

当然也可以写成：

\[m^n=∑_{i=0}^n\limits {n\brace i}?m^{\underline{i}} \]

理解： \(m^n\) 为 \(n\) 个有区别的小球丢进 \(m\) 个有区别的盒子，允许空盒子。枚举有效盒子的个数，再从 \(m\) 个盒子选 \(i\) 个盒子，然后 \(n\) 个小球丢进 \(i\) 个盒子。

转换到组合表示：

第二类斯特林数显然是和排列组合有关系的，转换过来：

\[{n\brace m}=\frac 1 {m!}∑_{k=0}^m\limits (?1)^kC(m,k)(m?k)^n \]

理解： 如果空箱子的情况我们也算进去，答案显然是 \(\dfrac {m^n}{m!}\) ，反过来求第二类斯特林数，又得减掉这种情况：选 \(k\) 个空盒子，然后小球放到其他的盒子里，但最后我们求出来的答案为有区别的盒子，转换过来要 \(×\dfrac 1 {m!}\)

第二类斯特林数与自然数幂的关系

求：

\[Sum(n)=\sum_{i=0}^n i^k \]

有：

\[Sum(n)=\sum_{i=0}^n i^k\\ =\sum_{i=0}^n \sum_{j=0}^k {k\brace j} i^{\underline{j}}\\ =\sum_{j=0}^k {k\brace j} \sum_{i=0}^n i^{\underline{j}}\\ =\sum_{j=0}^k {k\brace j} \sum_{i=0}^n j! \cdot C_i^j\\ =\sum_{j=0}^k {k\brace j}\cdot j! \sum_{i=0}^n C_i^j \]

其中 \(\sum_{i=0}^n C_i^j\) 是求杨辉三角一列的和。

通过归纳法可得： \(\sum_{i=0}^n C_i^j=C_{n+1}^{j+1}\) ，进而有：

\[=\sum_{j=0}^k {k\brace j}\cdot j!\cdot C_{n+1}^{j+1}\\ =\sum_{j=0}^k {k\brace j}\cdot \frac{(n+1)^{\underline{j+1}}}{j+1} \]

斯特林反演

定义：

\[f(n)=∑_{k=0}^n\limits {n\brace k}g(k)?g(n)=∑_{k=0}^n\limits (?1)^{n?k}{n\brack k}f(k) \]

证明：

我们先证这个反转公式

\[∑_{k=m}^n\limits (?1)^{n?k}{n\brack k}{k\brace m}=[m=n]\\ ∑_{k=m}^n\limits (?1)^{n?k}{n\brace k}{k\brack m}=[m=n]\\ \]

反转公式1：

\[m^{\underline{n}}=∑_{i=0}^n\limits {n\brack i}(?1)^{n?i}m^i\\ =∑_{i=0}^n\limits {n\brack i}(?1)^{n?i}∑_{j=0}^i\limits {i\brace j}m^{\underline{j}}\\ =∑_{i=0}^n\limits m^{\underline{i}}∑_{j=i}^n\limits (?1)^{n?j}{n\brack j}{j\brace i} \]

反转公式2：

\[m^n=∑_{i=0}^n\limits {n\brace i}m^{\underline{i}}\\ =∑_{i=0}^n\limits {n\brace i}(?1)^i(?m)^{\overline{i}}\\ =∑_{i=0}^n{n\brace i}(?1)^i∑_{j=0}^i\limits {i\brack j}(?m)^j\\ =∑_{i=0}^n\limits m^i∑_{j=i}^n\limits (?1)^{i?j}{n\brace j}{j\brack i} \]

例题：

[省选联考 2020 A 卷] 组合数问题

计算：

\[\sum_{k=0}^{n}f(k)\times x^k\times \binom{n}{k} \]

其中 \(n\), \(x\) \((1\le n, x\le 10^9)\) 为给定的整数，\(f(k)\) 为给定的一个 \(m\) 次多项式 \(f(k) = a_0 + a_1k + a_2k^2 + \cdots + a_mk^m\)，\(0\le m \le \min(n,1000)\)

有：

\[\sum_{k=0}^{n}\sum_{i=0}^m a_i\times k^i\times x^k\times \binom{n}{k}\\ =\sum_{i=0}^ma_i\times \sum_{k=0}^{n} k^i\times x^k\times \binom{n}{k}\\ =\sum_{i=0}^ma_i\times \sum_{k=0}^{n}\sum_{j=0}^{i}{i\brace j} k^{\underline{j}}\times x^k\times \binom{n}{k}\\ =\sum_{i=0}^m\sum_{k=0}^{n}\sum_{j=i}^{m}a_j\times {j\brace i} k^{\underline{i}}\times x^k\times \binom{n}{k}\\ =\sum_{i=0}^m \sum_{k=0}^{n}\sum_{j=i}^{m}a_j\times {j\brace i} \frac{k!}{(k-i)!}\times x^k\times \frac{n!}{k!(n-k)!}\\ =\sum_{i=0}^m\sum_{j=i}^{m}a_j\times {j\brace i}\times \sum_{k=0}^{n} x^k\times \frac{n^{\underline{i}}\times (n-i)^{\underline{k-i}}}{(k-i)!}\\ =\sum_{i=0}^m\sum_{j=i}^{m}a_j\times {j\brace i}\times n^{\underline{i}}\times \sum_{k=0}^{n} x^k\times C_{n-i}^{k-i}\\ =\sum_{i=0}^m\sum_{j=i}^{m}a_j\times {j\brace i}\times n^{\underline{i}}\times x^i\times \sum_{k=0}^{n-i} x^k\times C_{n-i}^{k}\\ =\sum_{i=0}^m\sum_{j=i}^{m}a_j\times {j\brace i}\times n^{\underline{i}}\times x^i\times (x+1)^{n-i}\\ =\sum_{i=0}^mn^{\underline{i}}\times x^i\times (x+1)^{n-i}\sum_{j=i}^{m}a_j\times {j\brace i}\\ \]

点击查看代码

[清华集训2016] 如何优雅地求和

有一个多项式函数 \(f(x)\)，最高次幂为 \(x^m\) ，定义变换 \(Q\) ：

\[Q(f,n,x)=∑_{k=0}^{n}\limits f(k)\binom nkx^k(1?x)^{n?k} \]

现在给定函数 \(f\) 和 \(n,x\) ，求 \(Q(f,n,x)\bmod998244353\) 。

出于某种原因，函数 \(f\) 由点值形式给出，即给定 \(a_0,a_1,?,a_m\) 共 \(m+1\) 个数，\(f(x)=a_x\) 。

考虑二项式反演：

\[f(x)=\sum_{i=0}^xs_i{x\choose i}\ ?\ s_x=\sum_{i=0}^x(-1)^{x-i}{x\choose i}f(i) \]

由于 \(\Large{x\choose i}\) 是一个 \(i\) 次多项式，\(f(x)\) 可以写成 \(f(x)=\sum_{i=0}^m\limits s_i{x\choose i}\) 的形式。

有：

\[s_x=\sum_{i=0}^m(-1)^{x-i}{x\choose i}f(i)\\ =\sum_{i=0}^m(-1)^{x-i}\frac{x!}{(i)!(x-i)!}f(i)\\ =x!\times \sum_{i=0}^m\frac{f(i)}{(i)!}\cdot\frac{(-1)^{x-i}}{(x-i)!} \]

卷积即可求出 \(s\) ，将 \(f(x)=\sum_{i=0}^m\limits s_i{x\choose i}\) ，代入原式中，有：

\[∑_{k=0}^{n}\limits f(k)\binom nkx^k(1?x)^{n?k}=∑_{k=0}^{n}\limits \sum_{i=0}^m\limits s_i{k\choose i}\binom nkx^k(1?x)^{n?k}\\ =∑_{k=0}^{n}\limits \sum_{i=0}^m\limits s_i{n-i\choose k-i}\binom nix^k(1?x)^{n?k}\\ =\sum_{i=0}^m\limits s_i\binom ni∑_{k=0}^{n-i}\limits {n-i\choose k}x^{k+i}(1?x)^{n?k-i}\\ =\sum_{i=0}^m\limits s_i\binom nix^i∑_{k=0}^{n-i}\limits {n-i\choose k}x^{k}(1?x)^{n?k-i}\\ =\sum_{i=0}^m\limits s_i\binom nix^i(1)^{n-i}\\ =\sum_{i=0}^m\limits s_i\binom nix^i\\ \]

点击查看代码

CF961G Partitions

给出 \(n\) 个物品，每个物品有一个权值 \(w_i\) ，定义一个集合 \(S\) 的权值 \(W(S)=|S|\sum\limits_{x\in S}w_x\) 。

定义一个划分的权值为 \(W'(R)=\sum\limits_{S\in R}W(S)\) ，求将 \(n\) 个物品划分成 \(k\) 个集合的所有方案的权值和。

考虑每个物品的贡献，对于每种方案，它都会和自己产生 \(w_i\times\Large{n\brace k}\) 的贡献，另外，对于剩下 \(n-1\) 个物品的每种划分方案，它都可以和每个物品产生贡献，共计 \(w_i\times(n-1)\times \Large{n-1\brace k}\)

我们要求的就是：

\[\sum_{i=1}^{n}w_i\times({n\brace k}+(n-1)\times {n-1\brace k}) \]

有容斥公式：

\[{n\brace k}=\frac{1}{k!}\sum_{i=0}^k(-1)^{k}{k\choose i}(k-i)^{n} \]

\(O(n+k)\) 求解即可。

点击查看代码

[国家集训队] Crash 的文明世界

给定一棵树，对于每个点 \(x\)，求 \(\sum_{i=1}^n\limits dist(i,x)^k\) 。

做法1.

直接维护 \(0\) ~ \(k\) 次方的和单次转移是 \(k^2\) 的吗，考虑维护 \(0\) ~ \(k\) 次下降幂。

转移时考虑到：

\[(d+1)^{\underline{i}}=(d+1)\times d^{\underline{i-1}}\\ =(d-i+1+i)\times d^{\underline{i-1}}\\ =(d-i+1)\times d^{\underline{i-1}}+i\times d^{\underline{i-1}}\\ =d^{\underline{i}}+i\times d^{\underline{i-1}} \]

因此，考虑转移 \(u\to x\)，有：

\[dp[x][i]=\sum_{u\to x}dp[u][i]+i\times dp[u][i-1] \]

最终答案为：

\[ans[x]=\sum_{i=0}^k {k\brace i}dp[x][i] \]

做法2.

对每个 \(x\) ，对于 \(j\in [0,k]\) 维护:

\[\sum_{i=1}^{n}\limits {dist(i,x)\choose j} \]

考虑到：

\[{n+1\choose m}={n\choose m}+{n\choose m-1} \]

有转移：

\[dp[x][i]=\sum_{u\to x}dp[u][i]+dp[u][i-1] \]

最终答案为：

\[ans[x]=\sum_{i=0}^k i!{k\brace i}dp[x][i] \]

点击查看代码

[HEOI2016/TJOI2016]求和

计算：

\[f(n)=\sum_{i=0}^n\sum_{j=0}^n {i\brace j}\times 2^j \times j! \]

有：

\[f(n)=\sum_{i=0}^n\sum_{j=0}^n\frac{1}{j!}\sum_{t=0}^j(-1)^t{j\choose t}(j-t)^i \times 2^j \times j!\\ =\sum_{i=0}^n\sum_{j=0}^n\sum_{t=0}^j(-1)^t{j\choose t}(j-t)^i \times 2^j \\ =\sum_{i=0}^n\sum_{j=0}^n\sum_{t=0}^j(-1)^t\times\frac{j!}{t!(j-t)!}\times (j-t)^i \times 2^j \\ =\sum_{j=0}^n\sum_{t=0}^j\frac{(-1)^t}{t!}\times\frac{\sum_{i=0}^n(j-t)^i}{(j-t)!}\times j! \times 2^j \\ =\sum_{j=0}^nj! \times 2^j\sum_{t=0}^j\frac{(-1)^t}{t!}\times\frac{\sum_{i=0}^n(j-t)^i}{(j-t)!} \\ \]

点击查看代码

CF932E Team Work

求：

\[ \sum_{i=1}^n\binom n i \times i^k \]

有：

\[\sum_{i=1}^n\binom n i \times i^k=\sum_{i=1}^n\binom n i \times \sum_{j=0}^k{k\brace j} i^{\underline{j}}\\ =\sum_{j=0}^k{k\brace j}\sum_{i=1}^n\binom n i \times i^{\underline{j}}\\ =\sum_{j=0}^k{k\brace j}\sum_{i=1}^n\frac{n!}{i!(n-i)!} \times \frac{i!}{(i-j)!}\\ =\sum_{j=0}^k{k\brace j}\sum_{i=1}^n\frac{n!}{(n-i)!(i-j)!}\\ =\sum_{j=0}^k{k\brace j}n^{\underline{j}}\sum_{i=1}^n\frac{(n-j)!}{(n-i)!(i-j)!}\\ =\sum_{j=0}^k{k\brace j}n^{\underline{j}}\sum_{i=1}^n{n-j\choose n-i}\\ =\sum_{j=0}^k{k\brace j}n^{\underline{j}}\times 2^{n-j}\\ \]

点击查看代码