一个数各个位上的数字相加等于6,问2位数有几个,3位数有几个,4位数有几个,第2013位数是多少
可以运用插板法,通过组合公式,C(a,b)= a!/b!/(a-b)! 进行计算。
对于 n 位正整数,各位数字之和等于 6,可以看作有 (6+n) 个小球分成 n 组。则:
在 (6+n) 小球的 (6+n-1) 个间隔中,插入 (n-1) 块隔板,即可将它们分隔成 n 组;每组抽走 1 个小球后,小球的总数即为 6。
运用组合公式计算方案数量,C(6+n-1,n-1);
其中,还需要减除首位为零的情况。这个减除项相当于 (n-1) 位,各位数字之和等于 6 的问题,计算方法相同。运用组合公式,C(6+n-2,n-2);
两项合并,计算公式为:S(n) = C(6+n-1,n-1) - C(6+n-2,n-2)
举例来说,对于10位数的情形:
S(10) = C(6+10-1,10-1) - C(6+10-2,10-2)
= C(15,9) - C(14,8)
= 15!/9!/(15-9)! - 14!/8!/(14-8)!
= 2002
对于问题中的2位数、3位数、4位数、2013位数,计算结果分别为:
S(2) = 6;
S(3) = 21;
S(4) = 56 ;
S(2013) = 276817455002088。
当然,对于位数不多的情形,枚举也是一个可行的方法。
但是,如果超过10位数,枚举效率非常低,甚至不可能完成。另外,对于2013位数,最高需要计算2018的阶乘,接近5800位大整数,需要编程来解决。或者通过分子分母约分来避免大整数计算。
此外,如果要计算 S(2) 到 S(2013) 的总和,并不需要循环累加。它相当于 S(2013) 的减除项换成 S(2) 的减除项。
SUM = C(2018,2012) - C(6,0)
= 2018!/2012!/6! - 6!/0!/6!
= 93102937365702263
即:各位数字之和等于 6 的 2位到2013位正整数,一共有 93102937365702263 个。
附:部分计算结果(限于篇幅,只能给出部分)和 fortran代码