盒子与球十二态

课件下载

$n$ 个球	$k$ 个盒子	无限制	每盒最多一球 $(n\leq k)$	每盒至少一球 $(k\leq n)$
全不同	全不同	$k^n$	$A^n_k$	$k!\times S(n,k)$
全相同	全不同	$C^{k-1}_{n+k-1}$	$C^n_k$	$C^{k-1}_{n-1}$
全不同	全相同	$\sum_{i=1}^{k}S(n,i)$	$1$	$S(n,k)$
全相同	全相同	$P(n+k,k)$	$1$	$P(n,k)$

---

基础函数

分类加法原理：做一件事情，有多种方式，每个方式有多种路径，将每个方式的路径数相加。

分步乘法原理：做一件事情，有多个阶段，每个阶段有多种选择，将每个阶段的选择数相乘。

排列：$A^m_n=n\times(n-1)\times...\times(n-m+1)$

组合：$C^m_n=A^m_n/A^m_m$

$S(n,k)=S(n-1,k-1)+S(n-1,k)\times k$

$P(n,k)=P(n-1,k-1)+P(n-k,k)$

---

$S(n,k)$

我们可以把它分为两种情况讨论：

• 上一层少少一个球，一个盒子：$S(n-1,k-1)$

• 上一层少一个球，盒子相同，这一层可放在任意一个盒子里：$S(n-1,k)\times k$

少一个球 $n-1$，少一个盒子 $k-1$，这一层这个空盒子放一个球。

少一个球 $n-1$，盒子相同 $k$，这一层可放在任意一个盒子里 $k$ 。

$so:$

$S(n,k)=S(n-1,k-1)+S(n-1,k)\times k$

---

$P(n,k)$

我们也可以把它分为两种情况讨论：

• 存在一个盒子只有一个球的情况：$P(n-1,k-1)$

• 不存在一个盒子只有一个球的情况：$P(n-k,k)$

存在，就有一个盘子有一个球。所以 $n-1$ ，球放一个，$k-1$ 盘子少一个。

不存在，就把所有盘子都放上一个。所以 $n-k$ ，球少 $k$ 个， $k$ 盘子不变。

边界：

$P(n,k)=\begin{cases} 0(n<k)\\ 1(k=1)\\ 1(n=k) \end{cases}$

浅浅推一下递推式 $QWQ$

最后数一下 “ $1$ ” 的个数就行了

$so:$

$P(n,k)=P(n-1,k-1)+P(n-k,k)$

---

盒子与球

盒子与球，就是有 $n$ 个东西放进 $k$ 个集里。

球不相同，实际是指球之间的组合有意义。

球全相同，实际是指球之间的组合无意义。

盒子不相同，实际是指盒子之间的排列有意义。

盒子全相同，实际是指盒子之间的排列无意义。

无限制，实际是指可有空集。

每盒最多一球，实际是指每盒最多一球废话。

每盒至少一球，实际是指不可有空集。

---

状态讲解

$k^n$

球不相同，球之间的组合有意义。

盒子不相同，盒子之间的排列有意义。

无限制，可有空集。

根据分步乘法原理，每个球可以去任何一个集。

$so：$

$k\times k \times...\times k(n$ 个 $k$ 相乘$)$

---

$A^n_k$

球不相同，球之间的组合有意义。

盒子不相同，盒子之间的排列有意义。

每盒最多一球。

可以把它变成考虑，每个球放在那个盒子，每个球不重复放在同一个盒子里。

也就是，第 $1$ 个球可以选择 $k$ 种方案$_{(可放在 k 个盒子里)}$，第 $2$ 个球可以选择 $k-1$ 种方案...第 $n$ 个球可以选择 $k-n$ 种方案。

$so:$

$n\times(n-1)\times...\times(n-k+1)$

---

$k!\times S(n,k)$

球不相同，球之间的组合有意义。

盒子不相同，盒子之间的排列有意义。

每盒最少一球，指不可有空集。

$k!$ 在这里的作用其实同 $A^n_k$ ，只是 $(n=k)$，为了盒子之间的排序。

$S(n,k)=S(n-1,k-1)+S(n-1,k)$ 如上

---

第二章 第三章 第四章