欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

第二类斯特灵数学习笔记

程序员文章站 2023-11-02 13:54:40
简单的介绍一下吧,斯特灵数其实有很多好玩的性质和扩展的。 定义 设$S(n, m)$表示把$n$个 不同的球 放到$m$个相同的盒子里,且不允许盒子为空的方案数 称$S$为第二类斯特灵数 计算方法 递推: 考虑第$n$个球放到了哪里 第一种情况是自己占一个盒子,方案为$S(n 1, m 1)$ 第二 ......

简单的介绍一下吧,斯特灵数其实有很多好玩的性质和扩展的。

定义

设$s(n, m)$表示把$n$个不同的球放到$m$个相同的盒子里,且不允许盒子为空的方案数

称$s$为第二类斯特灵数

计算方法

递推:

考虑第$n$个球放到了哪里

第一种情况是自己占一个盒子,方案为$s(n - 1, m - 1)$

第二种情况是和之前的元素共占$m$个盒子,方案为$s(n - 1, m) * m$,最后的系数是考虑放在不同位置。

这里我们认为{1}{2 4}{3}与{1}{2}{3 4}是不同的方案

而{1}{2 4}{3}与{1}{3}{2 4}是相同的方案

综上

$s(n, m) = s(n - 1, m - 1) + s(n - 1, m) * m$

边界条件$s(0, 0) = 1$

容斥

$s(n, m) = \frac{1}{m!} \sum_{k = 0}^m (-1)^k c(m, k) (m - k)^n$

也比较好理解,我们去枚举一个空盒子的个数

答案 = 无视空盒子放的方案 - 至少有一个盒子为空的方案 + 至少有两个盒子为空的方案 + $\dots$

显然,这个式子可以用fft优化,因此我们可以在$o(nlogn)$的复杂度内得到一行的斯特灵数

性质

  1. $$n^k=\sum_ { i=0}^k s(k,i)×i!×c_{n}^i$$

  2. $s(n, 2) = 2^{n - 1} - 1$