不同正整数之和
4 个不同的正整数之和为 1000，这四个数要么全为偶数，要么全为奇数，这样的四元数组（不考虑顺序）有多少个？ 分解两个类似问题不就行了吗：[*]4 个不同的正整数之和为 500，得到后各数*2；
[*]4 个不同的正整数之和为 502，得到后各数*2-1。
不就行了吗？ gxqcn 发表于 2014-1-9 17:28
分解两个类似问题不就行了吗：
[*]4 个不同的正整数之和为 500，得到后各数*2；
[*]4 个不同的正整数之和 ...
行，难点在于“4 个不同的正整数之和”而不是“4 个正整数之和” 500的表示成4个不同的正整数之和有 842263 种.
502的表示成4个不同的正整数之和有 852514 种.
所以1000表示成4个奇偶性质相同的不同正整数之和 有842263 + 852514 = 1694777 种 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$ $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 于 2014-4-7 18:29 编辑
由于是不考虑顺序的，所以属于整数拆分范畴的问题。
因为要求拆分量互不相同，且同奇偶，拆分数位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}`表示虚数单位）
当然也可以对母函数用泰勒展开求通项，结果是等价的:
SeriesCoefficient[
x/(1 - x) x^2/(1 - x^2) x^3/(1 - x^3) x^4/(1 - x^4), {x, 0,
n}] // FunctionExpand
将通项中代入n=502和n=500，分别得出852514和842263,因此最终结果是二者之和，1694777。
上面是解析的方法，得到了一般结果。如果只想得到数值结果，可以使用卷积求出母函数的系数，下面我用Matlab来检验上述结果的正确性：
% 4p+3q+2r+s=502
a=;
n=502;
r=1;
for k=1:length(a)
r=)];
end
nsol=r(end-n);
disp(['正整数解的个数为：' num2str(nsol)])
正整数解的个数为：852514
% 4p+3q+2r+s=500
n=500;
r=1;
for k=1:length(a)
r=)];
end
nsol=r(end-n);
disp(['正整数解的个数为：' num2str(nsol)])
正整数解的个数为：842263
852514+842263
ans =
1694777 本帖最后由 fungarwai 于 2014-4-7 13:11 编辑
在想这个问题时发现了一个公式，请各位帮忙求证
$|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}}|$
可能会用德·摩根定理 fungarwai 发表于 2014-4-7 13:09
在想这个问题时发现了一个公式，请各位帮忙求证
$|x_1 \ne x_2|=|U|-|x_1=x_2|$
有点像是容斥定理的变形 本帖最后由 kastin 于 2014-4-7 15:39 编辑
方法二，直接求解，一步到位：
问题转换为
求不定方程 `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
检验：
SeriesCoefficient[
x^16/(1 - x^2) /(1 - x^6) /(1 - x^4)^2, {x, 0, n}] // FunctionExpand
% /. n -> 1000