精华内容
下载资源
问答
  • 斯特林数
    2020-05-15 09:14:02

    第一类斯特林数

    n n n 个不同的小球,将它们串成 m m m 条项链,有多少种不同的方案?

    第一类斯特林数的表示方法为 [ n m ] \left[\begin{matrix}n\\m\end{matrix}\right] [nm] s ( n , m ) s(n,m) s(n,m),表示 n n n 个不同的小球串成 m m m 条项链的方案数,考虑第 n n n 个小球的位置,要么接在前面 n − 1 n-1 n1 个小球中的某一个的后面,要么就新开一条项链,那么递推式为:
    s ( n , m ) = ( n − 1 ) s ( n − 1 , m ) + s ( n − 1 , m − 1 ) s(n,m)=(n-1)s(n-1,m)+s(n-1,m-1) s(n,m)=(n1)s(n1,m)+s(n1,m1)

    用递推式来求 s s s 的话时间复杂度为 O ( n m ) O(nm) O(nm),但是有时候我们不需要所有的 s ( i , j ) s(i,j) s(i,j),只需要一个特定位置的值,此时可以考虑用生成函数来优化。

    转化一下上面的递推,第 i i i 次选择时,有 i − 1 i-1 i1 种选择不创造新的项链,有 1 1 1 种选择创造一条新的项链,写成生成函数就是:
    ∏ i = 0 n − 1 ( x + i ) \prod_{i=0}^{n-1} (x+i) i=0n1(x+i)

    此时可以用分治来解决,每一层再用 F F T FFT FFT 将左右两边的多项式乘起来。最后得到的多项式中, x m x^m xm 的系数就是 s ( n , m ) s(n,m) s(n,m),时间复杂度 O ( n log ⁡ 2 n ) O(n\log^2n) O(nlog2n)

    但是有些题会卡这种做法,因为存在更优秀的 O ( n log ⁡ n ) O(n\log n) O(nlogn) 做法。

    具体参考这题

    第二类斯特林数

    n n n 个不同的小球,放在 m m m 个相同的盒子里,每个盒子都不能为空,问有多少种方案。

    这东西和上面不一样的地方就是:在同一个盒子内,不在乎小球的顺序;而上面的项链在乎。

    第二类斯特林数的表示方法为 { n m } \left\{\begin{matrix}n\\m\end{matrix}\right\} {nm} S ( n , m ) S(n,m) S(n,m),类似的,表示 n n n 个不同的小球放在 m m m 个相同的盒子里的方案数。(注意,第一类是小 s s s,第二类是大 S S S)。

    考虑第 n n n 个小球,要么跟前面的小球放同一个盒子里,要么自己新开一个盒子:
    S ( n , m ) = m S ( n − 1 , m ) + S ( n − 1 , m − 1 ) S(n,m)=mS(n-1,m)+S(n-1,m-1) S(n,m)=mS(n1,m)+S(n1,m1)

    此时 S ( n − 1 , m ) S(n-1,m) S(n1,m) 的系数为 m m m,不能使用生成函数来加速了,但是可以考虑容斥。

    为了方便,先假设每个盒子都不一样,最后的方案数再除以 m ! m! m! 即可。

    容斥的话就要考虑不合法的方案,在这里,有盒子空了就是不合法,那么显然能得到:
    S ( n , m ) = 1 m ! ∑ i = 0 m ( − 1 ) i C m i ( m − i ) n S(n,m)=\frac1 {m!}\sum_{i=0}^m (-1)^i C_m^i (m-i)^n S(n,m)=m!1i=0m(1)iCmi(mi)n

    其中, i i i 表示至少 i i i 个盒子为空的方案数, ( − 1 ) i (-1)^i (1)i 是容斥系数, C m i C_m^i Cmi 表示从 m m m 个盒子里选出 i i i 个作为空盒子(因为我们假设了盒子都不一样,所以需要用组合数),然后 n n n 个球放在剩下的 m − i m-i mi 个盒子里的方案数就是 ( m − i ) n (m-i)^n (mi)n,以及最前面乘的 1 m ! \frac 1 {m!} m!1 就是上面所提到的。

    推一下:
         1 m ! ∑ i = 0 m ( − 1 ) i m ! i ! ( m − i ) ! ( m − i ) n = ∑ i = 0 m ( − 1 ) i i ! × ( m − i ) n ( m − i ) ! \begin{aligned} &~~~~\frac 1 {m!}\sum_{i=0}^m (-1)^i\frac {m!} {i!(m-i)!}(m-i)^n\\ &=\sum_{i=0}^m\frac {(-1)^i} {i!}\times \frac {(m-i)^n} {(m-i)!} \end{aligned}     m!1i=0m(1)ii!(mi)!m!(mi)n=i=0mi!(1)i×(mi)!(mi)n

    于是发现这个东西可以用 F F T FFT FFT 搞一搞,时间复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn)

    斯特林数与下降幂

    斯特林数和下降幂可谓是息息相关,这里就简单讲一下利用斯特林数如何做普通多项式与下降幂多项式的转化。

    一般幂转下降幂

    对于 x n x^n xn,有一个经典套路,考虑其组合意义, n n n 个不同的球放 x x x 个不同的盒子里的方案数,枚举一下有多少个非空的盒子:
    x n = ∑ i = 1 x ( x i ) S ( n , i ) i ! = ∑ i = 1 x S ( n , i ) x i ‾ x^n=\sum_{i=1}^x \binom x i S(n,i) i!=\sum_{i=1}^x S(n,i)x^{\underline i} xn=i=1x(ix)S(n,i)i!=i=1xS(n,i)xi

    一般见到的里面求和的上下界其实是 0 0 0 ~ n n n,事实上不难发现这个更宽松的上下界多出来的部分全都是 0 0 0,但是有时候推式子写这个上下界推的会更舒服。

    下降幂转一般幂

    上面提到了,第一类斯特林数的生成函数就是个上升幂,即:
    ∑ i = 1 n s ( n , i ) x i = ∏ i = 0 n − 1 ( x + i ) = x n ‾ \sum_{i=1}^n s(n,i)x^i=\prod_{i=0}^{n-1} (x+i)=x^{\overline n} i=1ns(n,i)xi=i=0n1(x+i)=xn

    假如我们将每一个 ( x + i ) (x+i) (x+i) 替换成 ( x − i ) (x-i) (xi),那么求出来的就是下降幂了。此时左边多项式系数只需要乘以 ( − 1 ) n − i (-1)^{n-i} (1)ni,等式就依然成立,即:
    x n ‾ = ∑ i = 1 n ( − 1 ) n − i s ( n , i ) x i x^{\underline n}=\sum_{i=1}^n (-1)^{n-i} s(n,i)x^i xn=i=1n(1)nis(n,i)xi

    贝尔数

    n n n 个不同的小球放在若干个相同的盒子里,问有多少种不同的方案。

    显然就是第二类斯特林数的和,即 B n = ∑ i = 1 n S ( n , k ) B_n=\sum_{i=1}^n S(n,k) Bn=i=1nS(n,k)

    同时,也能得到递推公式: B n + 1 = ∑ i = 0 n C n i B i B_{n+1}=\sum_{i=0}^nC_n^i B_i Bn+1=i=0nCniBi,枚举的 i i i 表示有 n − i n-i ni 个球和第 n + 1 n+1 n+1 个球在同一个盒子里,那么剩下的 i i i 个就不在同一个盒子里,他们的方案数就是 B i B_i Bi,然后由于球是不一样的,所以还要乘上 C n i C_n^i Cni 即从 n n n 个球里选 i i i 个球的方案数。

    考虑如何快速求出一个 B n B_n Bn,将 B n = ∑ i = 1 n S ( n , k ) B_n=\sum_{i=1}^nS(n,k) Bn=i=1nS(n,k) 展开,得到
    B n = ∑ i = 1 n ∑ j = 0 i ( − 1 ) j j ! × ( n − i ) n ( n − i ) ! = ∑ j = 0 n ( − 1 ) j j ! ∑ i = j n ( n − i ) n ( n − i ) ! \begin{aligned} B_n&=\sum_{i=1}^n\sum_{j=0}^i \frac {(-1)^j} {j!}\times \frac {(n-i)^n} {(n-i)!}\\ &=\sum_{j=0}^n \frac {(-1)^j} {j!}\sum_{i=j}^{n} \frac {(n-i)^n} {(n-i)!} \end{aligned} Bn=i=1nj=0ij!(1)j×(ni)!(ni)n=j=0nj!(1)ji=jn(ni)!(ni)n

    O ( n log ⁡ n ) O(n\log n) O(nlogn) 预处理 ( n − i ) n ( n − i ) ! \frac {(n-i)^n} {(n-i)!} (ni)!(ni)n 的后缀和,就可以 O ( n ) O(n) O(n) 求出 B n B_n Bn 了。

    题表

    第一类斯特林数模板题:上面那题。

    第二类斯特林数模板题:第二类斯特林数·行   题解

    CF932E Team Work   题解

    CF960G Bandit Blues   题解

    [HEOI2016/TJOI2016]求和   题解

    [国家集训队] Crash 的文明世界   题解

    更多相关内容
  • 第二类斯特林数是将一组 n 个对象划分为 k 个非空子集的方法数,用 S(k,i) 表示。 第二类斯特林数出现在称为组合学和分区研究的数学领域。 简而言之,它是将 k 个可区分元素分配到 I 个不可区分的容器中且没有容器为...
  • 将 n 个元素的集合划分为 k 个非空集合的方法称为斯特林。 例如,集合{1,2,3}可以通过一种方式划分为三个子集:{{1},{2},{3}}; 以三种方式分成两个子集:{{1,2},{3}}, {{1,3},{2}}和{{1},{2,3}}; 并以一种...
  • 第一类斯特林数定义为多项式中 x 的幂系数: Q(x)=(x-1)(x-2)...(xn)。 例如, Q0(x)=1; Q1(x)=x-1; % Q2(x)=(x-1)(x-2)=x^2-3x+2; Q3(x)=(x-1)(x-2)(x-3)=x^3-6x^2+11x-6; ... 此函数计算 n>=2 的情况(n=0 ...
  • INPUT: N 要分区的集合中的元素输出:一个矩阵,其元素 (i,j) 是 S(i,j)
  • 此代码计算(有符号)第一类斯特林数,如维基百科所述: https : //en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind
  • 斯特林数.txt

    2019-08-06 22:48:02
    就是博客里写的正确代码的txt,因为是第一次写博客,不知道应该上传什么资料,所以就上传了这个。
  • 斯特林数

    2021-03-23 17:17:27
    斯特林数有两类,分为第一类斯特林数和第二类斯特林数。 其中第一类斯特林数又有无符号版本和有符号的版本。这里主要介绍无符号版本。 第一类斯特林数 定义 将1−n1-n1−n划分为kkk个圆排列的方案数,这kkk个圆排列...

    斯特林数有两类,分为第一类斯特林数和第二类斯特林数。

    其中第一类斯特林数又有无符号版本和有符号的版本。这里主要介绍无符号版本。

    第一类斯特林数

    定义

    1 − n 1-n 1n划分为 k k k个圆排列的方案数,这 k k k个圆排列相互之间没有顺序。记作 s ( n , k ) s(n,k) s(n,k) [ n k ] \begin{bmatrix}n \\k \end{bmatrix} [nk]

    求法

    [ n k ] = [ n − 1 k − 1 ] + ( n − 1 ) [ n − 1 k ] \begin{bmatrix}n \\k \end{bmatrix}=\begin{bmatrix}n-1 \\k-1 \end{bmatrix}+(n-1)\begin{bmatrix}n-1 \\k \end{bmatrix} [nk]=[n1k1]+(n1)[n1k]

    推导的思路:
    假设我们现在正在放第 n n n个数,我们目前有两种选择:

    1. n n n放到新的圆当中
    2. n n n放到已有的圆中

    对于第一种选择,对于 n n n来说,放到新圆当中,只有一种放法。因此我们主要考虑前 n − 1 n-1 n1个数的放法即可。我们发现前 n − 1 n-1 n1个数的放法其实就是一个斯特林数 [ n − 1 k − 1 ] \begin{bmatrix}n-1 \\k-1 \end{bmatrix} [n1k1],也就是将 n − 1 n-1 n1个数划分为 k − 1 k-1 k1个圆排列的方案数。

    对于第二种选择,对于 n n n来说,放到之前的圆排列中的方案数,我们可以根据下面的例子得出:
    在这里插入图片描述
    对于这个含有4个数的圆排列,现在我想往里面插入一个数,总共有几种方案?
    可以发现,我们可以把新的数插入到 1 1 1的后面,或者到 2 2 2的后面,或者 3 3 3的后面,或者 4 4 4的后面,也就是图中的 a , b , c , d a,b,c,d a,b,c,d四个位置。总共有4种方案。

    因此我们现在想将 n n n插入到之前已存在的圆排列当中,就相当于选择插入到哪个前 n − 1 n-1 n1个数的后面。因此,有 n − 1 n-1 n1种方案。

    考虑了 n n n的插入放法,基于之前 n − 1 n-1 n1个数已经分成了 k k k个圆排列。因此最终第二种选择的方案数就是: ( n − 1 ) ∗ [ n − 1 k ] (n-1)*\begin{bmatrix}n-1 \\k \end{bmatrix} (n1)[n1k]

    两种选择的方案数相加即可推出上式。

    性质

    1. [ 0 0 ] = 1 \begin{bmatrix}0 \\0 \end{bmatrix}=1 [00]=1
    2. [ n n ] = 1 \begin{bmatrix}n \\n \end{bmatrix}=1 [nn]=1
    3. [ n 0 ] = 0 \begin{bmatrix}n \\0 \end{bmatrix}=0 [n0]=0
    4. [ n 1 ] = ( n − 1 ) ! \begin{bmatrix}n \\1 \end{bmatrix}=(n-1)! [n1]=(n1)!
      推导:
      这就相当于 n n n个数的圆排列。 n n n个数组成一个圆的方案数总共有 n ! n! n!种,不过,对于每种方案,都有 n n n个圆排列通过旋转可以与其相同,因此,不同的圆排列方案数有 n ! n = ( n − 1 ) ! \frac {n!}n=(n-1)! nn!=(n1)!
    5. [ n n − 1 ] = C n 2 \begin{bmatrix}n \\n-1 \end{bmatrix}=C_n^2 [nn1]=Cn2
    6. [ n 2 ] = 1 2 ∑ i = 1 n − 1 C n i ( i − 1 ) ! ( n − i − 1 ) ! = ( n − 1 ) ! ∑ i = 1 n − 1 1 i \begin{bmatrix}n \\2 \end{bmatrix}=\frac 12\sum_{i=1}^{n-1}C_n^i(i-1)!(n-i-1)!=(n-1)!\sum_{i=1}^{n-1}\frac 1i [n2]=21i=1n1Cni(i1)!(ni1)!=(n1)!i=1n1i1
      推导过程如下:
      1 2 ∑ i = 1 n − 1 C n i ( i − 1 ) ! ( n − i − 1 ) ! = 1 2 ∑ i = 1 n − 1 n ! i ( n − i ) = 1 2 ∑ i = 1 n − 1 ( n − 1 ) ! n i ( n − i ) = 1 2 ∑ i = 1 n − 1 ( n − 1 ) ! ( 1 i + 1 n − i ) = 1 2 ∗ 2 ∑ i = 1 n − 1 ( n − 1 ) ! 1 i = ( n − 1 ) ! ∑ i = 1 n − 1 1 i \frac 12\sum_{i=1}^{n-1}C_n^i(i-1)!(n-i-1)!=\frac 12\sum_{i=1}^{n-1}\frac {n!}{i(n-i)}=\frac 12\sum_{i=1}^{n-1}(n-1)!\frac n{i(n-i)}=\frac 12\sum_{i=1}^{n-1}(n-1)!(\frac 1i+\frac 1{n-i})=\frac 12*2\sum_{i=1}^{n-1}(n-1)!\frac 1i=(n-1)!\sum_{i=1}^{n-1}\frac 1i 21i=1n1Cni(i1)!(ni1)!=21i=1n1i(ni)n!=21i=1n1(n1)!i(ni)n=21i=1n1(n1)!(i1+ni1)=212i=1n1(n1)!i1=(n1)!i=1n1i1
      倒数第二步的推导,是由于 1 i \frac 1i i1 1 n − i \frac 1{n-i} ni1在取值范围内的值域相同,因此可以直接2倍。
    7. [ n n − 2 ] = 2 C n 3 + 3 C n 4 \begin{bmatrix}n \\{n-2} \end{bmatrix}=2C_n^3+3C_n^4 [nn2]=2Cn3+3Cn4
    8. ∑ k = 0 n s ( n , k ) = n ! \sum_{k=0}^ns(n,k)=n! k=0ns(n,k)=n!
      可以通过升阶函数证明。

    第二类斯特林数

    定义

    1 − n 1-n 1n划分成 k k k个子集的方案数,记作 S ( n , k ) S(n,k) S(n,k) { n k } \begin{Bmatrix} n \\k \end{Bmatrix} {nk}

    求法

    S ( n , k ) = S ( n − 1 , k − 1 ) + k S ( n − 1 , k ) S(n,k)=S(n-1,k-1)+kS(n-1,k) S(n,k)=S(n1,k1)+kS(n1,k)

    递推方式与第一类相同。

    性质

    1. S ( n , 0 ) = 0 n S(n,0)=0^n S(n,0)=0n
    2. S ( n , 1 ) = 1 S(n,1)=1 S(n,1)=1
    3. S ( n , n ) = 1 S(n,n)=1 S(n,n)=1
    4. S ( n , 2 ) = 2 n − 1 − 1 S(n,2)=2^{n-1}-1 S(n,2)=2n11
      假设两个集合有序,那么 n n n个数插入两个集合的总方案数是 2 n 2^n 2n,由于两个集合都不能为空,因此方案数是 2 n − 2 2^n-2 2n2。最后因为两个集合不考虑相互位置,因此,总方案数是 ( 2 n − 2 ) / 2 = 2 n − 1 − 1 (2^n-2)/2=2^{n-1}-1 (2n2)/2=2n11
    5. S ( n , n − 1 ) = C n 2 S(n,n-1)=C_n^2 S(n,n1)=Cn2
    6. S ( n , n − 2 ) = C n 3 + 3 C n 4 S(n,n-2)=C_n^3+3C_n^4 S(n,n2)=Cn3+3Cn4
    7. S ( n , n − 3 ) = C ( n , 4 ) + 10 C ( n , 5 ) + 15 C ( n , 6 ) S(n,n-3)=C(n,4)+10C(n,5)+15C(n,6) S(n,n3)=C(n,4)+10C(n,5)+15C(n,6)
    8. ∑ k = 0 n S ( n , k ) = B n , B n 是 贝 尔 数 \sum_{k=0}^nS(n,k)=B_n,B_n是贝尔数 k=0nS(n,k)=Bn,Bn

    通项公式

    S ( n , m ) = 1 m ! ∑ k = 0 m ( − 1 ) k C ( m , k ) ( m − k ) n S(n,m)=\frac 1{m!}\sum_{k=0}^m(-1)^kC(m,k)(m-k)^n S(n,m)=m!1k=0m(1)kC(m,k)(mk)n

    两类斯特林数的关系

    ∑ k = 0 n [ n k ] { k m } = ∑ k = 0 n { n k } [ k m ] \sum_{k=0}^n\begin{bmatrix}n \\k \end{bmatrix}\begin{Bmatrix}k \\m \end{Bmatrix}=\sum_{k=0}^n\begin{Bmatrix}n \\k \end{Bmatrix}\begin{bmatrix}k \\m \end{bmatrix} k=0n[nk]{km}=k=0n{nk}[km]

    展开全文
  • 该文件仅生成第一类和第二类斯特林数。 输出在同一个调用中提供了两个矩阵。 例如 [SN1,SN2]=mystirling1(n)。 这里,n 是矩阵大小。 这两个矩阵都是带有 int64 元素的正方形。 您可能希望将矩阵转换为 double 以...
  • 该文件仅生成第一类和第二类斯特林数。 输出在同一个调用中提供了两个矩阵。 例如 [SN1,SN2]=mystirling1(n)。 这里,n 是矩阵大小。 这两个矩阵都是带有 int64 元素的正方形。 您可能希望将矩阵转换为 double 以...
  • 斯特林数(数论)

    2021-11-14 10:42:47
    斯特林数:stirling 概念: 1、第一类斯特林数:把1~n排列成k个非空循环的方案数,用小写s(n,k)或[n k]表示 2、第二类斯特林数:将1~n排成k个非空集合的方案数,用大写S(n,k)或{n,k}表示 第一类斯特林数: 递推...

    斯特林数:stirling

    概念:

    1、第一类斯特林数:把1~n排列成k个非空循环的方案数,用小写s(n,k)或[n k]表示

    2、第二类斯特林数:将1~n排成k个非空集合的方案数,用大写S(n,k)或{n,k}表示

    第一类斯特林数:

    递推:

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

    边界s(0,0)=1,s(n,k)=0 (n<k)

    组合意义:考虑加入n时,可以自己构成环,后者插入一个之前已有的数的后面,复杂度O(nk)

    - 与上升幂、下降幂的关系:

    上升幂定义:

    $$
    \ x^ \bar n=x \times (x+1) \times.....\times(x+n-1)
    $$

    是一个多项式,有

    $$
    x^ \bar n=\sum_{k=1}^{n}s(n,k)\times x^k
    $$

    组合意义:考虑把1~n排成k个非空循环序列,然后将每个环染成[1,x]中的某种颜色,等式右边就是枚举环的数量,然后每个环任意染色,等式左边相当与考虑每次加入一个新点n,若构成一个新环,则有x种染色方法,否则插入1个之前已有的数的后面继承其颜色,那么n个点的总方案数就是上升幂

    下降幂定义:

    $$
    x^\bar n=x(x-1)....(x-n+1)
    $$

    是一个多项式,有:

    $$
    \ x^\bar n=\sum_{k=1}^{n} \left(-1\right)^ \left(n-k\right)\times s(n,k)\times x^k
    $$

    • 性质:

      $$
      s(n,1)=(n-1)!
      $$

       

      $$
      s(n,2)=(n-1)!\times\sum_{i=1}^{n-1}\frac{1}{i}
      $$

       

      $$
      n!=\sum_{k=0}^{n}s(n,k)
      $$

       

      最后一条的组合意义:任意1个排列可以看成一个置换,那么枚举置换中环的数量然后求和就是全排列

    s(n,k)k=0k=1k=2k=3k=4k=5k=6
    n=01
    n=101
    n=2011
    n=30231
    n=4061161
    n=50245035101
    n=6012027422585151

    第二类斯特林数:S(n,k)

    递推:

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

    边界S(0,0)=1,S(n,k) = 0(n<k)

    组合意义:考虑加入n时,可以自己构成一个集合,或者插入一个1之前已有的集合,复杂度O(nk)。第二类斯特林数也可以用小球模型来描述,其对应:n个不同的球,放进k个相同的盒子,不能有空盒子的方案数

    • 与下降幂之间的关系:

      $$
      x^n=\sum_{k=0}^{n}\times x^\underline k
      $$

       

      组合意义:给1~n每个数染[1,x]中的某种颜色,方案数为左边x^n右边枚举一共有k种不同的颜色,把1~n分成k个集合(S(n,k))然后每个集合一次染色

    • 通项公式(容斥):

      $$
      S(n.k)=\frac{1}{k!}\sum_{i=0}^{k}\times s(n,i)\times\left(n-k\right)^n
      $$

       

      组合意义:考虑“n个不同的球,放进k个不同的盒子,可以有空盒子的方案数”,其显然等于k^n。若不能有空盒子,则枚举空盒子的数量i然后容斥,即“n个不同的球,放进k个不同盒子,有至少i个空盒子”的方案数=s(n,i)*(k-i)^n,容斥系数为(-1)^i,最后再除以k!时把盒子不同转化为盒子相同,利用这个容斥可以实现O(nlogn)计算一个S(n,k)

      • 与自然数幂和的关系

        定义:

        $$
        F(n)=\sum_{i=1}^{n}i^k
        $$

         

        暴力计算时间复杂度O(nlogk)

      • 使用第二类stiring数转化为下降幂:

        $$
        F(n)=\sum_{i=1}^{n}\sum_{j=0}^{k}S\{k,j\}=\sum_{i=1}^{n}\sum_{j=0}^{k}S\{k,j\}j!s(i,j)
        $$

         

        $$
        F(n)=\sum_{j=0}^{k}j!\sum_{i=j}^{n}s(i,j)
        $$

         

        这个式子和n相关的杨辉三角上一列求和,等于右下角

        $$
        F(n)=\sum_{j=0}^{k}S\{k,j\}j!s(n+1,j+1)
        $$

         

        这个式子仅枚举k如果O(k^2)预处理S(k,j)那么可以在O(klogk)时间求解上F(n)

    S(n,k)k=0k=1k=2k=3k=4k=5k=6
    n=01
    n=101
    n=2011
    n=30131
    n=401761
    n=5011525101
    n=601319065151

    展开全文
  • 斯特林数相关

    2020-06-29 22:33:33
    最近听说了小道消息:XC要求初一的同学们学好各种东西,其中包括斯特林数。 我笑掉大牙! 联合省选的D1T2放出了一道裸的斯特林数,幸亏之前推过第二类斯特林数求自然数幂和,所以很幸运地切了。 这次比赛之后dyp和...

    联合省选的D1T2放出了一道裸的斯特林数,幸亏之前推过第二类斯特林数求自然数幂和,所以很幸运地切了。
    这次比赛之后dyp和gmh77疯狂学斯特林数,从此免疫。
    惊得我也系统地学一下斯特林数做做样子。


    概念

    第一类斯特林数:记为 s ( m , n ) s(m,n) s(m,n)(也可以用中括号表示),组合意义为 m m m个数形成 n n n个圆排列的方案数。
    有个比较系统的定义: s ( m , n ) = [ x n ] ∏ i = 0 m − 1 ( x + i ) s(m,n)=[x^n]\prod_{i=0}^{m-1}(x+i) s(m,n)=[xn]i=0m1(x+i)
    性质:
    s ( m , n ) = ( m − 1 ) ∗ s ( m − 1 , n ) + s ( m − 1 , n − 1 ) s(m,n)=(m-1)*s(m-1,n)+s(m-1,n-1) s(m,n)=(m1)s(m1,n)+s(m1,n1)
    组合意义可证。
    ∑ k = 0 n s ( n , k ) = n ! \sum_{k=0}^ns(n,k)=n! k=0ns(n,k)=n!
    每一种排列,对应着一种轮换。意思记排列为 p p p i i i p i p_i pi连边,这样就会形成若干个环。

    第二类斯特林数:记为 S ( m , n ) S(m,n) S(m,n)(也可以用大括号表示),组合意义为 m m m个数形成 n n n个集合的方案数。
    性质:
    S ( m , n ) = n ∗ S ( m − 1 , n ) + S ( m − 1 , n − 1 ) S(m,n)=n*S(m-1,n)+S(m-1,n-1) S(m,n)=nS(m1,n)+S(m1,n1)
    组合意义可证。
    S ( m , n ) = 1 n ! ∑ k = 0 n ( − 1 ) k C ( n , k ) ( n − k ) m S(m,n)=\frac{1}{n!}\sum_{k=0}^{n}(-1)^kC(n,k)(n-k)^m S(m,n)=n!1k=0n(1)kC(n,k)(nk)m
    反演得到(下面有提及)。
    ∑ k = 0 n S ( n , k ) = B n \sum_{k=0}^nS(n,k)=B_n k=0nS(n,k)=Bn
    B B B表示贝尔数。

    有符号斯特林数:顾名思义就是有符号的斯特林数。
    s s ( m , n ) = − ( m − 1 ) ∗ s s ( m − 1 , n ) + s s ( m − 1 , n − 1 ) s_s(m,n)=-(m-1)*s_s(m-1,n)+s_s(m-1,n-1) ss(m,n)=(m1)ss(m1,n)+ss(m1,n1)
    S s ( m , n ) = − n ∗ S s ( m − 1 , n ) + S s ( m − 1 , n − 1 ) S_s(m,n)=-n*S_s(m-1,n)+S_s(m-1,n-1) Ss(m,n)=nSs(m1,n)+Ss(m1,n1)

    下标 s s s意思为“signed”

    打个表出来可以发现
    s s ( m , n ) = ( − 1 ) m − n s ( m , n ) s_s(m,n)=(-1)^{m-n}s(m,n) ss(m,n)=(1)mns(m,n)
    S s ( m , n ) = ( − 1 ) m − n S ( m , n ) S_s(m,n)=(-1)^{m-n}S(m,n) Ss(m,n)=(1)mnS(m,n)


    性质

    s ( m , n ) ≥ S ( m , n ) s(m,n)\geq S(m,n) s(m,n)S(m,n)
    排列数大于等于集合数。

    普通幂、上升幂、下降幂相关:(这个在推式子的时候经常能够用到!)
    x n = ∑ k = 0 n S ( n , k ) x k ‾ x^n=\sum_{k=0}^nS(n,k)x^{\underline k} xn=k=0nS(n,k)xk
    x n = ∑ k = 0 n S ( n , k ) ( − 1 ) n − k x k ‾ = ∑ k = 0 n S s ( n , k ) x k ‾ x^n=\sum_{k=0}^nS(n,k)(-1)^{n-k}x^{\overline k}=\sum_{k=0}^nS_s(n,k)x^{\overline k} xn=k=0nS(n,k)(1)nkxk=k=0nSs(n,k)xk
    x n ‾ = ∑ k = 0 n s ( n , k ) x k x^{\overline n}=\sum_{k=0}^ns(n,k)x^k xn=k=0ns(n,k)xk
    x n ‾ = ∑ k = 0 n s ( n , k ) ( − 1 ) n − k x k = ∑ k = 0 n s s ( n , k ) x k x^{\underline n}=\sum_{k=0}^ns(n,k)(-1)^{n-k}x^k=\sum_{k=0}^ns_s(n,k)x^k xn=k=0ns(n,k)(1)nkxk=k=0nss(n,k)xk
    具体证明嘛,各种归纳,各种组合意义。


    快速求斯特林数

    第一类斯特林数:
    把定义式搬下来: s ( m , n ) = [ x n ] ∏ i = 0 m − 1 ( x + i ) s(m,n)=[x^n]\prod_{i=0}^{m-1}(x+i) s(m,n)=[xn]i=0m1(x+i)
    s m ( x ) = ∏ i = 0 m − 1 ( x + i ) s_m(x)=\prod_{i=0}^{m-1}(x+i) sm(x)=i=0m1(x+i)
    考虑倍增求这个东西。从 s m ( x ) s_m(x) sm(x)推到 s 2 m ( x ) s_{2m}(x) s2m(x)时:
    s 2 m ( x ) = s m ( x ) s m ( x + m ) s_{2m}(x)=s_{m}(x)s_m(x+m) s2m(x)=sm(x)sm(x+m)
    快速求出 s m ( x + m ) s_m(x+m) sm(x+m)。设 s m ( x ) = ∑ i = 0 m s m , i x i s_m(x)=\sum_{i=0}^ms_{m,i}x^i sm(x)=i=0msm,ixi。之前已经求出 s m , i s_{m,i} sm,i
    s m ( x + m ) = ∑ i = 0 m s m , i ( x + m ) i s_m(x+m)=\sum_{i=0}^ms_{m,i}(x+m)^i sm(x+m)=i=0msm,i(x+m)i
    二项式展开一下,推一波式子,就可以发现一个卷积。
    于是计算 s m ( x + m ) s_m(x+m) sm(x+m)的时间复杂度是 O ( m lg ⁡ m ) O(m\lg m) O(mlgm)的。
    由于 m m m是两倍两倍地扩大,所以总的时间复杂度也是 O ( m lg ⁡ m ) O(m \lg m) O(mlgm)

    第二类斯特林数:
    把上面那个普通幂转下降幂的式子搬下来,简单反演一下,得到:
    n ! S ( m , n ) = ∑ k = 0 n ( − 1 ) k C ( n , k ) ( n − k ) m n!S(m,n)=\sum_{k=0}^{n}(-1)^kC(n,k)(n-k)^m n!S(m,n)=k=0n(1)kC(n,k)(nk)m
    把后面的那个组合数拆开,可以发现这是个很明显的卷积形式。
    时间复杂度 O ( n lg ⁡ n ) O(n \lg n) O(nlgn)


    斯特林反演

    f ( n ) = ∑ k = 0 n S ( n , k ) g ( k ) ⟺ g ( n ) = ∑ k = 0 n ( − 1 ) n − k s ( n , k ) f ( k ) f(n)=\sum_{k=0}^n S(n,k)g(k) \Longleftrightarrow g(n)=\sum_{k=0}^n(-1)^{n-k}s(n,k)f(k) f(n)=k=0nS(n,k)g(k)g(n)=k=0n(1)nks(n,k)f(k)
    有个叫反转公式的东西:
    ∑ k s ( n , k ) S ( k , m ) ( − 1 ) n − k = [ m = n ] \sum_ks(n,k)S(k,m)(-1)^{n-k}=[m=n] ks(n,k)S(k,m)(1)nk=[m=n]
    ∑ k S ( n , k ) s ( k , m ) ( − 1 ) n − k = [ m = n ] \sum_kS(n,k)s(k,m)(-1)^{n-k}=[m=n] kS(n,k)s(k,m)(1)nk=[m=n]
    关于这个怎么证明……最严谨的方法应该是归纳。

    写公式太麻烦,直接口胡一下证明的思路(挺好推的)。
    比如上面这条式子: ∑ k s ( n , k ) S ( k , m ) ( − 1 ) n − k = [ m = n ] \sum_ks(n,k)S(k,m)(-1)^{n-k}=[m=n] ks(n,k)S(k,m)(1)nk=[m=n]
    先将 s ( n , k ) s(n,k) s(n,k)用递推式拆开,展开一下。
    再将 S ( k , m ) S(k,m) S(k,m)用递推式拆开,展开一下。
    照着这么做就可以很自然地归纳证明出来了。
    另一条式子也可以类似地推出来。
    看了一些博客,有些博客里面写了一种不是很严谨的证明方法:
    具体就是取一个普通幂 n m n^m nm,将它先用第二类斯特林数表示成下降幂多项式,然后将这个下降幂用第一类斯特林数表示成普通幂。
    推推式子就会得到这样: n m = ∑ j = 0 m n j ∑ k = j m S ( m , k ) s ( k , j ) ( − 1 ) j − k n^m=\sum_{j=0}^mn^j\sum_{k=j}^mS(m,k)s(k,j)(-1)^{j-k} nm=j=0mnjk=jmS(m,k)s(k,j)(1)jk
    然后谁告诉我,这怎么就能直接得到 ∑ k = j m S ( m , k ) s ( k , j ) ( − 1 ) j − k = [ j = m ] \sum_{k=j}^mS(m,k)s(k,j)(-1)^{j-k}=[j=m] k=jmS(m,k)s(k,j)(1)jk=[j=m]了???
    这种方法只能解释假设反转公式成立,这个东西也成立;但不能反过来推啊……

    如果设矩阵 F i , j = S ( i , j ) F_{i,j}=S(i,j) Fi,j=S(i,j) G i , j = ( − 1 ) i − j s ( i , j ) G_{i,j}=(-1)^{i-j}s(i,j) Gi,j=(1)ijs(i,j)
    (或者 F i , j = s ( i , j ) F_{i,j}=s(i,j) Fi,j=s(i,j) G i , j = ( − 1 ) i − j S ( i , j ) G_{i,j}=(-1)^{i-j}S(i,j) Gi,j=(1)ijS(i,j)
    不难发现 F ∗ G = E F*G=E FG=E,即 F F F G G G互逆。

    拉赫数(第三类斯特林数?)

    似乎只有维基上略有提及,所以不够详细请见谅。
    有错误请指出。

    无符号拉赫数:
    上升幂和下降幂定义:
    x n ‾ = ∑ k = 0 n L ( n , k ) x n ‾ x^{\overline n}=\sum_{k=0}^nL(n,k)x^{\underline n} xn=k=0nL(n,k)xn
    x n ‾ = ∑ k = 0 n ( − 1 ) n − k L ( n , k ) x n ‾ x^{\underline n}=\sum_{k=0}^{n}(-1)^{n-k}L(n,k)x^{\overline n} xn=k=0n(1)nkL(n,k)xn
    递推式定义: L ( m , n ) = L ( m − 1 , n − 1 ) + ( n − 1 + m ) L ( m , n − 1 ) L(m,n)=L(m-1,n-1)+(n-1+m)L(m,n-1) L(m,n)=L(m1,n1)+(n1+m)L(m,n1)
    矩阵乘法定义: L ( m , n ) = ∑ k s ( m , k ) S ( k , n ) L(m,n)=\sum_k s(m,k)S(k,n) L(m,n)=ks(m,k)S(k,n)

    有符号拉赫数:
    上升幂和下降幂定义:
    x n ‾ = ( − 1 ) n ∑ k = 0 n L s ( n , k ) x n ‾ x^{\overline n}=(-1)^n\sum_{k=0}^nL_s(n,k)x^{\underline n} xn=(1)nk=0nLs(n,k)xn
    x n ‾ = ( − 1 ) k ∑ k = 0 n L s ( n , k ) x n ‾ x^{\underline n}=(-1)^k\sum_{k=0}^{n}L_s(n,k)x^{\overline n} xn=(1)kk=0nLs(n,k)xn
    L s ( m , n ) = ( − 1 ) m L ( m , n ) L_s(m,n)=(-1)^mL(m,n) Ls(m,n)=(1)mL(m,n)

    性质:
    L ( m , n ) = C ( m − 1 , n − 1 ) m ! n ! L(m,n)=C(m-1,n-1)\frac{m!}{n!} L(m,n)=C(m1,n1)n!m!
    归纳可证:
    ∑ k L s ( m , k ) L s ( k , n ) = ∑ k ( − 1 ) m − k L ( m , k ) L ( k , n ) = [ m = n ] \sum_kL_s(m,k)L_s(k,n)=\sum_k(-1)^{m-k}L(m,k)L(k,n)=[m=n] kLs(m,k)Ls(k,n)=k(1)mkL(m,k)L(k,n)=[m=n]
    L ( n , k ) = n ! [ x n ] 1 k ! ( x 1 − x ) k L(n,k)=n![x^n]\frac{1}{k!}(\frac{x}{1-x})^k L(n,k)=n![xn]k!1(1xx)k


    参考资料

    https://www.cnblogs.com/Wuweizheng/p/8638858.html
    https://www.cnblogs.com/hchhch233/p/10016543.html
    https://www.cnblogs.com/owenyu/p/6724661.html
    https://www.cnblogs.com/gzy-cjoier/p/8426987.html
    百度百科
    维基百科

    展开全文
  • 卡特兰数 斯特林数

    2019-10-08 15:07:17
    卡特兰是组合数学中一个常出现在各种计数问题中出现的数列。 卡特兰前几项为 :C0=1,C1=1,C2=2,C3=5,C4=14,C5=42,C6=132,C7=429,C8=1430,C9=4862,C10=16796 1, 1, 2, 5, 14, 42, 132, 429...
  • 第二类斯特林数

    2021-08-23 10:56:32
    第二类斯特林数表示将n个不同的元素分成m个集合的方案数。 代码 s[i][j]实现代码: const int mod=1e9+7;//取模 LL s[N][N];//存放要求的第一类Stirling数 void init(){ memset(s,0,sizeof(s)); s[1][1]=1; for...
  • 通俗易懂的斯特林数介绍 定义 第一类斯特林数 第二类斯特林数 性质 通项 递推 第一类斯特林数 第二类斯特林数 特殊值 第一类斯特林数 第二类斯特林数 快速幂??? 斯特林反演 定义 第一类斯特林数 将 n n n个元素...
  • 斯特林数与上升幂与下降幂

    千次阅读 2020-09-01 11:01:48
    nk​​ xp‾≡xp−xmod  px^{\overline{p}}\equiv x^p-x\mod pxp​≡xp−xmodp 第二类斯特林数 第二类斯特林数写作 {nk}\left\{ \begin{aligned} n \\ k \end{aligned} \right\}{nk​} 或 S2(n,k)S_2(n, k)S2​(n,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,610
精华内容 1,844
关键字:

斯特林数

友情链接: WIFI代码.zip