数列（3）第一类斯特林数

# 第一类斯特林数（Stirling Number）

第一类斯特林数（斯特林轮换数）$\begin{bmatrix}n\\ k\end{bmatrix}$，也可记做 $s(n,k)$，表示将 $n$ 个两两不同的元素，划分为 $k$ 个互不区分的非空轮换的方案数。

一个轮换就是一个首尾相接的环形排列。我们可以写出一个轮换 $[A,B,C,D]$，并且我们认为 $[A,B,C,D]=[B,C,D,A]=[C,D,A,B]=[D,A,B,C]$，即，两个可以通过旋转而互相得到的轮换是等价的。注意，我们不认为两个可以通过翻转而相互得到的轮换等价，即 $[A,B,C,D]\neq[D,C,B,A]$。

# 递推式

$$\begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}$$

边界是 $\begin{bmatrix}n\\ 0\end{bmatrix}=[n=0]$。

该递推式的证明可以考虑其组合意义。

我们插入一个新元素时，有两种方案：

• 将该新元素置于一个单独的轮换中，共有 $\begin{bmatrix}n-1\\ k-1\end{bmatrix}$ 种方案；
• 将该元素插入到任何一个现有的轮换中，共有 $(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}$ 种方案。

根据加法原理，将两式相加即可得到递推式。

# 通项公式

第一类斯特林数没有实用的通项公式。

# 同一行第一类斯特林数的计算

类似第二类斯特林数，我们构造同行第一类斯特林数的生成函数，即

$F_n(x)=\sum\limits_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}x^i$

根据递推公式，不难写出

$F_n(x)=(n-1)F_{n-1}(x)+xF_{n-1}(x)$

于是

$F_n(x)=\prod\limits_{i=0}^{n-1}(x+i)=\dfrac{(x+n-1)!}{(x-1)!}$

这其实是 $x$ 的 $n$ 次上升阶乘幂，记做 $x^{\overline n}$。这个东西自然是可以暴力分治乘 $O(n\log^2n)$ 求出的，但用上升幂相关做法可以 $O(n\log n)$ 求出。

# 同一列第一类斯特林数的计算

仿照第二类斯特林数的计算，我们可以用指数型生成函数解决该问题。注意，由于递推公式和行有关，我们不能利用递推公式计算同列的第一类斯特林数。

显然，单个轮换的指数型生成函数为

$F(x)=\sum\limits_{i=1}^n\dfrac{(i-1)!x^i}{i!}=\sum\limits_{i=1}^n\dfrac{x^i}{i}$

它的 $k$ 次幂就是 $\begin{bmatrix}i\\k\end{bmatrix}$ 的指数型生成函数，$O(n\log n)$ 计算即可。

int main() {
  scanf("%d%d", &n, &k);
  fact[0] = 1;
  for (int i = 1; i <= n; ++i) fact[i] = (ll)fact[i - 1] * i % mod;
  ifact[n] = qpow(fact[n], mod - 2);
  for (int i = n - 1; i >= 0; --i) ifact[i] = (ll)ifact[i + 1] * (i + 1) % mod;
  poly f(n + 1);
  for (int i = 1; i <= n; ++i) f[i] = (ll)fact[i - 1] * ifact[i] % mod;
  f = exp(log(f >> 1) * k) << k, f.resize(n + 1);
  for (int i = 0; i <= n; ++i)
    printf("%lld ", (ll)f[i] * fact[i] % mod * ifact[k] % mod);
  return 0;
}

# 应用

# 上升幂与普通幂的相互转化

我们记上升阶乘幂 $x^{\overline{n}}=\prod_{k=0}^{n-1} (x+k)$。

则可以利用下面的恒等式将上升幂转化为普通幂：

$$x^{\overline{n}}=\sum_{k} \begin{bmatrix}n\\ k\end{bmatrix} x^k$$

如果将普通幂转化为上升幂，则有下面的恒等式：

$$x^n=\sum_{k} \begin{Bmatrix}n\\ k\end{Bmatrix} (-1)^{n-k} x^{\overline{k}}$$

# 下降幂与普通幂的相互转化

我们记下降阶乘幂 $x^{\underline{n}}=\dfrac{x!}{(x-n)!}=\prod_{k=0}^{n-1} (x-k)$。

则可以利用下面的恒等式将普通幂转化为下降幂：

$$x^n=\sum_{k} \begin{Bmatrix}n\\ k\end{Bmatrix} x^{\underline{k}}$$

如果将下降幂转化为普通幂，则有下面的恒等式：

$$x^{\underline{n}}=\sum_{k} \begin{bmatrix}n\\ k\end{bmatrix} (-1)^{n-k} x^k$$

# 多项式下降阶乘幂表示与多项式点值表示的关系

在这里，多项式的下降阶乘幂表示就是用

$$f(x)=\sum\limits_{i=0}^nb_i{x^{\underline{i}}}$$

的形式表示一个多项式，而点值表示就是用 $n+1$ 个点

$$(i,a_i),i=0..n$$

来表示一个多项式。

显然，下降阶乘幂 $b$ 和点值 $a$ 间满足这样的关系：

$$a_k=\sum\limits_{i=0}^{n}b_ik^{\underline{i}}$$

即

$$\begin{aligned} a_k&=\sum\limits_{i=0}^{n}\dfrac{b_ik!}{(k-i)!}\\\dfrac{a_k}{k!}&=\sum\limits_{i=0}^kb_i\dfrac{1}{(k-i)!} \end{aligned}$$

这是一个卷积形式的式子，我们可以在 $O(n\log n)$ 的时间复杂度内完成点值和下降阶乘幂的互相转化

# 例题链接

hdu 5625open in new window

# 题目概述

​ 每个仓库里面存放了一把钥匙(可能是打开这个仓库的,也可能是打假设最多可以强制打开k个仓库然后取到里面的钥匙,并且要求不能强制打开1号仓库,那么计算可以把所有仓库都打开的概率,保留4位小数.

# 一点想法

​ 首先考虑这样一个问题,就是n个仓库,如何能够打开k个仓库,拿到里面的钥匙,然后可以打开剩下其它的仓库的,很明显这个是当这n个仓库组成k个圆排列,然后从每个圆排列中暴力打开一个,取得钥匙,然后这个圆排列上的仓库都可以打开(此时每一个仓库放置的是它下一个仓库的钥匙),这个对应的就是第一类Stirling数.但是这个题目有一个要求,不能暴力打开1号仓库,所以1号仓库的钥匙只能这样放置,从n−1个仓库组成的k个排列中随机选择一个仓库放置1号钥匙,都可以通过先打开其他的仓库然后获得1号仓库的钥匙;但是对于n−1个仓库已经排成k−1个排列的情况,此时1号必须把它的钥匙放置到自身,但是自身又不能暴力打开,所以对于n个仓库不能暴力打开1号,至多先暴力打开kk个仓库获得钥匙然后打开其他仓库以便全部打开的要求,在已经计算出的第一类Stirling数s(n,k)上,要减去1号放置自身的情况,也就是s(n,k)−s(n−1,k−1).

​ 上面计算的是能够打开并且保证1号不被暴力打开的可能方法数,随机放置钥匙的总的方法数是n!n!,所以要计算概率,只要将可行的方法数除以总数就可以了,因为题目中要求的是至多打开k次,所以意味着使用1,2,…,k−1也要算作到至多k次里面.

# 注意

​ 我当时算第一类Stirling数的时候考虑到了不能算完一项后就直接减,因为递推式的计算依赖于前面两项,所以我就在算完整个后去减前面的项.,忘记了递推式后面的依赖于前面的,所言前面几个因为是0计算没改变,但是一旦遇到非0的,那么前面的结果就开始改变,对应后面的也开始改变

# 代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 30;
ll s[N][N];
ll ans[N][N];
ll f[N];

void calculate(){
    s[0][0] = 1;
    f[0] = 1;
    // 计算第一类Stirling数
    for (int i = 1; i < N; i++){
        for (int j = 0; j <= i; j++){
            // 第一类Stirling数递推式
            s[i][j] = (i-1) * s[i - 1][j] + s[i-1][j-1];
        }
        f[i] = f[i - 1] * i;
    }
    // 不能这样剔除，前面的改变后会影响后面剔除的结果。
    // for (int i = 1; i < N; i++){
    //     for (int j = 1; j <= i; j++){
    //         // 剔除没法打开1的情况
    //         s[i][j] -= s[i-1][j-1];
    //     }
    // }
    for (int i = 0; i < N; i++){
        for (int j = 1; j <= i; j++){
            ans[i][j] = ans[i][j - 1] + s[i][j] - s[i-1][j-1];
        }
    }
}

void print(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j <= i; j++){
            printf("%lld ", s[i][j]);
        }
        printf("\n");
    }
}
int main() {
    calculate();
    // print();
    int t;
    scanf("%d", &t);
    while (t--){
        int n, m;
        scanf("%d%d", &n, &m);
        printf("%.4f\n", 1.0 * ans[n][m] / f[n]);
    }
    return 0;
}