有关斯特林数

一些定义:

$x^\overline{k}=x^{k \uparrow}=\prod_{i=0}^{k-1}(x+i)=x(x+1)(x+2)…(x+k-1)$

$x^\underline{k}=x^{k \downarrow}=\prod_{i=0}^{k-1}(x-i)=x(x-1)(x-2)…(x-k+1)$

第一类斯特林数:

$\begin{bmatrix}n\\m\end{bmatrix}=s_u(n,m)=s(n,m)$

表示将n个元素分布到m个环上(环非空),元素互异,环不互异的方案数

可得递推式

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

其中$\begin{bmatrix}0\\0\end{bmatrix}=1$

$s_s(n,m)=(-1)^{n+m}s_u(n,m)$

第二类斯特林数:

$\begin{Bmatrix}n\\m\end{Bmatrix}=S(n,m)$

表示将n个元素放进m个集合中(集合非空),元素互异,集合不互异的方案数

可得递推式

$\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix}n-1\\m\end{Bmatrix}$

其中$\begin{Bmatrix}0\\0\end{Bmatrix}=0$

关于斯特林数的公式若干:

(1)$s_s(n,m)=s_s(n-1,m-1)-(n-1)s_s(n-1,m)$

$s_s(n,m)=(-1)^{n+m}s_u(n,m)$

$=(-1)^{n+m}(s_u(n-1,m-1)+(n-1)s_u(n-1,m))$

$=(-1)^{n+m}((-1)^{n+m}s_s(n-1,m-1)-(-1)^{n+m}(n-1)s_s(n-1,m))$

$=s_s(n-1,m-1)-(n-1)s_s(n-1,m)$

(2)$x^{\overline n}=\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i$

使用数学归纳法,对n进行归纳.

当n=0,1时显然成立

当n>1时,

$\begin{bmatrix}n\\0\end{bmatrix}=\begin{bmatrix}n-1\\0\end{bmatrix}=\begin{bmatrix}n-1\\n\end{bmatrix}=0​​$

$\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i=\sum_{i=1}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i$

$=\sum_{i=1}^{n}\left (\begin{bmatrix}n-1\\i-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\i\end{bmatrix}\right )x^i$

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

$=x\sum_{i=0}^{n-1}\begin{bmatrix}n-1\\i\end{bmatrix}x^i+(n-1)\sum_{i=0}^{n-1}\begin{bmatrix}n-1\\i\end{bmatrix}x^i$

$=(x+n-1)x^{\overline{n-1}}$

$=x^{\overline n}$

(3)$x^{\underline n}=\sum_{i=0}^{n}(-1)^{n+i}\begin{bmatrix}n\\i\end{bmatrix}x^i​$

同样使用数学归纳法

当n=0,1时显然成立

当n>1时,

$\sum_{i=0}^{n}(-1)^{n+i}\begin{bmatrix}n\\i\end{bmatrix}x^i=\sum_{i=1}^{n}(-1)^{n+i}\begin{bmatrix}n\\i\end{bmatrix}x^i$

$=\sum_{i=1}^{n}(-1)^{n+i}\left (\begin{bmatrix}n-1\\i-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\i\end{bmatrix}\right )x^i$

$=\sum_{i=1}^{n}(-1)^{n+i-2}\begin{bmatrix}n-1\\i-1\end{bmatrix}x^i-(n-1)\sum_{i=1}^{n}(-1)^{n-1+i}\begin{bmatrix}n-1\\i\end{bmatrix}x^i$

$=\sum_{i=0}^{n-1}(-1)^{n-1+i}\begin{bmatrix}n-1\\i\end{bmatrix}x^i-(n-1)\sum_{i=0}^{n-1}(-1)^{n+i-1}\begin{bmatrix}n-1\\i\end{bmatrix}x^i$

$=(x-n+1)x^{\underline{n-1}}$

$=x^{\underline n}$

(4)$x^n=\sum_{i=0}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline i}​$

继续使用数学归纳法…(今天怕是写公式要写吐…)

当n=0,1时显然成立

当n>1时,

$\begin{Bmatrix}n\\0\end{Bmatrix}=\begin{Bmatrix}n-1\\0\end{Bmatrix}=\begin{Bmatrix}n-1\\n\end{Bmatrix}=0$

$\sum_{i=0}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline i}=\sum_{i=1}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline i}$

$=\sum_{i=1}^{n}\left ( \begin{Bmatrix}n-1\\i-1\end{Bmatrix} +i\begin{Bmatrix}n-1\\i\end{Bmatrix}\right )x^{\underline i}$

$=\sum_{i=1}^{n}\begin{Bmatrix}n-1\\i-1\end{Bmatrix}x^{\underline i} +\sum_{i=1}^{n}i\begin{Bmatrix}n-1\\i\end{Bmatrix}x^{\underline i}$

$=\sum_{i=0}^{n-1}\begin{Bmatrix}n-1\\i\end{Bmatrix}x^{\underline {i+1}} +\sum_{i=0}^{n-1}i\begin{Bmatrix}n-1\\i\end{Bmatrix}x^{\underline i}$

$=\sum_{i=0}^{n-1}(x-i)\begin{Bmatrix}n-1\\i\end{Bmatrix}x^{\underline i} +\sum_{i=0}^{n-1}i\begin{Bmatrix}n-1\\i\end{Bmatrix}x^{\underline i}$

$=x\sum_{i=0}^{n-1}\begin{Bmatrix}n-1\\i\end{Bmatrix}x^{\underline i}$

$=xx^{n-1}$

$=x^n$

(5)$x^n=\sum_{i=0}^{n}(-1)^{n+i}\begin{Bmatrix}n\\i\end{Bmatrix}x^{\overline i}$

妈耶…我真的要吐了…

当n=0,1时,显然成立

当n>1时,

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

$=\sum_{i=1}^{n}(-1)^{n+i}\left ( \begin{Bmatrix}n-1\\i-1\end{Bmatrix} +i\begin{Bmatrix}n-1\\i\end{Bmatrix}\right )x^{\overline i}$

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

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

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

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

$=xx^{n-1}$

$=x^n$

(6)$\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^{m}(-1)^{m-i}\binom{m}{i}i^n$

终于可以不用数学归纳法了…虽然用数学归纳法也能证明

这里是假设有m-i个集合一定没有元素的一个容斥

先假设集合有标号,则有m-i个集合没有元素,则每个元素有i种选择方案

(7)斯特林反演

$f(n)=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}g(i)\Leftrightarrow g(n)=\sum_{i=0}^n(-1)^{n+i}\begin{bmatrix}n\\i\end{bmatrix}f(i)$

证明:

$\sum_{i=0}^n(-1)^{n+i}\begin{bmatrix}n\\i\end{bmatrix}f(i)$

$=\sum_{i=0}^n(-1)^{n+i}\begin{bmatrix}n\\i\end{bmatrix}\sum_{j=0}^i\begin{Bmatrix}i\\j\end{Bmatrix}g(j)$

$=\sum_{j=0}^ng(j)\sum_{i=j}^n(-1)^{n+i}\begin{bmatrix}n\\i\end{bmatrix}\begin{Bmatrix}i\\j\end{Bmatrix}$

考虑右边$\sum_{i=j}^n(-1)^{n+i}\begin{bmatrix}n\\i\end{bmatrix}\begin{Bmatrix}i\\j\end{Bmatrix}$的含义

表示将n个元素拼成i个环,再将i个环分到j个集合里,最后乘上$(-1)^{n+i}$

这个过程等价于先确定一个将n个元素划分到j个集合里,再将每一个集合的”集合内的元素拼环的有符号方案数和”乘起来.

考虑一个确定了的,有k个元素的集合$(k\geq 1)$的集合计算有符号方案数的和,答案应该为

$\sum_{i=0}^{k}(-1)^{k+i}\begin{bmatrix}k\\i\end{bmatrix}$

将x=1代入到公式3中,立得原式$=[k\leq1]$

所以当且仅当每一个集合中有且仅有一个元素,即j=n时,$\sum_{i=j}^n(-1)^{n+i}\begin{bmatrix}n\\i\end{bmatrix}\begin{Bmatrix}i\\j\end{Bmatrix}=1$,否则=0

所以原式$=g(n)$

斯特林反演的不同表达形式

$f(n)=\sum_{i=0}^n(-1)^{i}\begin{Bmatrix}n\\i\end{Bmatrix}g(i)\Leftrightarrow g(n)=\sum_{i=0}^n(-1)^{i}\begin{bmatrix}n\\i\end{bmatrix}f(i)$

$f(n)=(-1)^n\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}g(i)\Leftrightarrow g(n)=(-1)^n\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}f(i)$

$f(n)=\sum_{i=0}^n(-1)^{n+i}\begin{Bmatrix}n\\i\end{Bmatrix}g(i)\Leftrightarrow g(n)=\sum_{i=0}^n\begin{bmatrix}n\\i\end{bmatrix}f(i)$

例题:BZOJ2159(并不是斯特林反演)

《有关斯特林数》上有1条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注