notes

基础计数

盒子与球

默认以下盒子为m 球为n

1. 盒子不同 球相同
   • 不能为空 直接插板->C(n-1,m-1)
   • 可以有空 加入m个球使得变为上面问题
2. 盒子相同 球不同
   • 不能有空 相当于划分集合 方案不同当且仅当有一个集合的元素不同 那么就是第二类斯特林数
   • 可以有空 则枚举空的数量(无序)
3. 盒子相同 球也相同
   • 这就是个数的划分

<span id="skip">数的划分 </span>

往往是一类集合无序球也无差别的问题

1. n划分成k个数(f[n][k])
   • 就是k个
     - 使得最后结果每个位置都>=2 则先提出k个来放到每一个位置f[n-k][k]
     - 有为1的位置 则保证它存在f[n-1][k-1]
   • 不超过k个(可以有0)
     - 上述第二种变为f[n][k-1] 就相当于放了个0堆
2. n划分成不大于k的数f[n][k]
   • 可以有重
     - 每个数都<k f[n][k-1]
     - 有数为k f[n-m][m]
   • 每个数不同
     - 有数为k 使得之前的数不能为k -> f[n-m][m-1]

<span id="jump">####第二类斯特林数</span>

n个有差别元素划分为m个无序集合

1. 求法
   • 递推式 (n^2)
     • 第i个元素放一个新的集合 s[i-1][j-1]
     • 第i个元素放入已有集合 s[i-1][j]*j

• 通项式求一行(FFT -> nlogn) [图片上传失败...(image-7439a9-1516201501882)]

2. 要记的应用
   转换下降幂与自然幂 [图片上传失败...(image-bdb879-1516201501883)]
   n的k次下降幂是n(n-1)(n-2)…(n-k-1)
   有个小性质 n(k+1)=n(k)(n-k)
   那么实际上 i^k 就是 sigma(S(k,j)j!*C(i,j))后面那一坨就是下降幂

错排

每个位置都不是原本的数的方案数
两种递推形式
f[i]=(i-1)(f[i-1]+f[i-2]) f[i]=f[i-1]i(-1)^i
一种非递推(也是O(n)不知道有什么意义的形式) f[i]=sum{(-1)^in!/i!}