摘要：斯特林数第一斯特林数是第一斯特林数，它表示将不同元素划分为圆形排列的方案的数量。对于递减幂和组合数，有一些公式[inom｛n｝｛k｝k^｛下划线｛m｝｝=inom｛n-m｝{k-m｝n^｛underline｛m}｝]P4609[FJIO2016]建筑师考虑列举高度建筑物的位置。inom｛n｝｛j｝sum｛i＝j｝^｛n}inom{n-j｝{n-i｝&提出了一个组合数&＝sum{j＝1｝^{k｝{kracej｝j！Inom｛n｝｛j｝m^｛n-j｝&二项式定理结束｛对齐｝代码：https://codeforces.com/contest/1278/submission/107342990P6620【省选联考第2020A卷】一种与降幂无关的组合数问题的解决方法｛n｝｛j｝x ^｛j}（x+1）^｛n-j｝端｛对齐｝]但里面有一个组合数字，这不容易处理。。。考虑使用公式将阶乘乘以组合数更改为较低的降序。最好一开始就使用较低的功率。我们有一个多项式来转换低次多项式[b_i=sum_{j=i}^{m}{jracei}a_jf=sum_{i=0}^{m}b_ix^{underline{i}}][egin{aligned}ys&=sum_{i=0}^{m}b_isum_{k=i}^｛n}x^kk^{underline{i}}inom{i}{k}&转换低次函数&=sum_{i=0}^{m}b_isum_{k=i}^{n}x^ i｝inom｛n-i｝｛k-i｝&下降幂和组合数&=sum｛i＝0｝^｛m｝b_in ^｛下划线｛i｝x ^｛i}sum_｛k＝0｝^｛n-i｝x^｛k｝inom｛n-i｝｛k-i｝\&＝sum｛i＝0｝｝^｝m｝｝b_ in ^｛｛下划线｝i｝｝x（x+1）^｛n｝end｛aligned
Stirling 数
第一类斯特林数
({nrack m}) 为第一类斯特林数，表示将 (n) 个不同元素划分为 (k) 个圆排列的方案数。
有递推式
[{nrack m}={n-1rack k-1}+(n-1){n-1rack k} ]
第二类斯特林数
({nrace m}) 为第二类斯特林数，表示将 (n) 个不同元素划分为 (k) 个非空子集的方案数。
有递推式和通项式
[{nrace m}={n-1race k-1}+k{n-1race k}\ {nrace m}=sum_{i=0}^{m} frac{(-1)^{m-i}i^n}{i!(m-i)!} ]
上升幂和下降幂
上升幂和下降幂的定义
[x^{overline{n}}=prod_{k=0}^{n-1} (x+k)\ x^{underline{n}}=prod_{k=0}^{n-1} (x-k) ]
斯特林数可以把上升/下降幂和普通幂结合起来
[x^{overline{n}}=sum_{k} {nrack k} x^k\ x^n=sum_{k}{nrace k} (-1)^{n-k} x^{overline{k}}\ x^n=sum_{k} {nrace k} x^{underline{k}}\ x^{underline{n}}=sum_{k}{nrack k} (-1)^{n-k} x^k ]
还有阶乘
[n^k=sum_{i=1}^k inom{n}{i} {krace i} i! ]
从上升/下降幂转到普通幂用的是第二类，否则用的是第一类。
关于下降幂和组合数，有一些式子
[inom{n}{k} k^{underline{m}}=inom{n-m}{k-m} n^{underline{m}} ]
P4609 [FJOI2016]建筑师
考虑枚举高度为 (n) 的建筑放在哪里。这样就把左边和右边切开了，分成独立的两块。我们不妨考虑左边的情况（右边本质是相同的）
(f(i,j)) 表示 (i) 个建筑，从左向右看能看到 (j) 个建筑的方案数。
[f(i,j)=f(i-1,j-1)+(i-1) imes f(i-1,j) ]
这是第一类斯特林数的递推式。
考虑左右两个答案合并起来。
[ans=sum_{i=1}^{n} inom{n-1}{i-1} {i-1rack A-1} {n-irack B-1} ]
这东西可以变成（具体数学 P221 6.29）
[ans=inom{A+B-2}{A-1} {n-1rack A+B-2} ]
具体理解为把左右两边的圆排列合起来考虑，即 (n-1) 个数中选取 (A+B-2) 个圆排列，然后分 (A-1) 个到左边，(A+B-2) 个到右边。
code: https://www.luogu.com.cn/record/46537669
CF932E Team Work
[egin{aligned} ys &= sum_{i=1}^{n} inom{n}{i} sum_{j=1}^{k} {krace j} j! inom{i}{j} & 幂 o阶乘\ &= sum_{j=1}^{k} {krace j} j! sum_{i=j}^{n} inom{n}{i} inom{i}{j} & 交换求和号\ inom{n}{i} inom{i}{j} &= frac{n! i!}{i! (n-i)! j! (i-j)!}\ &= frac{n!}{(n-j)! j!} frac{(n-j)!}{(n-i)! (i-j)!}\ &= inom{n}{j} inom{n-j}{n-i}\ ys &= sum_{j=1}^{k} {krace j} j! inom{n}{j} sum_{i=j}^{n} inom{n-j}{n-i} & 提一个组合数出去\ &= sum_{j=1}^{k} {krace j} j! inom{n}{j} sum_{i=0}^{j} inom{n-j}{n-j-i}\ &= sum_{j=1}^{k} {krace j} j! inom{n}{j} 2^{n-j} & 下指标求和 end{aligned} ]
code: https://codeforces.com/contest/932/submission/107314924
CF1278F Cards
[egin{aligned} E(x)^k &= E(x^k)\ &= sum_{i=0}^{n} i^k inom{n}{i} frac{1}{m^i} frac{(m-1)^{n-i}}{m^{n-i}}\ &= frac{1}{m^n} sum_{i=0}^{n} inom{n}{i} i^k (m-1)^{n-i}\ &= frac{1}{m^n}sum_{j=0}^{k} {krace j} j! inom{n}{j} sum_{i=0}^{n} inom{n-j}{n-i-j}(m-1)^{n-i-j} & 同上题\ &= frac{1}{m^n}sum_{j=0}^{k} {krace j} j! inom{n}{j} m^{n-j} & 二项式定理 end{aligned} ]
code: https://codeforces.com/contest/1278/submission/107342990
P6620 [省选联考 2020 A 卷] 组合数问题
一个和下降幂无关的做法
[egin{aligned} ys &= sum_{k=0}^{n} sum_{i=0}^{m} a_ik^{i} x^k inom{n}{k}\ &= sum_{i=0}^{m} a_i sum_{k=0}^{n} x^k k^i inom{n}{k}\ &= sum_{i=0}^{m} a_i sum_{j=1}^{i} {irace j} j! inom{n}{j} sum_{k=0}^{n-j} inom{n-j}{k} x^{j+k} & 同上题\ &= sum_{i=0}^{m} a_i sum_{j=1}^{i} {irace j} j! inom{n}{j} x^{j} sum_{k=0}^{n-j} inom{n-j}{k} x^{k}\ &= sum_{i=0}^{m} a_i sum_{j=1}^{i} {irace j} j! inom{n}{j} x^{j} (x+1)^{n-j} end{aligned} ]
不过里面有组合数，不大好处理……考虑用公式把阶乘乘上组合数换成下降幂就行了。但其实我们 overcomplicate 了这个问题。如果一开始就用下降幂会更好（上题应该一样）
我们有多项式转下降幂多项式
[b_i=sum_{j=i}^{m} {jrace i} a_j\ f(x)=sum_{i=0}^{m} b_i x^{underline{i}} ]
[egin{aligned} ys &= sum_{i=0}^{m} b_i sum_{k=i}^{n} x^k k^{underline{i}} inom{n}{k} & 转下降幂多项式\ &= sum_{i=0}^{m} b_i sum_{k=i}^{n} x^k n^{underline{i}} inom{n-i}{k-i} & 下降幂与组合数\ &= sum_{i=0}^{m} b_i n^{underline{i}} x^{i} sum_{k=0}^{n-i} x^{k} inom{n-i}{k-i}\ &= sum_{i=0}^{m} b_i n^{underline{i}} x^{i} (x+1)^{n-i} end{aligned} ]
其实两种解法本质没有什么不同，只不过第一种中，下降幂用阶乘乘上一个组合数表示了，所以看上去会复杂一些。
code: https://www.luogu.com.cn/record/46669969
CF961G Partitions
学校里推的式子，又因为懒得打latex，就先鸽着（？
code: https://codeforces.com/contest/961/submission/108261256
P4827 [国家集训队] Crash 的文明世界
感觉很厉害的一道题目。
首先题目中有一个非常不好的 (k) 次方。我们可以转化成：
[d(i,j)^k=sum_{i=0}^{k} {krace i} inom{x}{i} i! ]
于是有：
[egin{aligned} s(u) &= sum_{v=1}^{n} sum_{i=0}^{k} {krace i} inom{d_{u,v}}{i} i!\ &= sum_{i=0}^{k} i! {krace i} sum_{v=1}^{n} inom{d_{u,v}}{i}\ end{aligned} ]
考虑用换根 DP 求出后面那个组合数求和。设 (f(u,t)) 表示 (u) 子树内的 (inom{d_{u,v}}{t}) 之和。关于组合数的转移，我们有加法公式，所以可以：
[f(u,t)=sum_{vin son_u} f_{v,t}+f_{v,t-1} ]
然后是换根。(g(v,t)) 表示子树外的和。父亲的贡献为 (g(u,t)+g(u,t-1))，兄弟的贡献为 (f(u,t)+f(u,t-1)-(f(v,t)+2f(v,t-1)+f(v,t-2)))。
[f(v,t)=g(u,t)+g(u,t-1)+f(u,t)+f(u,t-1)-(f(v,t)+2f(v,t-1)+f(v,t-2)) ]
然后 DP 好之后统计一下答案即可。
https://www.luogu.com.cn/record/47104122
SP106 BINSTIRL
第二类斯特林数的奇偶性……
考虑斯特林数的递推式
[egin{aligned} {n race m} &= {n-1 race m-1} + m {n-1 race m}\ &equiv {n-1 race m-1} + [2 otmid m] {n-1 race m}\ end{aligned} ]
考虑画出转移图。每一个点都可以斜着向右上走，但是只有 (m) 为偶数的时候才可以向右走。即求最终的路径方案数的奇偶性。考虑用组合数计算，我们要有 (m) 次向右上走，(n-m) 次向右走。一共有 (n-m) 个机会向右上转移，(r=lfloor frac{m+1}{2} floor) 个机会向右转移。那么用组合数即可计算出结果
[inom{n-m+r-1}{r-1} ]
然后根据组合数的结论
[inom{n}{m}equiv[(n operatorname{bitwise and} m)= m] pmod 2 ]
code: https://www.luogu.com.cn/record/47131333