组合数八题->赫拉克勒斯的12试炼
Garrison
·
·
个人记录
更好的阅读体验请移步到
前置知识
组合数
\LARGE\tbinom{n}{m} = \frac{n!}{(n-m)!m!}
第二类 Stirling 数
递推式:$\LARGE {n \brace m}=m{n-1 \brace m}+{n-1 \brace m-1}
{n \brace 0} = 1 (n \geq 0) \\ {n \brace n} = 0 (n > 0)
通项: \LARGE {n \brace m} = \frac{1}{m!}\sum_{i=0}^{m}(-1)^i\tbinom{m}{i}(m-i)^n
划分数
将 n 划分为 k 个正整数的方案数，求出划分方法数
递推式
paritition(n,m)=
\left\{
\begin{matrix}
partition(n,n)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(n<m)\\
partition(n-1,m-1)+partition(n-m,m)~~~~(n\geq m)\\
1~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(n=0~||~m=1)
\end{matrix}
\right.
正文
有无标号记为 $L/U$。
**限制：**
$A.$ 每个盒子可以为空
$B.$ 每个盒子不能为空
$C.$ 每个盒子最多有一个球
$ Part_1:(LLA)
$$
Sol:~~~~m^n
$$
$Part_2:(LLB)
转化成 Part_8(LUB) ,求出 n 个不同的求在 m 个相同盒子不允许为空的方案数，再乘以 m 个盒子的全排列数。
Sol:~~~~m!{n \brace m}
Part_3:(LLC)
分 n \leq m 和 n > m 讨论，n \leq m 相当于在 m 个位置中选 n 个位置进行全排。
Sol:~~~~\left\{
\begin{matrix}
P_{m}^{n}~~~~(n \leq m)\\
0~~~~~~~~(n>m)
\end{matrix}
\right.
Part_4:(ULA)
考虑插板法，但是会出现多个盒子插入到同一个空隙中，不能确定顺序。
首先，添加m个球到m个盒子中，默认了每一个盒子保证了有一个球，相当于盒子不能为空的情况，但是对方案数的推导没有影响。
此时有n+m个球，问题转化为于不同且不可为空的盒子放入相同的球的情况，就变成了普通的插板法。
Sol:~~~~\tbinom{n+m-1}{m-1}
Part_5:(ULB)
普通的插板法，相当于把 n 个球用 m-1 个不同的板子分成 m 份，组合数即可
Sol:~~~~\tbinom{n-1}{m-1}
Part_6:(ULC)
$$
Sol:~~~~\left\{
\begin{matrix}
\tbinom{m}{n}~~~(n\leq m)\\
0~~~~~~~(n > m)
\end{matrix}
\right.
$$
$Part_7:(LUA)
为 n 个不同的球放在 1\sim m 个相同且不为空的盒子的方案数的总和，转化成 Part_8(LUB) .
Sol:~~~~\sum_{i=1}^{m} {n \brace i}
Part_8:(LUB)
第 n 个球放在第 m 个盒子，其余的放在其余的格子，第 n 个球任意放，乘上 n-1 个球放在 m 个盒子中的方案数，这样能保证一定没有空盒子
见第二类斯特林数的定义，由此可知
Sol:~~~~{n \brace m}
Part_9:(LUC)
无论怎么放都是一样的
Sol:~~~~[n\leq m]
Part_{10}:(UUA)
为 n 个相同的球放在 1\sim m 个相同的且不为空盒子的方案数的总和，转化成 Part_{11}(UUB) .
Sol:~~~~\sum_{i=1}^{m} partition(n,i) = partition(n+m,m)
Part_{11}:(UUB)
就是前置中提到的划分数，类比
分两种情况
1.$ 给一个盘子放上 $1$ 保证不为空 $:partition(n, m) = partition(n, m-1)
$$
Sol:~~~~partition(n,m)
$$
$Part_{12}:(UUC)
无论怎么放都是一样的。
Sol:~~~~[n\leq m]