NOIP 普及 2014 第一轮 第 21 题：8 个相同球放入 5 个相同袋子的方案数

题目

把 $M$ 个同样的球放到 $N$ 个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的放置方法？(用 $K$ 表示)。

例如，$M=7,N=3$ 时，$K=8$；在这里认为 $(5,1,1)$ 和 $(1,5,1)$ 是同一种放置方法。 问：$M=8,N=5$ 时，$K=$

答案

18

题解

考点定位

本题考「球盒问题（相同的球放进相同的盒子）」,对应大纲 2.1.5 组合计数（难度【5】）。

解题过程

相同的球 + 相同的盒子 = 整数 n 拆成 ≤N 个部分的方案数 K。题面给出递推：

$$K(M,N)=K(M,N-1)+K(M-N,N)$$

（N 个空袋至少一个：K(M,N−1)；每袋至少一球：各拿走一球即 K(M−N,N)。）按原卷给定的递推表逐格填充得答案。

答案：18。

易错提醒

① 三种球盒模型的公式各不相同：球同盒同 = 整数拆分；球同盒异 = 隔板法 C(M+N−1,N−1)；球异盒异 = N^M；② 边界：K(0,N)=1、K(M,0)=0（M>0）。