首页 > 其他分享 >斯特林数

斯特林数

时间:2024-01-07 10:00:11浏览次数:21  
标签:begin end Bmatrix 斯特林 sum times bmatrix

第二类斯特林数

定义:

第二类斯特林数 \(\begin{Bmatrix}n\\k\end{Bmatrix}\),表示将 \(n\) 个两两不同的元素,划分为 \(k\) 个互不区分的非空子集的方案数量。

比如 \(\begin{Bmatrix} a_{1},a_{2},a_{3}\end{Bmatrix}\) 只能划分成 \(\begin{Bmatrix}a_{1}\end{Bmatrix}\), \(\begin{Bmatrix}a_{2},a_{3}\end{Bmatrix}\) 和 \(\begin{Bmatrix}a_{1},a_{2}\end{Bmatrix}\), \(\begin{Bmatrix}a_{3}\end{Bmatrix}\) 和 \(\begin{Bmatrix}a_{1},a_{3}\end{Bmatrix}\), \(\begin{Bmatrix}a_{2}\end{Bmatrix}\)。因此 \(S(3,2)=3\)。

递推式

\[h_{i,j}=h_{i-1,j-1}+j \times h_{i-1,j} \]

边界条件为 \(h_{0,0}=1\)。

考虑第 \(i\) 个元素是怎么来的,第一种是新建了一个集合,从 \(h_{i-1,j-1}\) 来。第二种是以前放在以前的 \(j\) 个集合里,因此是 \(j \times h_{i-1,j}\)。

通项公式

考虑二项式反演。

记 \(g(i)\) 表示将 \(n\) 个元素分成 \(i\) 个两两不同的集合的方案数(允许为空),\(f(i)\) 表示将 \(n\) 个元素分成 \(i\) 个两两不同的集合的方案数(不允许为空)。

显然 \(g(i)=i^n\)。

那么

\[\begin{aligned} f(i) &=\sum_{j=0}^{i}(-1)^{i-j}C_{i}^{j}g(j) \\&=\sum_{j=0}^{i}\frac{(-1)^{i-j}i!j^{n}}{j!(i-j)!} \end{aligned} \]

由于第二类斯特林数不区分集合顺序,因此通项公式为:

\[S(n,k)=\sum_{i=0}^{k}\frac{(-1)^{k-i}i^{n}}{i!(k-i)!} \]

应用:

  • \(x^n=\sum_{i=0}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline{i}}\)(普通幂转下降幂)

证明:

考虑有 \(n\) 个小球丢进 \(x\) 个盒子里(允许空),枚举非空的 \(i\) 个盒子,即 \(\sum_{i=0}^{min(n,x)}C_{x}^{i}\begin{Bmatrix}n\\i\end{Bmatrix}i!\)。

整理一下得到原式。

  • \(x^n=\sum_{i=0}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}(-1)^{n-i}x^{\bar i}\)(普通幂转上升幂)

证明:

由于 \(x^{\bar i}=(-1)^i(-x)^{\underline i}\),原式可化简为:

\[(-1)^{n}\sum_{i=0}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}(-x)^{\bar i} \]

即 \((-1)^n(-x)^{n}\)。

第一类斯特林数

定义:

第一类斯特林数 \(\begin{bmatrix}n\\k \end{bmatrix}\),表示将 \(n\) 个两两不同的元素,划分成 \(k\) 个互不区分的非空轮换的方案数。

递推式:

\[h_{i,j}=h_{i-1,j-1}+h_{i-1,j} \times (i-1) \]

边界条件 \(h_{0,0}=1\),考虑第 \(i\) 个元素是怎么来的,第一种是新建了一个轮换,从 \(h_{i-1,j-1}\) 来。第二种是以前放在以前的 \(n-1\) 个数的后面,因此是 \((i-1) \times h_{i-1,j}\)。

应用:

  • \(x^{\underline n}=\sum_{i=0}^{n} \begin{bmatrix}n\\i \end{bmatrix}(-1)^{n-i}x^i\)。(下降幂转普通幂)

证明:

考虑归纳法,\(n=1\) 时显然成立。

\[\begin{aligned} x^{\underline {n+1}} &=x^{\underline {n}} \times (x-n) \\&=(x-n) \times \sum_{i=0}^{n} \begin{bmatrix}n\\i \end{bmatrix}(-1)^{n-i}x^i \\&=\sum_{i=1}^{n+1}\begin{bmatrix}n\\i-1 \end{bmatrix}(-1)^{n-i+1}x^i+n \times \sum_{i=1}^{n+1}\begin{bmatrix}n\\i \end{bmatrix}(-1)^{n-i+1}x^i \\&= \sum_{i=1}^{n+1}(\begin{bmatrix}n\\i-1 \end{bmatrix}+n \times \begin{bmatrix}n\\i \end{bmatrix}) \times (-1)^{n-i+1}x^i \\&= \sum_{i=0}^{n+1} \begin{bmatrix}n+1\\i \end{bmatrix}(-1)^{n+1-i}x^i \end{aligned} \]

  • \(x^{\bar n}=\sum_{i=0}^{n} \begin{bmatrix}n\\i \end{bmatrix}x^i\)(上升幂转普通幂)。

证明:

由于 \(x^{\bar i}=(-1)^i(-x)^{\underline i}\),原式可化简为:

\[\begin{aligned} x^{\bar n} &=(-1)^{n}(-x)^{\underline i} \\&= (-1)^{n}\sum_{i=0}^{n} \begin{bmatrix}n\\i \end{bmatrix}(-1)^{n-i}(-x)^i \\&=\sum_{i=0}^{n} \begin{bmatrix}n\\i \end{bmatrix}x^i \end{aligned} \]

标签:begin,end,Bmatrix,斯特林,sum,times,bmatrix
From: https://www.cnblogs.com/xcs123/p/17950173

相关文章

  • 卡特兰数&斯特林数
    卡特兰数引入不妨从找规律开始。下标从\(0\)开始,卡特兰数的前几项为:1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790…那么通过认真的瞪眼观察,会发现它们满足递推关系。关于卡特兰数是一个很常见的数列。它并没有一个足够......
  • 斯特林数相关式子的证明
    具体数学221页给了很多斯特林恒等式,但是没有给出证明,现在我们来证明一下。前置知识斯特林数的递推公式\[{n\bracek}={n-1\bracek-1}+k{n-1\bracek}\]\[{n\brackk}={n-1\brackk-1}+(n-1){n-1\brackk}\]斯特林数的生成函数:\[\sum_{i\ge0}{n\bracei}x^i=(\sum_{k\ge......
  • 『学习笔记』第二类斯特林数(部分)
    第二类斯特林数定义定义\(\begin{Bmatrix}n\\m\end{Bmatrix}\)表示\(n\)个互不相同的元素放入\(m\)个没有区分的集合并使这\(m\)个集合非空的方案数。其中\(\begin{Bmatrix}n\\m\end{Bmatrix}\)可读作“\(n\)子集\(k\)”。递推式\[\begin{Bmatrix}n......
  • P5395 第二类斯特林数·行
    求\(s(n,i),i\len,n\le2^{18}\)\(k^n=\sum_{i=1}^ks(n,i)i!C(k,i)\)设\(f_k=k^n,g_i=s(n,i)i!\)\(f_k=\sum_{i=0}^kg_iC(k,i)\)由二项式反演\(g_k=\sum_{i=0}^k(-1)^{k-i}f_iC(k,i)\)展开来\(s(n,k)k!=\sum_{i=0}^k(-1)^{k-i}i^nC(k,i)\)即\(s(n,k)=\sum_{i=......
  • F. Bags with Balls 第二类斯特林数
    BagswithBalls标号为奇数的个数为\(c=\frac{m+1}{2}\)标号为偶数个数为\(w=m-c\)答案显然为\(ANS=\sum_{i=1}^{n}C(n,i)c^iw^{n-i}i^k\)直接算是\(O(n)\)的,但这道题\(n\)为\(1e9\)考虑第二类斯特林数化简\(i^k\)\(x^k=\sum_{i=1}^kC(x,i)s(k,i)i!\)\(ANS=\sum_{i=1}^{n}C......
  • 2021百度之星- 复赛 Add or Multiply 1 第二类斯特林数计数
    AddorMultiply1本质上这个题目中乘法和加法没有任何区别因为加法乘法均满足交换律不妨考虑乘法最后分成了k块每块内部没有顺序但是块之间有顺序有顺序共有m个乘法操作这样的方案数是\(s(m,k)k!\)这个时候要求k-1个空隙必须有加法但是开头和结尾可以有也可以没有这个......
  • CF 932 E. Team Work 第二类斯特林数总结
    求解\(\sum_{x=1}^nC(n,x)x^k,n\le10^9,k\le5000\)第二类斯特林数n个不同的小球放入k个相同的盒子的方案数\(S(n,k)\),盒子非空显然有\(S(n,k)=S(n-1,k-1)+k\cdotS(n-1,k)\)注意边界\(S(n,0)=[n==0],S(n,1)=1\)考虑到\(x^k\)可以利用第二类斯特林数化简\(x^k=\sum_{i=1}^{x......
  • HDU4372(第一类斯特林数)
    题目:CounttheBuildings题意:N座高楼,高度均不同且为1~N中的数,从前向后看能看到F个,从后向前看能看到B个,问有多少种可能的排列数。0<N,F,B<=2000首先我们知道一个结论:n的环排列的个数与n-1个元素的排列的个数相等,因为P(n,n)/n=(n-1)!。可以肯定,无论从最左边还是从最右边看,......
  • 【学习笔记】斯特林数
    听说第一类斯特林数啥用没有,先咕咕咕。第二类斯特林数是将\(n\)个有标号球放入\(m\)个无区别盒子的方案数(盒子不可为空)递推式:\[\begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+m\times\begin{bmatrix}n-1\\m\end{bmatrix}\]单独成一盒和......
  • 斯特林数,上升幂,下降幂学习笔记
    斯特林,上升幂,下降幂,普通幂的定义第二类斯特林数n\(n\brace0\)\(n\brace1\)\(n\brace2\)\(n\brace3\)\(n\brace4\)\(n\brace5\)\(n\brace6\)\(n\brace7\)\(n\brace8\)\(n\brace9\)0\(1\)\(0\)\(0\)\(0\)\(0\)\(0\)......