f: N -> M 将n个求放入m个盒子中的多种方式
distinct: 不同 identical: 相同
| balls per bin | unrestricted | <=1 | >=1 |
|---|---|---|---|
| n distinct balls , m distinct bins | $m^n$ | $(m)_n$ | $m!\begin{Bmatrix} m \ n \end{Bmatrix}$ |
| n identical balls , m distinct bins | $(\binom{n}{m})= \binom{n+m-1}{m-1}$ | $\binom{m}{n}$ | $\binom{n-1}{m-1}$ |
| n distinct balls , m identical bins | $\sum_{i=1}^m \begin{Bmatrix} n \ i \end{Bmatrix}$ | $\begin{cases} 1 &n \le m \ 0 & n>m \end{cases}$ | $\begin{Bmatrix} n \ m \end{Bmatrix}$ |
| n identical balls , m identical bins | $\sum_{i=0}^m{p_i(n)}$ (当m>=n时也可以直接表示为p(n)) | $\begin{cases} 1 &n \le m \ 0 & n>m \end{cases}$ | $p_m(n)$ |
映射
理解映射 $f: A \rightarrow B$的关键是抓住集合A中元素在集合B中的象的存在性和唯一性。根据映射中象与原象的不同状态，有下面几种有用的映射关系。
- 单射：对于映射 $f: A \rightarrow B$，如果A中不同的元素在B中有不同的象，那么称映射 $f: A \rightarrow B$为集合A到B的单射。
对于单射 $f: A \rightarrow B$，有$|A| \le |B|$。这里|M|表示集合M中的元素个数 - 满射：对于映射 $f: A \rightarrow B$，如果B中的每一个元素在A中都有原象，那么映射 $f: A \rightarrow B$为集合A到集合B的满射。
对于满射 $f: A \rightarrow B$，有$|A| \ge |B|$。 - 双射：如果映射 $f: A \rightarrow B$同时是A到B上的单射和满射，那么称映射 $f: A \rightarrow B$为集合A到B的双射。双射也叫做一一映射。
对于双射 $f: A \rightarrow B$，有$|A| = |B|$。
上述的表格我看作一个4*3的矩阵，根据对应位置来解释对应的答案。
符号定义
先来了解一下一些对应符号的定义
- $(m)_n$也就是平时我们理解的排列数从m个数当中取n个数做全排列，$(m)_n = \frac {m!}{(m-n)!}$
- $\binom{m}{n}$组合数从m个球中取n个球得到的方法种数，$\binom{m}{n} = \frac{m!}{n!(m-n)!}$
- $\begin{Bmatrix} n \ k \end{Bmatrix}$第二类斯特林数，具体数学上给出的是表示将一个有n件物品的集合划分成k个非空子集的方法数
对应就有第一类斯特林数$\begin{bmatrix} n \ k \end{bmatrix}$，表示将n个元素排成k个轮换。- $p_m(n)$将正整数n划分成m个正整数相加的方法数（只是交换了数字的顺序视为等价）
- $p(n)$就是划分函数或者分割函数我的对应博客中有具体地讲解。
斯特林数
第二类斯特林数
$\begin{Bmatrix} n \ k \end{Bmatrix} =k \begin{Bmatrix} n-1 \ k \end{Bmatrix} + \begin{Bmatrix} n-1 \ k-1 \end{Bmatrix}$
上述的递归式很容易理解为最后一个物品是否单独形成一个等价类形成了两种可能，如果它不单独形成等价类，它可以加入其他k各等价类中，所以乘以k，否则单独形成等价类。
n个不同球放入m个不同箱子，保证每个箱子球数量大于1的解释
因为这里球和箱子各不相同，所以可以作为集合中的元素看待.
根据映射原理：n个球属于集合A，m个箱子属于集合B，保证每个箱子球数量大于1，说明这是个$f:A \rightarrow B$满射。
$$
\forall i \in B \quad f^{-1}(i) \ne 0 \\
(f^{-1}(B_1),f^{-1}(B_2),f^{-1}(B_3),…,f^{-1}(B_m)) ->构成了一个有序的n元集合的m组划分
$$
简单理解就是
$f^{-1}(B_i)$得到的是A中映射到B中第i个元素的一组元素的集合。
假定如上构成的这m组划分是有序的，那么就理解为将n个不同的元素划分到m个集合内，这就是一个第二类斯特林数$\begin{Bmatrix} n \ m \end{Bmatrix}$，然后实际上m个箱子的不同，它任意交换顺序可构成m!种有序集合。
所以总的方法数量就是$m! \begin{Bmatrix} n \ m \end{Bmatrix}$。
n个相同的球放入m个不同箱子的解释
最简单地说就叫插板法。
如果每个箱子要求数量都>=1，那么就相当于在n个球的n-1个间隔中找到m个间隔插入隔板，这样就区分出来了m个箱子中的球的数量。
那么当可以要求任意数量的时候，那么也就是说明箱子中可以是0个球，但为了保证两个隔板间至少要有球作区分，那么只要将n+m，让每个箱子都在原基础上多加一个球即可。
$p_k(n)$
当x限定将n表示成刚好k个正整数之和时，可以表示为$p_k(n)$。显然$p(n) = \sum_{k=1}^n{p_k(n)}$
性质
- 对于n>1, $p_n(n) = p_1(n) = 1$
- $p_2(n) = \left\lfloor n/2 \right\rfloor$ (OEIS:A004526)
- $p_3(n)= 最接近n^2/12的正整数$。(OEIS:A069905)
- $p_{n-1}(n) = 1$
- $p_k(n) = p_{k-1}(n-1) + p_k(n-k)$。
1.最小的那个数字是1时，除去那个数字，剩余个数为k-1
2.最小的数字大于1时，将每个位置上的数字都减去1，共减了k，剩余数字个数为k
$p_k(n)$能够抽象表示为n个相同的球放入m个相同的箱子的方法种数。
我们构建一个关于S -> T的映射
我们可以知道的对于S->T的映射
1)单射情况下 $|S| \le |T|$
2)满射情况下 $|S| \ge |T|$
根据单射和满射的情况，这是一个很优秀的计算出上下界的方法
我们构建划分和组合两种方式
$$
\begin{aligned}
partition \quad
& \begin{cases}
x_1+x_2+ … +x_k = n \\
(x_1,x_2,…,x_k) & x_1\ge x_2 \ge … \ge x_k \ge 1
\end{cases}
\\
\\
composition \quad
& \begin{cases}
x_1+x_2+ … +x_k = n \\
(x_1,x_2,…,x_k) & x_i \ge 1
\end{cases}
\end{aligned}
$$
对于partition的结果k个数字可以任意排序，建立一个集合S，对于composition建立一个集合T，那么S到T的映射必然是满射的，因为必然包含了T中所有的结果，S中甚至可能会出现重复的部分，那么就能得知：
$|S| \ge |T| \Leftrightarrow k!p_k(n) \ge \binom{n-1}{k-1}$.
同理对于partition的结果k个数字可以任意排序，建立一个集合S，对于composition建立一个集合T，希望S到T的映射必是单射的，那么只有在任意$x_i$和$x_j$不相等的情况下成立，那么就构造$x_1+k-1 \ge x_2+k-2 \ge … \ge x_k \ge 1$，因为是单射就能得到如下结果
$|S| \le |T| \Leftrightarrow k!p_k(n) \le \binom{n+(k-1)k/2-1}{k-1}$.
$$
\frac{\binom{n-1}{k-1}}{k!} \le p_k(n) \le \frac{\binom{n+(k-1)k/2-1}{k-1}}{k!}
$$
那么由n趋向于无穷，可以推算得知这趋向于一个极限。
