组合问题

tommywong

1,1,2,3,3,4,5,5,5,6,5,5,5,4,3,3,2,1,1
a(492)=b(123)+3b(122)+5b(121)+5b(120)+2b(119)=852514
a(490)=2b(122)+5b(121)+5b(120)+3b(119)+b(118)=842263

1,2,4,4,5,4,4,2,1
b(123)=c(41)+4c(40)+4c(39)=56217
b(122)=4c(40)+4c(39)+c(38)=54894
b(121)=2c(40)+5c(39)+2c(38)=53592
b(120)=c(40)+4c(39)+4c(38)=52311
b(119)=4c(39)+4c(38)+c(37)=51050
b(118)=2c(39)+5c(38)+2c(37)=49810

1,3,3,1
c(41)=3d(20)+d(19)=6853
c(40)=d(20)+3d(19)=6391
c(39)=3d(19)+d(18)=5950
c(38)=d(19)+3d(18)=5530
c(37)=3d(18)+d(17)=5130

$d(x)=C_{x+3}^3$

tommywong

我讲解一下怎么得到这个结果。

这个结果主要用了三种技巧，第一个是组合数脱离无限求和的公式：

$\displaystyle \sum_{j=0}^{\infty} C_{n-j}^m=C_{n+1}^{m+1}$

例如$\displaystyle \sum_{j_i=0}^{\infty} C_{10-j_1-j_2}^0=C_{12}^2$，这也是$x+y+z=10$的分布，先不要管为什么是这个和式，看看其他两个技巧。

$\displaystyle \sum_{a_i=0}^{\infty} C_{\frac{X-k_2a_2-k_3a_3-...-k_ma_m}{k_1}}^0=\sum_{a_i=0}^{\infty} C_{\frac{X-k_1a_1-k_3a_3-...-k_ma_m}{k_2}}^0=...=\sum_{a_i=0}^{\infty} C_{\frac{X-k_1a_1-k_2a_2-...-k_{m-1}a_{m-1}}{k_m}}^0$

$\displaystyle \sum_{a_i=0}^{\infty} C_{\frac{X-k_2a_2-k_3a_3-...-k_ma_m}{k_1}}^0=\sum_{b_i=0}^{k_1-1} \sum_{a_i=0}^{\infty} C_{\frac{X-k_2b_2-k_3b_3-...-k_mb_m}{k_1}-k_2a_2-k_3a_3-...-k_ma_m}^0$

现在$\displaystyle \sum_{j_i=0}^{\infty} C_{\frac{X-j_1-2j_2-3j_3}{4}}^0$要脱离无限求和的话，可以这样做：

$\displaystyle \sum_{j_i=0}^{\infty} C_{\frac{X-j_1-2j_2-3j_3}{4}}^0=\sum_{a_i=0}^3 \sum_{j_i=0}^{\infty} C_{\frac{X-a_1-2a_2-3a_3}{4}-j_1-2j_2-3j_3}^0$

$\displaystyle =\sum_{a_i=0}^3 \sum_{j_i=0}^{\infty} C_{\frac{\frac{X-a_1-2a_2-3a_3}{4}-j_1-2j_2-j_3}{3}}^0=\sum_{a_i=0}^3 \sum_{b_i=0}^2 \sum_{j_i=0}^{\infty} C_{\frac{\frac{X-a_1-2a_2-3a_3}{4}-b_1-2b_2-b_3}{3}-j_1-2j_2-j_3}^0$

$\displaystyle =\sum_{a_i=0}^3 \sum_{b_i=0}^2 \sum_{c_i=0}^1 \sum_{j_i=0}^{\infty} C_{\frac{\frac{\frac{X-a_1-2a_2-3a_3}{4}-b_1-2b_2-b_3}{3}-c_1-c_2-c_3}{2}-j_1-j_2-j_3}^0=\sum_{a_i=0}^3 \sum_{b_i=0}^2 \sum_{c_i=0}^1 \sum_{j_i=0}^{\infty} C_{3+\frac{\frac{\frac{X-a_1-2a_2-3a_3}{4}-b_1-2b_2-b_3}{3}-c_1-c_2-c_3}{2}}^3$

21#那些其实就是$\displaystyle \sum_{a_i=0}^3 \sum_{b_i=0}^2 \sum_{c_i=0}^1 \sum_{j_i=0}^{\infty} C_{3+\frac{\frac{\frac{X-a_1-2a_2-3a_3}{4}-b_1-2b_2-b_3}{3}-c_1-c_2-c_3}{2}}^3$

可以说明整数分布$X=k_1a_1+k_2a_2+...+k_ma_m$都能表达成$\displaystyle \sum_{a_i=0}^{\infty} C_{\frac{X-k_2a_2-k_3a_3-...-k_ma_m}{k_1}}^0$，而其他函数例如平方和$X=a_1^2+a_2^2$其实都能表达成和式，但我还没有技巧可以算出这种和式。

tommywong

$X=a_1+2a_2+3a_3+4a_4$

$j_1=1,2,...,12$,$j_2=1,2,...,6$,$j_3=1,2,3,4$,$j_4=1,2,3$

$X+48=12(a_{1j_1}+a_{2j_2}+a_{3j_3}+a_{4j_4})+j_1+2j_2+3j_3+4j_4$

展开$(x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^{10}+x^{11}+x^{12})(x^2+x^4+x^6+x^8+x^{10}+x^{12})(x^3+x^6+x^9+x^{12})(x^4+x^8+x^{12})$得到$j_1+2j_2+3j_3+4j_4$的分布

$X=502,C_{44}^3+30C_{43}^3+39C_{42}^3+2C_{41}^3=852514$

$X=500,23C_{43}^3+44C_{42}^3+5C_{41}^3=842263$