带容量限制的相同球分入不同盒子的计数问题

嘿，你的初始思路完全没问题！可重复组合的公式确实是这类“相同物品放入不同容器”问题的核心，但因为每个盒子有最大容量限制，我们需要用容斥原理来剔除那些不符合要求的分配方式，最终得到正确结果。下面一步步拆解：

步骤1：计算无限制的总分配数 #

根据你提到的可重复r-组合公式，把13个相同的球放入3个不同盒子，无任何限制时的方式数为：
$$
\binom{n + r - 1}{r}
$$
这里n=3（盒子数），r=13（球数），代入得：
$$
\binom{13 + 3 - 1}{13} = \binom{15}{13} = \binom{15}{2} = 105
$$

步骤2：定义并计算不符合限制的情况 #

我们需要排除那些某盒子超过最大容量的分配：

• 设集合A：$k_1$装≥6个球（超过最多5个的限制）。先给$k_1$放6个球，剩下13-6=7个球无限制分配，方式数为：
  $$
  \binom{7 + 3 - 1}{7} = \binom{9}{7} = \binom{9}{2} = 36
  $$
• 设集合B：$k_2$装≥7个球（超过最多6个的限制）。先给$k_2$放7个球，剩下13-7=6个球无限制分配，方式数为：
  $$
  \binom{6 + 3 - 1}{6} = \binom{8}{6} = \binom{8}{2} = 28
  $$
• 设集合C：$k_3$装≥5个球（超过最多4个的限制）。先给$k_3$放5个球，剩下13-5=8个球无限制分配，方式数为：
  $$
  \binom{8 + 3 - 1}{8} = \binom{10}{8} = \binom{10}{2} = 45
  $$

步骤3：计算不符合情况的交集（避免重复剔除） #

容斥原理要求我们把重复减去的部分加回来：

• $A∩B$：$k_1≥6$且$k_2≥7$，总共需要6+7=13个球，剩下0个球，方式数为：
  $$
  \binom{0 + 3 - 1}{0} = \binom{2}{0} = 1
  $$
• $A∩C$：$k_1≥6$且$k_3≥5$，总共需要6+5=11个球，剩下13-11=2个球，方式数为：
  $$
  \binom{2 + 3 - 1}{2} = \binom{4}{2} = 6
  $$
• $B∩C$：$k_2≥7$且$k_3≥5$，总共需要7+5=12个球，剩下13-12=1个球，方式数为：
  $$
  \binom{1 + 3 - 1}{1} = \binom{3}{1} = 3
  $$
• $A∩B∩C$：$k_1≥6$、$k_2≥7$、$k_3≥5$，总共需要6+7+5=18个球，但我们只有13个球，这种情况不存在，方式数为0。

步骤4：应用容斥原理计算最终结果 #

符合条件的方式数 = 总方式数 - 单个不符合的方式数之和 + 两两交集的方式数之和 - 三个交集的方式数
代入数值：
$$
105 - (36 + 28 + 45) + (1 + 6 + 3) - 0 = 105 - 109 + 10 = 6
$$

简单来说，你的初始公式是基础，容斥原理帮我们处理了“不能超过容量”的限制条件，这样就完美解决问题啦！

内容的提问来源于stack exchange，提问作者user530832