求不大于 10000 且各位数之和是 19 的正整数的个数

popo987654

想请教一下除枚举外有没有较便捷的解法？

luyuanhong

题  求不大于 10000 且各位数之和是 19 的正整数的个数。

解  容易看出，满足要求的正整数，最多是四位数，所以，它的各位数必定是由

0～9 中的 4 个数组成，这 4 个数的总和为 19 。

    下面分几种情况讨论：

（1）4 个数各不相同，可以是：

0+2+8+9，0+3+7+9，0+4+6+9，0+4+7+8，0+5+6+8，1+2+7+9，1+3+6+9，1+3+7+8，

1+4+5+9，1+4+6+8，1+5+6+7，2+3+5+9，2+3+6+8，2+4+5+8，2+4+6+7，3+4+5+7。

   共有 16 种组合，每种组合中的 4 个数的位置又可以有 4！= 24 种不同的排列，

所以这样的数共有 16 × 24 = 384 个。

（2）4 个数中有两个相同，另两个互不相同，可以是：

1+1+8+9，2+2+6+9，2+2+7+8，3+3+4+9，3+3+5+8，3+3+6+7，4+4+2+9，4+4+3+8，

4+4+5+6，5+5+0+9，5+5+1+8，5+5+2+7，5+5+3+6，6+6+0+7，6+6+2+5，6+6+3+4，

7+7+0+5，7+7+1+4，7+7+2+3，8+8+0+3，8+8+1+2，9+9+0+1。
   
    共有 22 种组合，在 4 个位置中找 2 个位置放两个相同的数，有 C(4,2) = 6

种放法，剩下两个数，还可互换位置，所以这样的数共有 22 × 6 × 2 = 264 个。

（3）4 个数中有三个相同，另一个不相同，可以是：

4+4+4+7，5+5+5+4，6+6+6+1。

   共有 3 种组合，在 4 个位置中找 3 个位置放三个相同的数，有 C(4,3) = 4

种放法，所以这样的数共有 3 × 4 = 12 个。

   综合以上分析，可知满足要求的正整数共有 384 + 264 + 12 = 660 个。

luyuanhong

题  求不大于 10000 且各位数之和是 19 的正整数的个数。

解  容易看出，满足要求的正整数，最多是四位数，所以，它的各位数必定是由

0～9 中的 4 个数组成，这 4 个数的总和为 19 。

    先不考虑数字不大于 9 的限制，只考虑总和为 19 的 4 个非负整数。

    设想将 19 个球排成一列，再插入 3 块隔板，将球分成 4 段（有些段中球数

可以是 0），这 4 段中的球数就是总和为 19 的 4 个非负整数。

    球与隔板共有 19 + 3 = 22 个物体，在 22 个物体中选 3 个物体作为隔板，有

C(22,3) = 1540 种不同的选法。也就是有 1540 种不同的情形。

    下面考虑扣除有数字大于 9 的情形。

    其中的数字如果大于 9 ，这数字只可能是 10,11,…,19 ，而且只可能有一个。

    设大于 9 的数字是 k ，这个数的位置有 4 种放法。剩下 3 个数之和是 19-k ，

设想将 19-k 个球排成一列，再插入 2 块隔板，将球分成 3 段，对应于这 3 个数。

球与隔板共有 19-k + 2 = 21-k 个物体，在其中选隔板，有 C(21-k,2) 种不同选法。

    所以，有数字大于 9 的不同的情形共有

4 × [C(11,2)+C(10,2)+C(9,2)+C(8,2)+C(7,2)+C(6,2)+C(5,2)+C(4,2)+C(3,2)+C(2,2)]

      = 4 × (55 + 45 + 36 + 28 + 21 + 15 + 10 + 6 + 1) = 4 × 220 = 880 种。

    综合以上分析可知，符合要求的正整数共有 1540 - 880 = 660 个。