数组合数学

放球模型总结-集合间映射计数

字数统计: 1.1k字   |   阅读时长: 4分
, ,

摘要: 12 种放球模型，以及对应的集合间映射的角度的理解

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在 组合数学1-排列组合 中，我们大致串一下基础排列组合的公式，其中放球模型是一种重要的理解组合计数的模型。本文我们系统地梳理放球模型的各种变种，共 12 种，同时这 12 种放球模型可以与两个集合间的映射的计数进行对应。本文直接给出结论，供参考，证明一般用母函数即可。

12 种放球模型

把 n 个球放入 m 个盒子中，有多少种放法。

n 个球完全相同还是各不相同；m 个盒子，是 1 ~ m 有编号还是不加区分；放球方式是每个盒子不能空、最多放一个球，还是没有限制。最终的结果不一样。

编号 n个球是否相同 m个盒是否相同 每盒个数限制 放法个数 备注
1 球不同 盒不同 无限制 $m^{n}$ 每个球都能放进任意盒子里
2 球不同 盒不同 每盒最多1个 $P(m, n) = (m)_{n}$ 依次考虑每个球挑一个盒放进去，之后，下一个球可以放的盒就少了一个。
3 球不同 盒不同 每盒至少1个 $m!S(n, m)$ 考虑容斥原理，在确定有 i 个空盒之后转化为 1，$\sum\limits_{i=0}\limits^{m}(-1)^{i}\binom{m}{i}(m-i)^{n}$；也可以考虑当盒子相同时，转化为 6，而这里盒子不同，需要乘一个 $m!$
4 球不同 盒相同 无限制 $\sum\limits_{i=1}\limits^{m}S(n, i)$ 若有 i 个盒子非空，则由第二类斯特林数定义，答案为 $S(n, i)$，枚举所有 i，对第二类斯特林数按行求和
5 球不同 盒相同 每盒最多1个 $\delta(n\leq m)$ 球放到哪个盒子都一样。考虑盒子能不能放下所有球即可
6 球不同 盒相同 每盒至少1个 $S(n, m)$ 第二类Strling数的定义
7 球相同 盒不同 无限制 $\binom{n+m-1}{n}$ 隔板法
8 球相同 盒不同 每盒最多1个 $\binom{m}{n}$ 组合数定义
9 球相同 盒不同 每盒至少1个 $\binom{n-1}{m-1}$ 隔板法
10 球相同 盒相同 无限制 $p_{m}(n)$ 相当于把 n 划分为 m 个自然数的方法数，也就是m 部分拆数的定义 $p_{m}(n)$
11 球相同 盒相同 每盒最多1个 $\delta(n\leq m)$ 与 5 一样，球放到哪个盒子都一样。考虑盒子能不能放下所有球即可
12 球相同 盒相同 每盒至少1个 $p_{n-m}(n)$ 先给所有盒子各强制塞一个球进去，转化为 10。

其中：

  • $(m)_{n}$ 是下降幂
  • $S(n, m)$ 是第二类 Stirling 数
  • $p_{m}(n)$ 是分拆数
  • $\delta(n\leq m)$ 的定义如下

12 种两集合间映射模型

集合 A 的基数为 n，集合 B 的基数为 m，有多少个从 A 到 B 的映射 $f: A \rightarrow B$。

编号 集合A中的元素(基数n) 集合B中的元素(基数m) 映射 $f$ 的限制 $f$ 的个数
1 各自不同 各自不同 不加限制 $m^{n}$
2 各自不同 各自不同 单射 $P(m, n) = (m)_{n}$
3 各自不同 各自不同 满射 $m!S(n, m)$
4 各自不同 全部相同 不加限制 $\sum\limits_{i=1}\limits^{m}S(n, i)$
5 各自不同 全部相同 单射 $\delta(n\leq m)$
6 各自不同 全部相同 满射 $S(n, m)$
7 全部相同 各自不同 不加限制 $\binom{n+m-1}{n}$
8 全部相同 各自不同 单射 $\binom{m}{n}$
9 全部相同 各自不同 满射 $\binom{n-1}{m-1}$
10 全部相同 全部相同 不加限制 $p_{m}(n)$
11 全部相同 全部相同 单射 $\delta(n\leq m)$
12 全部相同 全部相同 满射 $p_{n-m}(n)$
Share