zcmimi's blog

arrow_back第二类斯特林数共2篇文章

avatar
zc
2020-07-05 13:10:00
查看原题

点击跳转

此题要求的是S(n,m) \mod 2(第二类斯特林数)

  1. m为偶数,S(n,m) \equiv S(n-1,m-1)

  2. m为奇数,S(n,m) \equiv S(n-1,m-1)+s(n-1,m)

这样的话,相当于:

  1. (x,y)y为奇数时,可以走到(x+1,y+1)(a变换)

  2. 否则可以走到(x+1,y+1)(a变换),或(x+1,y)(b变换)

求从(0,0)走到(n,m)的方案数\pmod 2

这个过程必然走了ma变换,走了n-mb变换

b变换只能在偶数位置出现,那么变换的序列必然是如下形式:

a,b\times ?,a,a,b\times ?,a,a,...,a

也就是在\frac {m+1}2个间隔中插入n-mb,即隔板法

方案数:C(n-m+\frac{m+1}2-1,\frac{m+1}2 -1) \mod 2

还有一个结论:仅当n\&m=m时,C(n,m) \equiv 1 \bmod 2(lucas定理代入即可推出)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

第二类斯特林数

n个不同的球放进m个相同的盒子,保证盒子非空,求方案数。

容斥法:

S(n,m)=\frac 1{m!}\sum_{i=0}^m {m\choose i}(m-i)^n(-1)^i

枚举空盒个数,剩下随便放,到这里开始也有了二项式反演的形式

由于盒子相同,所以除以m!

递推法:

S(n,m)=S(n-1,m-1)+mS(n-1,m)

相当于考虑现在要放的求是否单独在一个盒子里:

  1. 不占一盒:

    其余n-1个球放到m-1个盒子里

  2. 放到某个有球的盒子里:

    m个盒子可放(m种可能),其余n-1个球放到m个盒子里

此题要求的是S(n,m) \mod 2

m为偶数,S(n,m) \equiv S(n-1,m-1)

m为奇数,S(n,m) \equiv S(n-1,m-1)+s(n-1,m)

这样的话,相当于:

(x,y)y为奇数时,可以走到(x+1,y+1)(a变换

否则可以走到(x+1,y+1)(a变换,或(x+1,y)(b变换

求从(0,0)走到(n,m)的方案数\mod 2

这个过程必然走了ma变换,走了n-mb变换

b变换只能在偶数位置出现,那么变换的序列必然是如下形式:

a,b\times ?,a,a,b\times ?,a,a,...,a

也就是在\frac {m+1}2个间隔中插入n-mb,即隔板法

方案数:C(n-m+\frac{m+1}2-1,\frac{m+1}2 -1) \mod 2

还有一个结论:仅当n\&m==m时,C(n,m) \equiv 1 \bmod 2

1/1
Search
search