精华内容
下载资源
问答
  • 第一类Stirling数(第一类斯特林数
    千次阅读
    2019-01-28 21:47:35

    第一类Stirling数(第一类斯特林数)

    • 定义

    • 第一类Stirling数表示把 n n n个不同元素构成 m m m个圆的排列方案数,写作 s ( n , m ) s(n,m) s(n,m).
    • 根据正负性分为无符号第一类Stirling数 s u ( n , m ) s_u(n,m) su(n,m)带符号第一类Stirling数 s s ( n , m ) s_s(n,m) ss(n,m).
    • 组合数学中的第一类Stirling数泛指无符号第一类Stirling数,在此,也只展开介绍无符号第一类Stirling数。
    • 递推式

    • 考虑 s u ( n , m ) s_u(n,m) su(n,m)可以由什么转移得到?
    • 1、 s u ( n − 1 , m − 1 ) s_u(n-1,m-1) su(n1,m1),由 n − 1 n-1 n1个不同元素构成了 m − 1 m-1 m1个圆,则第 n n n个元素必须单独构成第 m m m圆。方案数:
      s u ( n − 1 , m − 1 ) s_u(n-1,m-1) su(n1,m1)
    • 2、 s u ( n − 1 , m ) s_u(n-1,m) su(n1,m),由 n − 1 n-1 n1个不同元素已经构成了 m m m个圆,则第 n n n个元素可以放在前 n − 1 n-1 n1个元素中任意一个前面。方案数:
      s u ( n − 1 , m ) ∗ ( n − 1 ) s_u(n-1,m)*(n-1) su(n1,m)(n1)
    • 则可以得出递推式:
      s u ( n , m ) = s u ( n − 1 , m − 1 ) + s u ( n − 1 , m ) ∗ ( n − 1 ) s_u(n,m)=s_u(n-1,m-1)+s_u(n-1,m)*(n-1) su(n,m)=su(n1,m1)+su(n1,m)(n1)
    • 三角形

    n s u ( n , m ) s_u(n,m) su(n,m)
    01
    10 1
    20 1 1
    30 2 3 1
    40 6 11 6 1
    50 24 50 35 10 1
    • 性质

    • 通过观察以上的三角形可以得到:
    • 1、 s u ( 0 , 0 ) = 1 s_u(0,0)=1 su(0,0)=1
    • 2、 s u ( n , 0 ) = 0 s_u(n,0)=0 su(n,0)=0
    • 3、 s u ( n , n ) = 1 s_u(n,n)=1 su(n,n)=1
    • 4、 s u ( n , 1 ) = ( n − 1 ) ! s_u(n,1)=(n-1)! su(n,1)=(n1)!
    • 5、 s u ( n , n − 1 ) = C n 2 = n ( n − 1 ) 2 s_u(n,n-1)=C_{n}^{2}=\frac{n(n-1)}{2} su(n,n1)=Cn2=2n(n1)
    • 更多请见百度百科
    • 应用

    • 经典仓库解锁问题:
    • 1、有 n n n个仓库,每个仓库 2 2 2把钥匙,共 2 n 2n 2n把钥匙。又有 n n n位官员,如何放置钥匙才能使得每一位官员能打开每一个仓库?(不考虑官员手里的钥匙)共多少种方案?
    • 只需把钥匙放成一个环形(仓库 1 1 1放钥匙 2 2 2,仓库 2 2 2放钥匙 3 3 3……仓库 n n n放钥匙 1 1 1),一共有 ( n − 1 ) ! (n-1)! (n1)!种方案(不能自己放自己的钥匙)。
    • 答案实质上是 s u ( n , 1 ) s_u(n,1) su(n,1) n n n个不同元素构成一个环的方案数。
    • 2、如果把官员分成 m m m个部,每个部拥有自己的仓库,仓库和官员数量对应。如何放置钥匙才能使得每一位官员能打开自己部的所有仓库(不考虑官员和他们手里的钥匙),而无法打开其他的任何一个仓库?共有多少种方案?
    • 分析一下就发现,只要把钥匙类似上一问,但放成 m m m个环即可,
    • 这样的方案数正是 n n n个不同元素构成 m m m个环的方案数,
    • 所以答案为 s u ( n , m ) s_u(n,m) su(n,m).

    更多

    第二类Stirling数(第二类斯特林数)
    Stirling数(斯特林数)第一类Stirling数&第二类Stirling数

    更多相关内容
  • 此代码计算(有符号)第一类斯特林数,如维基百科所述: https : //en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind
  • 第一类斯特林数的表示方法为 [nm]\left[\begin{matrix}n\\m\end{matrix}\right][nm​] 或 S(n,m)S(n,m)S(n,m),表示 nnn 个不同的小球串成 mmm 条项链的方案数,考虑第 nnn 个小球的位置,要么接在前面 n−1n-1n−1 ...

    第一类斯特林数

    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 的文明世界   题解

    展开全文
  • 第一类斯特林数

    千次阅读 2019-01-12 12:05:12
    概念 [nk]n \brack k[kn​]表示将nnn...[nk]=[n−1k−1]+[n−1k]×(n−1){n \brack k}= {{n-1} \brack {k-1}}+{{n-1}\brack k}\times (n-1)[kn​]=[k−1n−1​]+[kn−1​]×(n−1) [n−1k−1]n-1 \brack k-1[k−1n−...

    概念

    [ n k ] n \brack k [kn]表示将 n n n个数的序列划分为 k k k圆排列的方案数。

    递推公式

    [ n k ] = [ n − 1 k − 1 ] + [ n − 1 k ] × ( n − 1 ) {n \brack k}= {{n-1} \brack {k-1}}+{{n-1}\brack k}\times (n-1) [kn]=[k1n1]+[kn1]×(n1)
    [ n − 1 k − 1 ] n-1 \brack k-1 [k1n1]表示将最后一个数单独创建一个圆排列的方案数

    [ n − 1 k ] × ( n − 1 ) {n-1\brack k}\times (n-1) [kn1]×(n1)表示将最后一个数插入前面k个圆排列中的方案数。对每个圆排列,能插入的位置数即为圆排列的大小,所以总的插入位置数为n-1。

    多项式表示

    [ n k ] {n \brack k} [kn]为多项式 f n ( x ) = ∏ i = 0 n − 1 ( x + i ) f_n(x)=\prod_{i=0}^{n-1}(x+i) fn(x)=i=0n1(x+i) k k k次项系数。
    比较好想:(不严格证明)
    n = 1 n=1 n=1时显然成立。
    n > 1 n>1 n>1时, f n ( x ) = ( x + n − 1 ) f n − 1 ( x ) = x ⋅ f n − 1 ( x ) + ( n − 1 ) f n − 1 ( x ) f_n(x)=(x+n-1)f_{n-1}(x)=x\cdot f_{n-1}(x)+(n-1)f_{n-1}(x) fn(x)=(x+n1)fn1(x)=xfn1(x)+(n1)fn1(x)
    即,将 f n − 1 ( x ) f_{n-1}(x) fn1(x)右移一位,再加上自己的 ( n − 1 ) (n-1) (n1)倍,列个表出来看看。
      1 x x 2 x 3 . . . x ⋅ f n − 1   [ n − 1 0 ] [ n − 1 1 ] [ n − 1 2 ] . . . ( n − 1 ) f n − 1 ( n − 1 ) [ n − 1 0 ] ( n − 1 ) [ n − 1 1 ] ( n − 1 ) [ n − 1 2 ] ( n − 1 ) [ n − 1 3 ] . . . \begin{array}{c:c:c:c:c:c} \ &1&x&x^2&x^3&...\\\hdashline\\ x\cdot f_{n-1}&\ &{n-1\brack 0}&{n-1\brack 1}&{n-1\brack 2}&... \\\\\hdashline\\ (n-1)f_{n-1}&(n-1){n-1\brack 0}&(n-1){n-1\brack 1}&(n-1){n-1\brack 2}&(n-1){n-1\brack 3}&...\\\\\hdashline \end{array}  xfn1(n1)fn11 (n1)[0n1]x[0n1](n1)[1n1]x2[1n1](n1)[2n1]x3[2n1](n1)[3n1].........
    对应竖着相加, x i x^i xi系数正好为 [ n − 1 i − 1 ] + ( n − 1 ) [ n − 1 i ] = [ n i ] {n-1\brack i-1}+(n-1){n-1\brack i}={n\brack i} [i1n1]+(n1)[in1]=[in]

    倍增求Stirling

    利用上面那个多项式,已经可以用分治FFT求出,时间复杂度 O ( n ⋅ log ⁡ 2 2 n ) O(n\cdot {\log_2}^2n) O(nlog22n)

    还可以更优秀。
    当我们求出 f n ( x ) = ∏ i = 0 n − 1 ( x + i ) f_n(x)=\prod_{i=0}^{n-1}(x+i) fn(x)=i=0n1(x+i),可以更快的求出 g n ( x ) = ∏ i = 0 n − 1 ( x + n + i ) g_n(x)=\prod_{i=0}^{n-1}(x+n+i) gn(x)=i=0n1(x+n+i)
    这样可得 f 2 n ( x ) = f n ( x ) g n ( x ) f_{2n}(x)=f_n(x)g_n(x) f2n(x)=fn(x)gn(x)
    f n ( x ) f_n(x) fn(x)已求出, f n ( x ) = ∑ i = 0 n a i ⋅ x i f_n(x)=\sum_{i=0}^na_i\cdot x^i fn(x)=i=0naixi
    g n ( x ) = ∑ i = 0 n a i ( x + n ) i = ∑ i = 0 n ∑ j = 0 i a i ( i j ) n i − j x j = ∑ i = 0 n ∑ j = 0 i a i i ! ( i − j ) ! ⋅ j ! n i − j x j = ∑ j = 0 n x j j ! ∑ i = j n ( a i ⋅ i ! ) n i − j ( i − j ) ! = ∑ i = 0 n x i i ! ∑ j = 0 n − i ( a i + j ⋅ ( i + j ) ! ) n j j ! \begin{aligned} g_n(x)&=\sum_{i=0}^na_i(x+n)^i \\ &=\sum_{i=0}^n\sum_{j=0}^ia_i{i \choose j}n^{i-j}x^j\\ &=\sum_{i=0}^n\sum_{j=0}^ia_i{\frac {i!} {(i-j)!\cdot j!}}n^{i-j}x^j\\ &=\sum_{j=0}^n\frac {x^j} {j!}\sum_{i=j}^n({a_i}\cdot i!)\frac {n^{i-j}} {(i-j)!}\\ &=\sum_{i=0}^n\frac {x^i} {i!}\sum_{j=0}^{n-i}\big({a_{i+j}}\cdot (i+j)!\big)\frac {n^{j}} {j!} \end{aligned} gn(x)=i=0nai(x+n)i=i=0nj=0iai(ji)nijxj=i=0nj=0iai(ij)!j!i!nijxj=j=0nj!xji=jn(aii!)(ij)!nij=i=0ni!xij=0ni(ai+j(i+j)!)j!nj
    后面一个求和式满足卷积的形式,将一个多项式设为 ∑ i = 0 n a i ( i + j ) ! ⋅ x i \sum_{i=0}^na_i(i+j)!\cdot x^i i=0nai(i+j)!xi,另一个多项式设为 ∑ i = 0 n n i i ! x n − i \sum_{i=0}^n\frac {n^i} {i!}x^{n-i} i=0ni!nixni,两多项式相乘,再左移n位即可。

    于是我们可以倍增求解,每次求出 f n ( x ) f_n(x) fn(x),用 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n)的时间计算出 f 2 n ( x ) f_{2n}(x) f2n(x)
    总时间复杂度为 T ( n ) = T ( n / 2 ) + O ( n log ⁡ n ) = O ( n log ⁡ n ) T(n) = T(n/2) + O(n\log n) = O(n\log n) T(n)=T(n/2)+O(nlogn)=O(nlogn)

    一些能转换为第一类斯特林数的问题

    1.求满足此条件排列的方案数:n个数的排列,有m个数满足,这个数在他的前缀中是最大的。
    这m个数把n个数分成了m段,每段中,最大数一定在最前面,即每一段内的排列,只有相对位置不同,才算不同的排列,就是圆排列。所以方案数为 [ n m ] n\brack m [mn]
    2.留坑。。。。。。。

    展开全文
  • 第一类斯特林数定义为多项式中 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 ...
  • 第一类斯特林数:n 个人坐在 r个圆桌的方案数 :n 个人坐在 r个圆桌的方案数 :最后一个人单独坐一个圆桌 :前面 n - 1个人坐在了 r 个圆桌上,最后一个人坐在前面 n - 1人中的任意一个人的左边。 HDU2625:他...

    第一类斯特林数:n 个人坐在 r个圆桌的方案数

    S[n][r] = S[n-1][r-1] + (n - 1) * S[n - 1][r] 

    S[n][r]:n 个人坐在 r 个圆桌的方案数

    S[n-1][r-1]:最后一个人单独坐一个圆桌

    (n- 1) * S[n-1][r]:前面 n - 1个人坐在了 r 个圆桌上,最后一个人坐在前面 n - 1人中的任意一个人的左边。

    HDU2625:他要最多破 k 个门,即形成最多 k 个循环,不能单独一个形成循环,这样不合法,自己房间的钥匙放在自己的房间里面。

    // 第一类斯特林数 n个球放成r个非空循环
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 20 + 1;
    typedef long long ll;
    ll S[maxn][maxn], A[maxn][maxn];
    void init()
    {
    	S[0][0] = 0, S[1][1] = 1;
    	for(ll i = 2; i < maxn; i++) {
    		for(ll j = 1; j <= i; j++) S[i][j] = S[i-1][j-1] + (i - 1) * S[i-1][j];
    	}
    	for(ll i = 1; i < maxn; i++) {
    		A[i][1] = i, A[i][0] = 1;
    		for(ll j = 2; j <= i; j++) A[i][j] = A[i][j-1] * (i - j + 1);
    	}
    }
    int main()
    {
    	init();
    	int t, n, k;
    	scanf("%d", &t);
    	while(t--) {
    		scanf("%d %d", &n, &k);
    		ll ans = 0;
    		for(int i = 0; i <= k; i++) ans += S[n][i] - S[n-1][i-1];
    		printf("%.4lf\n", 1.0 * ans / A[n][n]);
    	}
    	return 0;
    }
    

     

    展开全文
  • 题目描述 ...第一行两个整数n,m含义如图所述 输出格式 一行一个整数,为答案模1e9+7的值 数据范围 时间限制1s,空间限制:512M 样例1 Input 3 2 Output 3 样例1解释 一共有132、231、213...
  • 该文件仅生成第一类和第二类斯特林数。 输出在同一个调用中提供了两个矩阵。 例如 [SN1,SN2]=mystirling1(n)。 这里,n 是矩阵大小。 这两个矩阵都是带有 int64 元素的正方形。 您可能希望将矩阵转换为 double 以...
  • 将 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)]。 它以英国数学家 James Stirling (1692-1770) 的名字命名。 在统计学中,它用于...
  • 第一类斯特林数学习小记

    千次阅读 2016-03-13 11:48:33
    概念问题来源p个不同人围k个相同圆桌而坐,要求各桌非空,其不同方案第一类StirlingS(p,k)S(p,k) 。问题解决S(p,p)=1(p≥0),S(p,0)=0(p≥1)S(p,p)=1(p≥0),S(p,0)=0(p≥1) 分类讨论。 一,人1独围...
  • 第一类斯特林数  解决问题:给n个元素,求出k个环排列的方法数  Stirling[n][k] 1 1 1 2 3 1 6 11 6 1 24 50 35 10 1 120 274 225 85 15 1 720 1764 1624 735 ...
  • INPUT: N 要分区的集合中的元素输出:个矩阵,其元素 (i,j) 是 S(i,j)
  • 最近做题有时会碰到斯特林数(Stirling数),就觉得好好的学习一番,于是呢,写下这篇博客...,要与大写的第二类斯特林数区分开来,定义上面也讲到了,但是呢,其实那句话最好改成第一类斯特林数的绝对值,因为第一类
  • 第一类斯特林数小结

    2019-04-02 21:33:00
    第一类斯特林数 s1nms1_n^ms1nm​表示将nnn个数放进mmm个圆排列的方案数。 有一个显然的递推式: s1nm=s1n−1m−1+(n−1)s1n−1ms1_n^m=s1_{n-1}^{m-1}+(n-1)s1_{n-1}^ms1nm​=s1n−1m−1...
  • 考试时太弱了不会。 结果被吊起来打。 学习了一下zzd的博客。 首先\(O\left( n^2 \right)\)的递推十分简单。 但是不够快, 根据\(x^{\overline{n}}=\sum_{k=0}^n \left[ n \atop k \right] x^k\) ...就是个\(l...
  • 第一类/第二类斯特林数学习笔记
  • 链接: ... 题意: 有N个房间,每个房间里有一把钥匙,钥匙随机分配。如果手中有对应的钥匙,就可以开门,如果没有钥匙就只能选择破门而入拿钥匙, ...第一类斯特林数 代码: 31 ll stir[25...
  • 第一类斯特林数: 我们考虑这样一个问题:有n个互不同的小球,拼成k个环,有几种拼法。数据量:n&amp;amp;amp;amp;lt;=1000 这样的数据量,不难看出是一个n^2的DP或者说递推。 我们假设S(n,k)表示前n个小球,...
  • 记xn‾=x(x+1)(x+2)⋯(x+n−1)x^{\overline{n}}=x(x+1)(x+2)\cdots(x+n-1)xn=x(x+1)(x+2)⋯(x+n−1),xn‾=x(x−1)(x−2)⋯(x−n+1)x^{\underline{n}}=x(x-1)(x-2)\cdots(x-n+1...第一类斯特林数 定义为xn‾x^{\over...
  • 斯特林数
  • 第一和第二类斯特林数小结

    千次阅读 2018-07-02 12:01:03
    第一类斯特林数 暑假里,小L到海边去玩,捡了nnn个不同的贝壳。现在她想把这些贝壳串成kkk个项链(项链是环形的)。她忽然很疑惑,这有多少种方案呢? 聪明的小L很快想到,假设S1(n,k)S1(n,k)S_1(n,k)为nnn个贝壳...
  • 第一类斯特林数和第二类斯特林数

    万次阅读 2017-08-22 20:57:21
    第一类Stirlings(p,k)是将p个有区别的求排列成k个非空的圆排列的方案。其中任一方案可表为:将p个求分成非空的k份,再把每份中的球排成一个圆,n个球的圆排列为(n-1)!。 第二StirlingS(p,k)是将p个有...
  • 第一类斯特林数·行

    2021-03-28 23:31:13
    } void init(int n,int m) { //n,m表示最高长度,每次运算调用次 lim=1,bit=0; while(lim<n+m-1) lim<<=1,bit++; _inv=qpow(lim,mod-2); for(int i=0; i; i++) r[i]=(r[i>>1]>>1)|((i&1)(bit-1)); } void NTT(ll *...
  • 类斯特林数

    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...
  • 要想实现python实现类斯特林数详细所有情况,首先我们要了解将个整数拆分非0整数的所有情况(已经写了相应的博客),详细的理论这个博客就不讲了,大家可以去参考我的其他两篇博客  将个整数拆分各种情况...
  • 第一类斯特林数有递推公式S(n,m)=S(n−1,m−1)+(n−1)×S(n−1,m) 证明:我们考虑把第n个元素放在什么位置。如果单独形成一个圆排列,则答案就是S(n-1,m-1). 如果插入到原来的m个圆排列中,那本质上就是在n-1个元素...
  • 1、考虑的是组合数概念(无符号的斯特林数) S(n,m)S(n,m)S(n,m)表示把n个不同的球放入m个相同的盒子中,不允许有空盒的方案,而且注意,这个盒子很有意思,这些球只能放成圈且如果顺序不同也视为不同方案。 2、...

空空如也

空空如也

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

第一类斯特林数

友情链接: PE View.rar