大家好，欢迎来到IT知识分享网。
斯特林(Stirling)数
斯特林数是组合数学中，关于子集划分和置换划分的一类问题的解。其中，分为第一类斯特林数和第二类斯特林数。
第一类斯特林数
[ n k ] {n \brack k} [kn] 表示 n n n个元素排成 k k k个轮换。这里的轮换是指：
例如存在轮换 [ 1 , 2 , 3 ] [1,2,3] [1,2,3]，那么意思就是存在三个相等序列 [ 1 , 2 , 3 ] = [ 2 , 3 , 1 ] = [ 3 , 1 , 2 ] [1,2,3]=[2,3,1]=[3,1,2] [1,2,3]=[2,3,1]=[3,1,2]。
特别的，一个元素的轮换只有他本身，因为 [ 1 ] [1] [1]单个元素只能和自己轮换。两个元素的轮换也只有一个，因为 [ 1 , 2 ] = [ 2 , 1 ] [1,2]=[2,1] [1,2]=[2,1]是同一个轮换。
一般来说，对于 [ n 1 ] {n \brack 1} [1n]，每一个 n n n个元素的全排列正好对应 n n n个轮换，因此根据除法原理：
[ n 1 ] = n ! n = ( n − 1 ) ! {n \brack 1} = \frac{n!}{n} = (n-1)! [1n]=nn!=(n−1)!
事实上，还容易看出：
[ n n ] = 1 {n \brack n} = 1 [nn]=1
[ n n − 1 ] = ( n 2 ) {n \brack n-1} = \binom{n}{2} [n−1n]=(2n)
对于最后一个等式，运用的鸽巢原理，相当于我们把 n n n个元素放进 n − 1 n-1 n−1个箱子里面，并且不能放空，那么必有两个元素在同一个箱子里面，因为有两个元素的那个箱子的轮换相等，所以我们不用做任何处理。
现在我们考虑第一类斯特林数的递推公式，考虑 n n n个元素最后一个元素 n n n，对于他的安放方式有两种。第一种自己单独成为一个轮换，方案数为 [ n − 1 k − 1 ] {n-1 \brack k-1} [k−1n−1]。第二种，插入前 n − 1 n-1 n−1个元素生成的 k k k个轮换中，方案数为 ( n − 1 ) [ n − 1 k ] (n-1){n-1 \brack k} (n−1)[kn−1]（对于每一个轮换，假如这个轮换的大小为 ∣ S ∣ |S| ∣S∣，那么插入一个元素变成一个新的轮换有 ∣ S ∣ |S| ∣S∣种方式，即可以在每一个元素前面插入而不重复，因为 ∑ ∣ S i ∣ = ( n − 1 ) \sum |S_i|=(n-1) ∑∣Si∣=(n−1)，故总共有 ( n − 1 ) (n-1) (n−1)种插入方式），因此，我们的递推公式为：
[ n k ] = [ n − 1 k − 1 ] + ( n − 1 ) [ n − 1 k ] {n \brack k} = {n-1 \brack k-1} + (n-1){n-1 \brack k} [kn]=[k−1n−1]+(n−1)[kn−1]
其中，我们认为：
[ 0 0 ] = 1 [ n 0 ] = 0 ( n > 0 ) {0 \brack 0} = 1 \\ {n \brack 0} = 0 (n \gt 0) [00]=1[0n]=0(n>0)
例题
看不到的火柴数
LeetCode 5762
设答案为 P ( n , k ) P(n,k) P(n,k)
我们考虑最后一个位置能看到或者不能看到。如果能看到那么长度为 n n n的火柴必定在最后一个位置，方案数为 P ( n − 1 , k − 1 ) P(n – 1,k – 1) P(n−1,k−1)。如果看不到，那么最后一个位置上的元素可以是前 [ 1 , n − 1 ] [1,n-1] [1,n−1]内的所有元素和元素 n n n做置换，相对大小不变，因此方案数为 ( n − 1 ) ∗ P ( n − 1 , k ) (n-1)*P(n-1,k) (n−1)∗P(n−1,k)。因此递推公式为：
P ( n , k ) = P ( n − 1 , k − 1 ) + ( n − 1 ) ∗ P ( n − 1 , k ) P(n,k) = P(n – 1,k – 1) + (n-1)*P(n-1,k) P(n,k)=P(n−1,k−1)+(n−1)∗P(n−1,k)
答案就是第一类斯特林数。 P ( n , k ) = [ n k ] P(n,k) = {n \brack k} P(n,k)=[kn]
高楼
HDU4372
我们枚举最高建筑 n n n的位置，他前面可以有 [ 0 , n − 1 ] [0,n-1] [0,n−1]个建筑，故答案为：
a n s = ∑ i = 0 n − 1 [ i f − 1 ] [ n − i − 1 b − 1 ] ( n − 1 i ) ans = \sum_{i = 0}^{n-1} {i \brack f – 1} {n – i – 1 \brack b – 1} \binom{n – 1}{i} ans=i=0∑n−1[f−1i][b−1n−i−1](in−1)
查询次数很多，这么做必定会超时。因此我们必须使用一个神奇的公式化简这个和式。
具体的，我们把最高建筑 n n n放在最后面，构造 [ n − 1 f + b − 2 ] {n – 1 \brack f + b – 2} [f+b−2n−1]，接着，然后把前面的 b − 1 b-1 b−1个圆排列移到后面去，因此答案为：
a n s = [ n − 1 f + b − 2 ] ( f + b − 2 b − 1 ) ans = {n – 1 \brack f + b – 2} \binom{f + b – 2}{b – 1} ans=[f+b−2n−1](b−1f+b−2)
这样，我们得到了一个很重要的公式：
[ n l + m ] ( l + m l ) = ∑ k [ k l ] [ n − k m ] ( n k ) {n \brack l + m} \binom{l + m}{l} = \sum_k {k \brack l}{n-k \brack m} \binom{n}{k} [l+mn](ll+m)=k∑[lk][mn−k](kn)
第二类斯特林数
第二类斯特林数 { n m } {n \brace m} {
mn}是指，将 n n n个不同的元素划分为 m m m个相同的非空集合的方案数。
有如下递推式子：
{ n m } = { n − 1 m − 1 } + { n − 1 m } × m {n \brace m} = {n-1 \brace m-1} + {n-1 \brace m} \times m {
mn}={
m−1n−1}+{
mn−1}×m
我们考虑最后一个元素的划分，第一种方式将最后一个元素单独放在一个集合中，需要将前 n − 1 n-1 n−1个元素划分成 m − 1 m-1 m−1个集合。第二种情况将最后一个元素插入到之前已经划分好的集合中，有 m m m中插入方式，插入到每个集合都是不同的，方案数为 { n − 1 m } × m {n-1 \brace m} \times m {
mn−1}×m。
P1655 模板
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define FR freopen("in.txt", "r", stdin) #define FW freopen("out.txt", "w", stdout) struct Decimal {
int bits[500]; int tot; Decimal() : Decimal(0) {
} Decimal(int init) : tot(0) {
fill(bits, bits + 500, 0); if (init == 0) {
tot = 1; return; } for (; init; init /= 10) {
bits[tot++] = init % 10; } } Decimal operator+(Decimal o) {
Decimal ans(0); int i = 0; for (; i < max(tot, o.tot); i++) {
ans.bits[i] += bits[i] + o.bits[i]; ans.bits[i + 1] += ans.bits[i] / 10; ans.bits[i] %= 10; } ans.tot = ans.bits[i] == 0 ? i : i + 1; return ans; } Decimal operator*(Decimal o) {
Decimal ans(0); for (int i = 0; i < tot; i++) {
for (int j = 0; j < o.tot; j++) {
ans.bits[i + j] += bits[i] * o.bits[j]; ans.bits[i + j + 1] += ans.bits[i + j] / 10; ans.bits[i + j] %= 10; } } int t = tot + o.tot - 1; while (ans.bits[t] == 0) t--; ans.tot = t + 1; return ans; } Decimal operator*(int k) {
Decimal fact(k); return (*this) * fact; } void output() {
for (int i = tot - 1; i >= 0; i--) {
putchar(bits[i] + '0'); } putchar('\n'); } }; Decimal stir[105][105]; int main() {
stir[0][0] = Decimal(1); for (int n = 1; n <= 101; n++) {
for (int m = 1; m <= min(101, n); m++) {
stir[n][m] = stir[n - 1][m - 1] + stir[n - 1][m] * m; } } int N, M; while (scanf("%d %d", &N, &M) != EOF) {
stir[N][M].output(); } return 0; } 免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/138366.html
