Question

【题目】有10粒糖，每天至少吃一粒，吃完为止。共有多少种不同的吃法？

Answer 1

【答案】512

【解析】初看本题似乎觉得很好入手，比如可以按天数进行分类枚举：

1天吃完的有1种方法，这天吃10块；2天吃完的有9种方法，10=1+9=2+8=……=9+1；

当枚举到3天吃完的时，情况就有点错综复杂了，叫人无所适从……所以我们必须换一种角度来思考．

不妨从具体的例子入手来分析，比如这10块糖分4天吃完：

第1天吃2块；第2天吃3块；第3天吃1块；第4天吃4块．

我们可以将10个“○”代表10粒糖，把10个“○”排成一排，“○”之间共有9个空位，若相邻两块糖是分在两天吃的，就在其间画一条竖线(如下图)．

○○|○○○|○|○○○○

比如上图就表示“第1天吃2块；第2天吃3块；第3天吃1块；第4天吃4块．”

这样一来，每一种吃糖的方法就对应着一种“在9个空位中插入若干个‘|’的方法”，要求有多少个不同的吃法，就是要求在这9个空位中插入若干个“|”的方法数。

由于每个空位都有画‘|’与“不画‘|’两种可能：

根据乘法原理，在这9个空位中画若干个“|”的方法数有：，这也就说明吃完10颗糖共有512种不同的吃法。