最近做題有時會碰到斯特林?jǐn)?shù)（Stirling數(shù)），就覺得好好的學(xué)習(xí)一番，于是呢，寫下這篇博客，來記錄一些知識

簡單介紹

第一類斯特林?jǐn)?shù)表示表示將 n 個不同元素構(gòu)成m個圓排列的數(shù)目。——百度百科

第一類斯特林?jǐn)?shù)，可以表示為$s(n,m)$，注意這里是小寫
，要與大寫的第二類斯特林?jǐn)?shù)區(qū)分開來，定義上面也講到了，但是呢，其實那句話最好改成第一類斯特林?jǐn)?shù)的絕對值，因為第一類斯特林?jǐn)?shù)是分正負(fù)的，分為無符號斯特林?jǐn)?shù)$s_u(n,m)$和有符號斯特林?jǐn)?shù)$s_s(n,m)$

有無符號Stirling數(shù)分別表現(xiàn)為其升階函數(shù)和降階函數(shù)的各項系數(shù)[類似于二項式系數(shù)]，形式如下：
$$x^{n\downarrow }=x(x?1)(x?2)???(x?n+1)=\sum _{k=0}^n{s}_s(n,k)x^k$$
$$x^{n\uparrow }=x(x+1)(x+2)???(x+n?1)=\sum _{k=0}^n{s}_u(n,k)x^k$$

這是一個很煩的式子，但其實呢，有符號和無符號斯特林?jǐn)?shù)之間的關(guān)系其實很簡單$s_s(n,m)=(?1{)}^{n+m}{s}_u(n,m)$
另外，這個式子的推導(dǎo)可以見我的另一篇博客：第二類斯特林?jǐn)?shù)學(xué)習(xí)記錄

計算公式

第一類斯特林?jǐn)?shù)有個遞推式很好想
想一下對于$s_u(n,m)$
若$n=0$，$m=0$那么顯然就一種方案
若$n?=0$，$m=0$那么肯定分配不了，有0種方案
若$n?=0$，$m?=0$
那么考慮轉(zhuǎn)移
倘若由$s_u(n?1,m?1)$轉(zhuǎn)移而來，則說明新來的一個點自成一個環(huán)只有一倍的貢獻(xiàn)
倘若由$s_u(n?1,m)$轉(zhuǎn)移而來，則說明新來的一個點插入到m個環(huán)中的n-1個空格的任何一個位置，那么就有n-1倍的貢獻(xiàn)，遞推式為$s_u(n,m)=s_u(n?1,m?1)+(n?1)?s_u(n?1,m)$
有符號的第一類斯特林?jǐn)?shù)的遞推式為$s_s(n,m)=s_s(n?1,m?1)?(n?1)?s_s(n?1,m)$
證明是前面那個公式$$\sum _{k=0}^{n}s(n,k)x^k=x^{n\downarrow }=x^{n?1\downarrow }?(x?n+1)=\sum _{k=0}^{n?1}s(n?1,k)x^{k+1}?n?\sum _{k=0}^{n?1}s(n?1,k)x^k$$
依次把$x^m$在左右兩邊的系數(shù)提取出來得到
另外有這個式子：（證明在第二類斯特林?jǐn)?shù)的博客里）
$$x^{n\downarrow }=\sum _{i=0}^n{\left[\begin{array}{c}n\\ i\end{array}\right]}_s{x}^i$$
我們可以通過這個公式在$\Theta (nlo{g}^{2}n)$的復(fù)雜度內(nèi)用分治+FFT求出某個$n$對應(yīng)的所有$s_u(n,m)$值

性質(zhì)

除了一些比較容易想到的性質(zhì)外，第一類斯特林?jǐn)?shù)還有如下性質(zhì)
$$s_u(n,2)=(n?1)!?\sum _{i=1}^{n?1}\frac{1}{i}$$
$$\sum _{k=0}^n{s}_u(n,k)=n!$$
容易發(fā)現(xiàn)，每一個排列都對應(yīng)著一個輪換（相當(dāng)于i到ai連一條邊的一副圖），然后枚舉輪換里環(huán)的數(shù)量就好了

應(yīng)用

第一類斯特林?jǐn)?shù)是一種在組合方面比較有用的數(shù)，很多問題都可通過它來解決，熟悉它的性質(zhì)，才能熟練的運用到公式推導(dǎo)的過程中去

總結(jié)

以上是生活随笔為你收集整理的第一类斯特林数学习记录的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。