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

斯特林数

时间:2024-02-20 19:56:35浏览次数:15  
标签:begin end Bmatrix 斯特林 sum bmatrix

妈妈生的,这个东西在模拟赛里把我干爆了。

记录一些简单的内容,并不会有超纲的多项式。

第二类斯特林数

\(\begin{Bmatrix}n\\ k\end{Bmatrix}\) 表示第二类斯特林数,也可记作 \(S(n,k)\),组合意义是把 \(n\) 个不同元素划分成 \(k\) 个互不区分的子集的方案数。

显然有递推式:

\[S(n,k)=S(n-1,k-1)+k \times S(n-1,k) \]

由于它比较简单,是可以直接算出的:

\[\begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}i^n}{i!(m-i)!} \]

直接二项式反演就能证明此公式。

第一类斯特林数

\(\begin{bmatrix}n\\ k\end{bmatrix}\) 表示第一类斯特林数,也可记作 \(s(n,k)\),组合意义是把 \(n\) 个不同元素划分成 \(k\) 个互不区分的环的方案数。

显然有递推式:

\[s(n,k)=s(n-1,k-1)+(n-1) \times s(n-1,k) \]

上升幂和普通幂的转化

\[x^{\overline{n}}=\sum_{k} \begin{bmatrix}n\\ k\end{bmatrix} x^k \]

\[x^n=\sum_{k} \begin{Bmatrix}n\\ k\end{Bmatrix} (-1)^{n-k} x^{\overline{k}} \]

下降幂和普通幂的转化

事实上这个更加实用,因为组合数就是两个下降幂相除。

\[x^n=\sum_{k} \begin{Bmatrix}n\\ k\end{Bmatrix} x^{\underline{k}} \]

\[x^{\underline{n}}=\sum_{k} \begin{bmatrix}n\\ k\end{bmatrix} (-1)^{n-k} x^k \]

于是我们可以将普通多项式转化成下降幂多项式。

在不用任何多项式科技的情况下可以做到 \(\Theta(m^2)\)。

下降幂多项式有很优秀的性质,例如与组合数相乘可以得到漂亮的结果。

标签:begin,end,Bmatrix,斯特林,sum,bmatrix
From: https://www.cnblogs.com/tx-lcy/p/18023953

相关文章

  • 斯特林数
    第一类斯特林数:\([^n_k]\):把\(n\)个数放入\(k\)个环中,本质不同的方案数。(要求每个环非空,环之间不区分,环可旋转)\([^n_k]=(n-1)[^{n-1}_k]+[^{n-1}_{k-1}]\)。\(\displaystyle\sum_{k=0}^n[^n_k]=n!\)。第二类斯特林数:\(\{^n_k\}\):把\(n\)个数放入\(k\)个盒中,本质不同......
  • [省选联考 2020 A 卷] 组合数问题(斯特林数)
    题面计算\[\left(\sum_{k=0}^{n}f(k)\timesx^k\times\binom{n}{k}\right)\bmodp\]的值。思路因为模数为合数,不能求逆元,要把组合数的分母消掉。\(x^k\)似乎不能做什么,\(f(k)\)的操作空间似乎很大首先将\(f(k)=\sum_{i=0}^{m}a_ix^i\)转化为\(f(k)=\sum_{i=0}^{m}b_ix^......
  • 斯特林数相关
    定义第一类斯特林数:\({n\brackk}\),指将\(n\)个数放入\(k\)个环中(环无区分)的方案数。第二类斯特林数:\({n\bracek}\),指将\(n\)个数放入\(k\)个盒子(盒子无区分)的方案数。递推式:\[{n\brackk}=(n-1){n-1\brackk}+{n-1\brackk-1}\]说明:我们考虑最后一个数......
  • 斯特林数
    第二类斯特林数定义:第二类斯特林数\(\begin{Bmatrix}n\\k\end{Bmatrix}\),表示将\(n\)个两两不同的元素,划分为\(k\)个互不区分的非空子集的方案数量。比如\(\begin{Bmatrix}a_{1},a_{2},a_{3}\end{Bmatrix}\)只能划分成\(\begin{Bmatrix}a_{1}\end{Bmatrix}\),\(\begi......
  • 卡特兰数&斯特林数
    卡特兰数引入不妨从找规律开始。下标从\(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个空隙必须有加法但是开头和结尾可以有也可以没有这个......