首页 > 其他分享 >【3】斯特林数

【3】斯特林数

时间:2024-08-30 19:36:31浏览次数:6  
标签:begin end dbinom limits 斯特林 sum Bmatrix

除了组合数、卡特兰数之外,最重要的一类特殊数便是斯特林数。

1.1 第二类斯特林数

斯特林数通常有两种,分别为第一类斯特林数和第二类斯特林数,后者通常更为重要。

与组合数类似,第二类斯特林数也有自己的符号 $ \begin{Bmatrix}n \ m\end{Bmatrix}$,其含义为把 \(n\) 个不同的数划分到 \(m\) 个非空集合中的方案数。

我们首先从递推的角度考虑怎么计算第二类斯特林数,我们考虑第 \(n\) 个数的划分情况:

  • 单独分到一个集合,\(\begin{Bmatrix}n-1 \\ m-1\end{Bmatrix}\)。
  • 加入某个集合,$ m\begin{Bmatrix}n-1 \ m\end{Bmatrix}$。

那么我们得到 $ \begin{Bmatrix}n \ m\end{Bmatrix}=\begin{Bmatrix}n-1 \ m-1\end{Bmatrix}+m\begin{Bmatrix}n-1 \ m\end{Bmatrix}$。

于是可以得到 \(\Theta(n^2)\) 的递推公式。

那么,第二类斯特林数有没有通项公式呢?

首先,因为集合之间没有区别,我们不妨让集合也有区别,这样方案数就变成了 \(m!\begin{Bmatrix}n \\ m\end{Bmatrix}\)。

另一方面,我们要求所有集合非空,那么可以考虑容斥, 钦定若干集合为空的,剩下的任意。

那么可以得到一个计算式:

\[m!\begin{Bmatrix}n \\ m\end{Bmatrix}=\sum\limits_{i=0}^m\dbinom{m}{i}(-1)^i(m-i)^n \]

这样便可以得到第二类斯特林数的通项公式,只不过求单个只能 \(\Theta(m)\)。

另一方面,我们有下面这个式子:

\[m^n=\sum\limits_{i=0}^m\dbinom{m}{i}{\begin{Bmatrix}n \\ i\end{Bmatrix}}i! \]

其含义为,左边为把 \(n\) 个不同的球装进 \(m\) 个不同的盒子里的方案数,右边是枚举非空的盒子数量,然后乘上第二类斯特林数,并且因为盒子不同,要再乘上 \(i!\)。

更进一步的,上面的式子可以看成下面的式子做二项式反演得到的。

同时,因为 \(\dbinom{m}{i}i!=m^{\underline{i}}\),且 \(i\) 要 \(\leq n\) 才有意义,所以上式可以改写为:

\[x^n=\sum\limits_{i=0}^n\begin{Bmatrix} n \\i \end{Bmatrix}x^{\underline{i}} \]

这样我们就得到了把普通幂转化为下降幂的方法。

自然数幂和问题

给定 \(n,m\),求 \(\sum\limits_{i=0}^ni^m\)。

\[\sum\limits_{i=0}^ni^m=\sum\limits_{i=0}^n\sum\limits_{j=0}^m\begin{Bmatrix} m \\j \end{Bmatrix}i^{\underline{j}} \]

\[=\sum\limits_{j=0}^m \begin{Bmatrix} m \\j \end{Bmatrix}\sum\limits_{i=0}^ni^{\underline{j}} \]

下降幂和组合数的性质很相近啊,我们不妨用上指标求和推一推:

\[\sum\limits_{i=0}^ni^{\underline{k}}=k!\sum\limits_{i=0}^n\dbinom{i}{k}=k!\dbinom{n+1}{k+1}=k!\frac{(n+1)!}{(k+1)!(n-k)!}=\frac{(n+1)^{\underline{k+1}}}{k+1} \]

那么原式等于:

\[=(n+1)\sum\limits_{j=0}^m\begin{Bmatrix} m \\j \end{Bmatrix}\frac{n^{j}}{j+1} \]

复杂度 \(\Theta(m^2)\),瓶颈在于预处理第二类斯特林数。

CF932E Team Work

\[\sum\limits_{i=0}^n\dbinom{n}{i}i^m=\sum\limits_{j=0}^m\begin{Bmatrix} m \\j \end{Bmatrix}\sum\limits_{i=0}^n\dbinom{n}{i}i^{\underline{j}} \]

\[=\sum\limits_{j=0}^m\begin{Bmatrix} m \\j \end{Bmatrix}j!\sum\limits_{i=0}^n\dbinom{n}{i}\dbinom{i}{j} \]

\[=\sum\limits_{j=0}^m\begin{Bmatrix} m \\j \end{Bmatrix}j!\dbinom{n}{j}\sum\limits_{i=0}^{n-j}\dbinom{n-j}{i-j} \]

\[=\sum\limits_{j=0}^m\begin{Bmatrix} m \\j \end{Bmatrix}j!\dbinom{n}{j}2^{n-j} \]

复杂度 \(\Theta(m^2)\)。

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

\[\sum\limits_{k=0}^n\sum\limits_{j=0}^mf_jk^{j}x^{k}\dbinom{n}{k} \]

\[\sum\limits_{j=0}^mf_j\sum\limits_{k=0}^n\sum\limits_{p=0}^{j}\begin{Bmatrix} j \\p \end{Bmatrix}k^{\underline{p}}x^{k}\dbinom{n}{k} \]

\[\sum\limits_{j=0}^mf_j\sum\limits_{p=0}^{j}\begin{Bmatrix} j \\p \end{Bmatrix}p!\sum\limits_{k=0}^n\dbinom{k}{p}\dbinom{n}{k}x^{k} \]

\[\sum\limits_{j=0}^mf_j\sum\limits_{p=0}^{j}\begin{Bmatrix} j \\p \end{Bmatrix}p!\dbinom{n}{p}\sum\limits_{k=0}^n\dbinom{n-p}{k-p}x^{k} \]

\[\sum\limits_{j=0}^mf_j\sum\limits_{p=0}^{j}\begin{Bmatrix} j \\p \end{Bmatrix}p!\dbinom{n}{p}\sum\limits_{k=0}^{n-p}\dbinom{n-p}{k}x^{k+p} \]

\[\sum\limits_{j=0}^mf_j\sum\limits_{p=0}^{j}\begin{Bmatrix} j \\p \end{Bmatrix}p!\dbinom{n}{p}x^{p}\sum\limits_{k=0}^{n-p}\dbinom{n-p}{k}x^{k} \]

\[\sum\limits_{j=0}^mf_j\sum\limits_{p=0}^{j}\begin{Bmatrix} j \\p \end{Bmatrix}p!\dbinom{n}{p}x^{p}(1+x)^{n-p} \]

复杂度 \(\Theta(m^2)\)。

练习一 CF1278F Cards

此外有很多题是根据组合数的组合意义进行优化。

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

\[ans_x=\sum\limits_{i=1}^ndis(i,x)^k=\sum\limits_{i=1}^n\sum\limits_{j=0}^k \begin{Bmatrix} k \\j \end{Bmatrix}j!\dbinom{dis(i,x)}{j}=\sum\limits_{j=0}^k \begin{Bmatrix} k \\j \end{Bmatrix}j!\sum\limits_{i=1}^n\dbinom{dis(i,x)}{j} \]

考虑组合意义,在所有点到 \(x\) 的路径上选了 \(j\) 条边的方案数之和,那么容易设计一个 dp,\(f_{x,i}\) 为 \(x\) 子树内,所有路径上选出 \(i\) 条边的方案数之和,转移是容易的。

之后只需要换根 DP 求出每个点的答案就行,复杂度 \(\Theta(nk)\)。

练习二 P8362 [SNOI2022] 数位

1.2 第一类斯特林数

第一类斯特林数被表示为 \(\begin{bmatrix}n \\ m\end{bmatrix}\),其含义为把 \(n\) 个不同元素扔到 \(m\) 个环上的方案数,即有 \(m\) 个置换环的 \(n\) 元排列个数。

与之前类似,我们还是考虑新加入一个元素,也是有两种情况:

  • 单独构成一个环,\(\begin{bmatrix}n-1 \\ m-1\end{bmatrix}\)
  • 插入之前的某个元素后面,\((n-1)\begin{bmatrix}n-1 \\ m\end{bmatrix}\)

于是也得到了 \(\Theta(n^2)\) 的递推公式。

[FJOI2016] 建筑师

模板题,按照组合意义推即可。

1.3 斯特林反演

与下降幂类似,我们定义上升幂 \(x^{\overline{n}}=\prod\limits_{i=0}^{n-1}(x+i)\),那么就有如下两个公式:

  • \[x^{\overline{n}}=\sum\limits_{i=0}^n\begin{bmatrix} n \\i \end{bmatrix}x^{i} \]

  • \[x^{\underline{n}}=\sum\limits_{i=0}^n(-1)^i\begin{bmatrix} n \\i \end{bmatrix}x^{i} \]

证明比较复杂且不太重要。

结合前面的我们一共有四个高度相似的公式:

  • \[x^n=\sum\limits_{i=0}^n\begin{Bmatrix} n \\i \end{Bmatrix}x^{\underline{i}} \]

  • \[x^n=\sum\limits_{i=0}^n(-1)^i\begin{Bmatrix} n \\i \end{Bmatrix}x^{\overline{i}} \]

  • \[x^{\overline{n}}=\sum\limits_{i=0}^n\begin{bmatrix} n \\i \end{bmatrix}x^{i} \]

  • \[x^{\underline{n}}=\sum\limits_{i=0}^n(-1)^i\begin{bmatrix} n \\i \end{bmatrix}x^{i} \]

这个公式也很好记,我们认为上升幂>普通幂>下降幂,那么:

  • 从两边(上升幂,下降幂)到中间(普通幂)用第二类斯特林数,从中间到两边用第一类斯特林数。
  • 从小的到大的要带 \((-1)^i\),从大的到小的不需要。

此外还有 斯特林反演 公式:

\[f(n)=\sum\limits_{i=0}^n\begin{Bmatrix} n \\i \end{Bmatrix}g(i)\Leftrightarrow g(n)=\sum\limits_{i=0}^n(-1)^i\begin{bmatrix} n \\i \end{bmatrix}f(i) \]

P10591 BZOJ4671 异或图

我们钦定出 \(i\) 个连通块,满足连通块之间没边,连通块内部随意,这样子的方案数是 \(g_i\)。

如果恰好有 \(i\) 个连通块的方案数是 \(f_i\),那么考虑 \(f\) 与 \(g\) 的关系,因为 \(g\) 的每个连通块实际可能是由若干连通块构成的,那么就是把 \(f\) 的若干连通块分到一个 \(g\) 的连通块里,这个方案数就是第二类斯特林数。

\[g_i=\sum\limits_{j=i}^n\begin{Bmatrix} j \\i \end{Bmatrix}f_j\Leftrightarrow f_i=\sum\limits_{j=i}^n(-1)^{j-i}\begin{bmatrix} j \\i \end{bmatrix}g_j \]

最终求的就是 \(f_1\),因此我们需要求出 \(g_1,g_2\dots g_n\)。

直接枚举钦定出来的连通块,这个复杂度是 \(n\)的贝尔数 ,那么限制就是连通块之间每条边的出现次数是偶数。我们可以列出一些关于图是否选择的异或方程,那么求出线性基之后这个方案数就是 \(2\) 的自由元个数次方。

综合题目 CF961G Partitions

更综合的题目 [ARC138E] Decreasing Subsequence

标签:begin,end,dbinom,limits,斯特林,sum,Bmatrix
From: https://www.cnblogs.com/jesoyizexry/p/18389396

相关文章

  • 斯特林数学习笔记
    定义第二类斯特林数\(n\bracem\)表示\(n\)个两两不同的元素划分为\(m\)个互不区分的非空子集的方案数;第一类斯特林数\(n\brackm\)表示\(n\)个两两不同的元素划分为\(m\)个互不区分的非空轮换(可以理解为环)的方案数。第二类斯特林数的递推式:\({n\bracem}={n-1\bra......
  • 卡特兰数和斯特林数
    感觉这几个东西挺常用,记录一下吧。1.卡特兰数假如我们定义\(C_n\)表示第\(n\)个卡特兰数。然后我们就有一下几个式子。\(C_n=\dfrac{\dbinom{2n}{n}}{n+1}\)\(C_n=\begin{cases}\sum^n_{i=1}H_{i-1}H_{n-i}\\n\ge2\\1\end{cases}\)\(C_n=\dbin......
  • 下降幂及斯特林数杂谈
    定义第一类斯特林数\[c(n,k)=|s(n,k)|=(-1)^{n-k}s(n,k)\]给出定义:\[x^{\barn}=\sum_{k=0}^kc(n,k)x^k\\x^{\underlinen}=\sum_{k=0}^ns(n,k)x^k=\sum_{k=0}^n(-1)^{n-k}c(n,k)x^k\]通常把\(c(n,k)\)称为无标号第一类斯特林数,\(s(n,k)\)称为有标号第一类斯特林数。......
  • CF1278F Cards(斯特林数+二项式定理)
    题意简述有\(m\)张牌,其中有一张是王牌。你现在可以洗\(n\)次牌(每种牌堆序列等概率出现),然后查看牌堆顶的第一张牌。设\(x\)为\(n\)次洗牌中第一张牌是王牌的次数,则得分为\(x^k\)。求得分的期望值对\(998244353\)取模的值。\(1\len,m<998244353,k\le5000\)分析将......
  • 斯特林数
    妈妈生的,这个东西在模拟赛里把我干爆了。记录一些简单的内容,并不会有超纲的多项式。第二类斯特林数\(\begin{Bmatrix}n\\k\end{Bmatrix}\)表示第二类斯特林数,也可记作\(S(n,k)\),组合意义是把\(n\)个不同元素划分成\(k\)个互不区分的子集的方案数。显然有递推式:\[S(n,k......
  • 斯特林数
    第一类斯特林数:\([^n_k]\):把\(n\)个数放入\(k\)个环中,本质不同的方案数。(要求每个环非空,环之间不区分,环可旋转)\([^n_k]=(n-1)[^{n-1}_k]+[^{n-1}_{k-1}]\)。\(\displaystyle\sum_{k=0}^n[^n_k]=n!\)。第二类斯特林数:\(\{^n_k\}\):把\(n\)个数放入\(k\)个盒中,本质不同......
  • [省选联考 2020 A 卷] 组合数问题(斯特林数)
    题面计算\[\left(\sum_{k=0}^{n}f(k)\timesx^k\times\binom{n}{k}\right)\bmodp\]的值。思路因为模数为合数,不能求逆元,要把组合数的分母消掉。\(x^k\)似乎不能做什么,\(f(k)\)的操作空间似乎很大首先将\(f(k)=\sum_{i=0}^{m}a_ix^i\)转化为\(f(k)=\sum_{i=0}^{m}b_ix^......
  • 斯特林数相关
    定义第一类斯特林数:\({n\brackk}\),指将\(n\)个数放入\(k\)个环中(环无区分)的方案数。第二类斯特林数:\({n\bracek}\),指将\(n\)个数放入\(k\)个盒子(盒子无区分)的方案数。递推式:\[{n\brackk}=(n-1){n-1\brackk}+{n-1\brackk-1}\]说明:我们考虑最后一个数......
  • 斯特林数
    第二类斯特林数定义:第二类斯特林数\(\begin{Bmatrix}n\\k\end{Bmatrix}\),表示将\(n\)个两两不同的元素,划分为\(k\)个互不区分的非空子集的方案数量。比如\(\begin{Bmatrix}a_{1},a_{2},a_{3}\end{Bmatrix}\)只能划分成\(\begin{Bmatrix}a_{1}\end{Bmatrix}\),\(\begi......
  • 卡特兰数&斯特林数
    卡特兰数引入不妨从找规律开始。下标从\(0\)开始,卡特兰数的前几项为:1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790…那么通过认真的瞪眼观察,会发现它们满足递推关系。关于卡特兰数是一个很常见的数列。它并没有一个足够......