NOIP 普及组初赛 · NOIP 2014 普及组初赛试题 第 21 题

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

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

别被'球和袋子'绕晕，核心是'把8拆成最多5个数'。拿到这种题，先想：是不是整数划分？划分的份数能不能超过5？能不能有0？把这三个关过了，剩下的就是老老实实枚举，按从大到小列，保证不重不漏，数个数就行。

最容易栽跟头的地方有三处。第一，把'袋子'当成'盒子'，忘了题目强调'同样的袋子'，于是去用隔板法去算，结果把顺序也算进去了，像(5,1,1)和(1,5,1)被当成两种，这就多算了一大截。第二，枚举时没控制好份数上限，把拆成6份、7份甚至8份全算进去，比如(1,1,1,1,1,1,1,1)这种，题目只允许最多5个袋子，多出来的那些全要砍掉。第三，枚举时容易漏掉一些中间项，比如4+3+1这种，或者重复写，比如把4+2+2和4+2+1+1搞混，导致最后数出来的总数对不上。记住，这是组合里的整数划分，不是排列组合里的隔板法，顺序不重要，份数有上限，0可以出现但实际就是少用几个袋子。

考点与概念：整数划分（带份数上限）

这题考的是整数划分，但有个关键限制：拆成的份数不能超过5。命题人喜欢在这种'球和袋子都相同'的表述里挖坑，其实就是想让你别用隔板法，别去管顺序，只关心每份是多少。概念上，就是把一个整数拆成若干个正整数之和，顺序无关，份数有限制。

命题视角：为什么考这个？

NOIP普及组里，这类题通常出现在'组合计数'板块。命题人设计M=7,N=3时K=8，就是让你先熟悉'把7拆成最多3份'的枚举套路，然后换到M=8,N=5，难度稍增，但思路不变。他们爱在'同样的袋子'上做文章，诱导学生去用隔板法，结果把(5,1,1)和(1,5,1)当成不同，或者把拆成6份的也算进去，这些都是典型的陷阱。