[组合] 问一道组合题目

longzaifei

2007年是一个特殊的年份, 它的各位数字之和 2+0+0+7=9 是一个完全平方数, 我们暂且将其称作 "平方年". 那么从公元元年开始, 历史上经历了多少个 "平方年"?

abababa

各位数之和最小是1，最大不超过$2999$的各位之和，也就是$29$，之间的平方数只有$1,4,9,16,25$
然后就是有序分折吧，最少是1分折，最多是4分折，公式是$C_{k-1}^{n-1}$
$C_{1-1}^{1-1}$
$C_{1-1}^{4-1}+C_{2-1}^{4-1}+C_{3-1}^{4-1}+C_{4-1}^{4-1}$
$C_{1-1}^{9-1}+C_{2-1}^{9-1}+C_{3-1}^{9-1}+C_{4-1}^{9-1}$
$C_{1-1}^{16-1}+C_{2-1}^{16-1}+C_{3-1}^{16-1}+C_{4-1}^{16-1}$
$C_{1-1}^{25-1}+C_{2-1}^{25-1}+C_{3-1}^{25-1}+C_{4-1}^{25-1}$

abababa

回复 2# abababa

哦，这个错了，分拆的时候必须是每位都不大于9，对1，4，9来说都可以，16和25就不行了，不能1分拆，25也不能2分拆
那$16=9+7=8+8=7+9$，就只有这三种情况了

abababa

回复 3# abababa

这样也还有0没有考虑进去，看来不能这样算了。刚才一位网友算的是有290个，不过他是用程序算的

tommywong

$x_1\in[0,1],x_2,x_3,x_4\in[0,9]$
$x_1+x_2+x_3+x_4=k$
$\displaystyle \frac{(1-x^2)(1-x^{10})^3}{(1-x)^4}
=(1+x)(1-x^{10})^3\sum_{n=0}^{\infty} C_{n+2}^2 x^n$
$\displaystyle =(1+x-3x^{10}-3x^{11}+3x^{20}+3x^{21}-x^{30}-x^{31})\sum_{n=0}^{\infty} C_{n+2}^2 x^n$
$k=1,C_3^2+C_2^2=4$
$k=4,C_6^2+C_5^2=25$
$k=9,C_{11}^2+C_{10}^2=100$
$k=16,C_{18}^2+C_{17}^2-3C_8^2-3C_7^2=142$
$k=25,C_{27}^2+C_{26}^2-3C_{17}^2-3C_{16}^2+3C_7^2+3C_6^2=16$
$4+25+100+142+16=287$

$x_1=2,x_2=0,x_3+x_4=k-2$
$k-2=2,(x_3,x_4)=(0,2),(1,1)$
$k-2=7,(x_3,x_4)=(0,7)$
$287+3=290$