盒子与球12态（1）

windphoenix · 2023-09-17 01:18:39 · 个人记录

盒子与球十二态（一）

课件下载

基础函数

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

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

排列：

组合：

S(n,k)

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

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

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

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

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

so:

P(n,k)

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

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

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

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

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

边界：

浅浅推一下递推式 QWQ

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

so:

盒子与球

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

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

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

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

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

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

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

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

状态讲解

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

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

无限制，可有空集。

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

so：

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

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

每盒最多一球。

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

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

so:

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

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

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