《计算机程序设计艺术·卷4A:组合算法(一)》的习题 7.2.1.7-15:


首先,我们复习一下组合,见《计算机程序设计艺术·卷1:基本算法(第3版)》的 1.2.6 节:


接下来,是允许重复的组合,见习题 1.2.6-60 及答案:


习题 7.2.1.7-15 的答案如下:

这个答案有一处错误,因为 56 + 35 + 20 + 10 + 4 + 1 = 126 ≠ 252

实际上,投掷 n 颗骰子,相当于从 m = 6 个对象中一次取出 n 个的允许重复的组合,所得结果共有 种。如果把它们分解为以数 j (1 ≤ j ≤ 6) 开头的话,分别有 种。当 1 ≤ n ≤ 7 时的情况如下所示:

所以,正确的表达式应该是: 126 + 70 + 35 + 15 + 5 + 1 = 252

顺便还得到一个恒等式: