不同正整数之和

fungarwai

4 个不同的正整数之和为 1000，这四个数要么全为偶数，要么全为奇数，这样的四元数组（不考虑顺序）有多少个？

gxqcn

分解两个类似问题不就行了吗：

• 4 个不同的正整数之和为 500，得到后各数*2；
• 4 个不同的正整数之和为 502，得到后各数*2-1。
  

不就行了吗？

fungarwai

gxqcn 发表于 2014-1-9 17:28
分解两个类似问题不就行了吗：

4 个不同的正整数之和为 500，得到后各数*2；

4 个不同的正整数之和 ...

行，难点在于“4 个不同的正整数之和”而不是“4 个正整数之和”

wayne

500的表示成4个不同的正整数之和有 842263 种.
502的表示成4个不同的正整数之和有 852514 种.
所以1000表示成4个奇偶性质相同的不同正整数之和 有  842263 + 852514 = 1694777 种

fungarwai

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$

fungarwai

$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$

kastin

由于是不考虑顺序的，所以属于整数拆分范畴的问题。
因为要求拆分量互不相同，且同奇偶，拆分数位4，这是个带有约束条件的整数拆分问题。解答方法有不少。

一般来说，整数拆分问题使用的是母函数（生成函数）方法，或者递推法。递推法的适用性更加广泛，特别是对于n较大的情况。这里由于拆分数为4，n=1000不是很大，所以可以使用母函数方法来解决。

问题可以记为
求不定方程`X_1+X_2+X_3+X_4=1000\enspace(X_1 \lt X_2 \lt X_3 \lt X_4)`的奇数解的个数和偶数解的个数之和。（注：要求是4个不同数之和，因此偶数不考虑0的情况。）

当`X_i`为奇数时，可设`X_i=2k_i-1`，那么上述不定方程变为`k_1+k_2+k_3+k_4=502\enspace(1\leqslant k_1 \lt k_2 \lt k_3 \lt k_4)`的正整数解的个数。
当`X_i`为偶数时，可设`X_i=2k_i`，那么上述不定方程变为`k_1+k_2+k_3+k_4=500\enspace(1 \leqslant k_1 \lt k_2 \lt k_3 \lt k_4)`的正整数解的个数。

根据Ferrers图的性质可知，n的k拆分数等于把n拆分成最大分量为k的所有拆分数，因此可进一步等价为`4y_1+3y_2+2y_3+y_4=502\enspace与\enspace4y_1+3y_2+2y_3+y_4=500\enspace的正整数解个数之和。`(特别注意，这里并未要求`y_1 \lt y_2 \lt y_3 \lt y_4`)。
如果对整数拆分知识不太了解的话，因为有等价关系`1 \leqslant k_1 \lt k_2 \lt k_3 \lt k_4 \Longleftrightarrow y_j为正整数，且k_0=0, k_{j+1}=k_j+y_{j+1}`，只需对k的不定方程作后面的代换即那么同样可以通过代换来得到上面关于y的不定方程。

不定方程`4y_1+3y_2+2y_3+y_4=n`的正整数解的个数所对应的母函数为$$(x+x^2+x^3+x^4+\cdots)(x^2+x^4+x^6\cdots)(x^3+x^6+x^9+x^{12}+\cdots)(x^4+x^8+x^{12}+\cdots)=\frac{x^{10}}{(1-x)(1-x^2)(1-x^3)(1-x^4)}$$
化为部分分式和，即可得到通解。
$-1/(8 (x^2 + 1)) - 1/(9 (x^2 + x + 1)) - 3/(16 (x + 1)) + 1/(
32 (x + 1)^2) + 19/(16 (x - 1)) + 239/(288 (x - 1)^2) + 7/(
24 (x - 1)^3) + 1/(24 (x - 1)^4) + 1$
通解为
`\frac{ 2 n^3 - 30 n^2 -  \frac{64}{\sqrt{3}}\sin \frac{2\pi (n + 1)}{3}+
   9 ((-1)^n + 15) n - 45 (-1)^n - 18 (-\text{i})^n - 18 \text{i}^n - 175}{288}`（正体的`\text{i}`表示虚数单位）
当然也可以对母函数用泰勒展开求通项，结果是等价的:

1. SeriesCoefficient[
   
2.   x/(1 - x) x^2/(1 - x^2) x^3/(1 - x^3) x^4/(1 - x^4), {x, 0,
   
3.    n}] // FunctionExpand

复制代码

将通项中代入n=502和n=500，分别得出852514和842263,因此最终结果是二者之和，1694777。

上面是解析的方法，得到了一般结果。如果只想得到数值结果，可以使用卷积求出母函数的系数，下面我用Matlab来检验上述结果的正确性：

1. % 4p+3q+2r+s=502
   
2. a=[4 3 2 1];
   
3. n=502;
   
4. r=1;
   
5. for k=1:length(a)
   
6. r=[r conv(r,[(1-(-1).^(rem(n:-1:1,a(k))==0))/2 0])];
   
7. end
   
8. nsol=r(end-n);
   
9. disp(['正整数解的个数为：' num2str(nsol)])
   
10. 正整数解的个数为：852514
    
11. % 4p+3q+2r+s=500
    
12. n=500;
    
13. r=1;
    
14. for k=1:length(a)
    
15. r=[r conv(r,[(1-(-1).^(rem(n:-1:1,a(k))==0))/2 0])];
    
16. end
    
17. nsol=r(end-n);
    
18. disp(['正整数解的个数为：' num2str(nsol)])
    
19. 正整数解的个数为：842263
    
20. 852514+842263
    
21. 
    
22. ans =
    
23. 
    
24.      1694777

复制代码

fungarwai

在想这个问题时发现了一个公式，请各位帮忙求证

$|x_1 \ne x_2|=|U|-|x_1=x_2|$

$|x_1 \ne x_2 \ne x_3|=|U|-\sum|x_1=x_2|+2|x_1=x_2=x_3|$

$|x_1 \ne x_2 \ne x_3 \ne x_4|=|U|-\sum|x_1=x_2|+2\sum|x_1=x_2=x_3|+\sum|x_1=x_2 \cap x_3=x_4|-6|x_1=x_2=x_3=x_4|$

证明：

$|x_1 \ne x_2 \ne ... \ne x_n|=\sum (-1)^{r_1+r_2+...+r_m} r_1!r_2!...r_m!\sum_{i_1\ne i_2 \ne ... \ne i_{r_t}}|\bigcap_{t=1}^m x_{i_1}=x_{i_2}=...=x_{i_{r_t+1}}|$

可能会用德·摩根定理

kastin

fungarwai 发表于 2014-4-7 13:09
在想这个问题时发现了一个公式，请各位帮忙求证

$|x_1 \ne x_2|=|U|-|x_1=x_2|$

有点像是容斥定理的变形

kastin

方法二，直接求解，一步到位：
问题转换为
求不定方程 `X_1+X_2+X_3+X_4=1000` 的奇数解的个数和偶数解的个数之和，由于是4个不同的数，且不考虑顺序，故需要加入条件 `0\lt X_1\lt X_2\lt X_3\lt X_4`。

直接作代换`X_1=y_1, X_2=X_1+y_2，X_3=X_2+y_3，X_4=X_3+y_4\enspace (y_i\geqslant 1)`就能满足上述条件，此时方程化为`4y_1+3y_2+2y_3+y_4=1000`。
由于要求`X_i`同奇偶，所以只要满足`y_2，y_3，y_4`为偶数即可（当`y_1`为奇数，那么`X_i`均为奇数；当`y_1`为偶数，那么`X_i`均为偶数）
因此母函数可以直接写出来$$(x^{4\cdot1}+x^{4\cdot2}+x^{4\cdot3}+x^{4\cdot4}+\cdots)(x^{3\cdot2}+x^{3\cdot4}+x^{3\cdot6}+\cdots)(x^{2\cdot2}+x^{2\cdot4}+x^{2\cdot6}+\cdots)(x^2+x^4+x^6+\cdots)=\frac{x^{16}}{(1-x^2)(1-x^4)^2(1-x^6)}$$
因此直接可以得出
4 个不同的正整数之和为 n，这四个数要么全为偶数，要么全为奇数，这样的四元数组（不考虑顺序）有
`\frac{(n - 8) ((n^2-16n) (1 + (-1)^n)  +
    2 (23 (-1)^n + 9 \text{i}^n + 9 \text{(-i)}^n+
       23)) - \frac{128 \sin\frac{(n + 1)\pi}{3}}{\sqrt{3}} - \frac{128 \sin\frac{2(n + 1)\pi}{3}}{\sqrt{3}}}{1152}`
代入n=1000即得结果为1694777
检验：

1. SeriesCoefficient[
   
2.   x^16/(1 - x^2) /(1 - x^6) /(1 - x^4)^2, {x, 0, n}] // FunctionExpand
   
3. % /. n -> 1000

复制代码