组合数学中将物体放入盒子中的四种情况

luixiao1220

3074人浏览 · 2022-05-20 22:21:10

luixiao1220 · 2022-05-20 22:21:10 发布

在实现生活中，如何将物体分配到盒子里面是一个非常普通且常见的一个问题。
要解决这个问题需要考虑几种清空。
首先我们把这个问题分成四个类别的的问题。

将不同的物体分配到不同的盒子中
将相同的物体分配到不同的盒子中
将不同的物体分配到相同的盒子中
将相同的物体分配到相同的盒子中

将不同的物体分配到不同的盒子中

举例：如果将52张扑克开（一套扑克牌）分配给4个玩家，每人5张牌。
有多少种分配方法？
解答：这个问题就是典型的将不同的物体分配到不同的盒子中的问题。
要解决这个问题其实很简单，只需要采用乘法原理即可。采用五个步骤，
第一步分配给第一个玩家，第二步分配给第二个玩家，并以此类推。

$(525)(475)(425)(375)=52!5!5!5!5!32!\binom{52}{5}\binom{47}{5}\binom{42}{5}\binom{37}{5}=\frac{52!}{5!5!5!5!32!}$
总结：将n个不同的物体分配给k个不同盒子，
并且每一个盒子分配得到的数量是 $,kn_i, i=1,2,\cdots, k$ .
分配方案的个数是 $n!n1!n2!⋯nk!\frac{n!}{n_1!n_2! \cdots n_k!}$

将相同的物体分配到不同的盒子中

举例：对于算式 $a,b,c,d\in \mathbb{N}$ . 请问 $a, b, c, d$
有多少种不同的取值？
解答: 这个问题相当于用隔板去把10个1，分割来开。
隔板的数量是3就可以了。注意这里不能用插入，插入会造成重复。
而是选择隔板的位置。从10+3个位置中选择3个位置的隔板。

$(133)=(10+4−14−1)\binom{13}{3}=\binom{10+4-1}{4-1}$
总结：将n个相同的物体分配到r个不同的盒子中，总的分配方案是

$(n+r−1r−1)\binom{n+r-1}{r-1}$

将不同的物体分配到相同的盒子中

虽然看起来这个问题比较简单，但是这个问题比前面两个问题都要复杂得多。
这个问题没有一个统一的公式。因为包含很多种情况。比如只放在一个盒子里，
只放在两个盒子里面，等等。这其中，每个盒子不为空的情况有统一公式，
这个公式在机器学习中的应用就是聚类。把n个不同的物体聚成4类，
这四个类别其实就是4个相同的盒子。但是这个问题有一个要求及时每个盒子不能为空，
否则不能聚为一个类别。这个问题的答案其实就是第二类的Stirling数。

n个不同的对象分到k个相同的盒子里面, 要求每个盒子至少有一个对象.
有多少种分法. 这是在k均值聚类里面的一个组合数学问题.
在k均值聚类里面有n个对象各不相同,
要把这个n个对象分到k个类别里面并要求每个类别必须至少含有一个对象.
总共的分法有多少中? 这道题的答案是第二类的stirling number.
我们来看看如何来求解.我们把原问题定义为 $P (n, k)$

初探

如果将n个不同的对象放到k个不同的盒子里面总共有多少种方法?
这个问题不再限制每个盒子必须含有一个对象. 我们定义这个事件为 $S$ ,答案是
$S|=k^n$

接下来,
我们再来定义特殊的几个事件.我们先假设盒子各不相同并且有 $k$ 个盒子.
设 $A_i$ 表示第 $(1\leqslant i\leqslant k)$ 个盒子是空的事件.
那么,我们定义下面一个事件

$Sn,k=A‾1∩A‾2∩⋯∩A‾kS_{n,k}=\overline{A}_1\cap \overline{A}_2 \cap \cdots \cap \overline{A}_k$

事件 $S_{n,k}$ 表示, $k$ 个盒子都非空.

$∣Sn,k∣=∣S∣−∣A1∪A2∪⋯∪Ak∣|S_{n,k}|=|S|-|A_1\cup A_2\cup \cdots \cup A_k|$

如果我们能够计算出 $S_{n,k}|$ 那么 $P(n,k)=1k!∣Sn,k∣P(n,k)=\frac{1}{k!}|S_{n,k}|$

容斥原理

现在我们剩下的唯一目的就是计算 $∣A1∪A2∪⋯∪Ak∣|A_1\cup A_2\cup \cdots \cup A_k|$ .
而这个集合可以使用容斥原理来计算

$∣A1∪A2∪⋯∪Ak∣=∑i=1k∣Ai∣−∑i≠jk∣Ai∩Aj∣+∑i≠j≠hk∣Ai∩Aj∩Ah∣+⋯+(−1)k∣A1∩A2∩⋯∩Ak∣|A_1\cup A_2\cup \cdots \cup A_k| = \sum_{i=1}^{k}|A_i|-\sum_{i\neq j}^k|A_i\cap A_j|+\sum_{i\neq j \neq h}^{k}|A_i\cap A_j\cap A_h|+\cdots+ (-1)^k|A_1\cap A_2\cap \cdots \cap A_k|$

$∣A1∪A2∪⋯∪Ak∣=(k1)(k−1)n−(k2)(k−2)n+(k3)(k−3)n+⋯+(−1)k−1(kk)(k−k)n|A_1\cup A_2\cup \cdots \cup A_k|=\binom{k}{1}(k-1)^n-\binom{k}{2}(k-2)^n+\binom{k}{3}(k-3)^n+\cdots + (-1)^{k-1}\binom{k}{k}(k-k)^n$

最后可得

$∣Sn,k∣=∣S∣−∣A1∪A2∪⋯∪Ak∣=(k0)(k−0)n−(k1)(k−1)n+(k2)(k−2)n+(k3)(k−3)n+⋯+(−1)k(kk)(k−k)n=∑i=0k(ki)(−1)i(k−i)n\left. \begin{aligned} |S_{n,k}|&=|S|-|A_1\cup A_2\cup \cdots \cup A_k|\\ &=\binom{k}{0}(k-0)^n-\binom{k}{1}(k-1)^n+\binom{k}{2}(k-2)^n+\binom{k}{3}(k-3)^n+\cdots + (-1)^{k}\binom{k}{k}(k-k)^n\\ &=\sum_{i=0}^{k}\binom{k}{i}(-1)^i(k-i)^n \end{aligned} \right.$

最后得到第二类stirling number为

$P(n,k)=1k!∣Sn,k∣=1k!∑i=0k(ki)(−1)i(k−i)nP(n,k)=\frac{1}{k!}|S_{n,k}|=\frac{1}{k!}\sum_{i=0}^{k}\binom{k}{i}(-1)^i(k-i)^n$

总结

至此，我们可以最终得到我们原问题的答案

$∑r=1kP(n,r)\sum_{r=1}^{k}P(n,r)$

即分成好几种情况进行处理，每一种是一个Stirling Number。

将相同的物体分配到相同的盒子中

这个问题其实也没有一个简单的统一公式，我们把这个问题的解设为 $H (n, k)$ ,
即把n个相同的物体分配给k个相同的盒子. 这个问题也是要分情况考虑的，
比如所有的对象放到一个，两个，三个，等等，
并且每一个盒子非空。我们用 $W (n, k)$ 来表示将n个相同的物体放倒k相同的盒子中，
并且每个盒子非空。那么原问题就等于

$H(n,k)=∑r=1kW(n,r)H(n,k)=\sum_{r=1}^{k}W(n,r)$

那么，这个问题转为话求 $W (n, r)$ .

$W(n,r)=∑j=1rW(n−r,j)=H(n−r,r)W(n,r)=\sum_{j=1}^{r}W(n-r,j)=H(n-r, r)$

这是因为，
每一个盒子分走一个之后剩下的就只有 $n - r$ 个物体。然后剩下这 $n - r$ 个物体再考虑以下情况，
非空的放入 $1$ 个盒子， $2$ 个盒子， $⋯\cdots$ , $r$ 个盒子。
:::

2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

A100、H100、H20算力租赁怎么选？企业级GPU选型指南

2048 AI社区

基于 Node.js + 大模型的 AI 客服系统

本文介绍了如何为博客部署AI智能助手，解决内容查找难、互动少的痛点。该助手具备四项核心功能：智能对话、文章搜索推荐、FAQ自动匹配和多模型切换（支持文本/图像生成）。技术实现上采用Node.js+Express框架，通过直接解析Hexo源文件实现文章索引，使用JSON格式存储FAQ优先匹配常见问题以降低API成本。系统包含IP级限流保护，前端深度集成Hexo主题。部署方式支持pm2进程管理，平均响

2048 AI社区

用 AI 一句话查 A 股数据，免费替代 Tushare（附完整教程）

【摘要】半导体板块近期大涨40%，存储芯片或迎超级周期。本文介绍一种零代码金融数据分析方案，通过阿里云百炼MCP平台的financial-expert技能，用自然语言即可查询A股/基金/宏观数据。3分钟完成安装（Node.js+CLI工具+API配置），支持五大实战场景：1)半导体行业估值分析；2)基本面选股（如筛选连续3年净利润增长>30%个股）；3)基金经理筛选；4)宏观指标趋势研判；5