数学研发网设为首页收藏本站

数学研发论坛

 找回密码
 欢迎注册
查看: 2143|回复: 24

[提问] 不同正整数之和

[复制链接]
发表于 2014-1-9 16:12:41 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
4 个不同的正整数之和为 1000,这四个数要么全为偶数,要么全为奇数,这样的四元数组(不考虑顺序)有多少个?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-1-9 17:28:36 | 显示全部楼层
分解两个类似问题不就行了吗:
  • 4 个不同的正整数之和为 500,得到后各数*2;
  • 4 个不同的正整数之和为 502,得到后各数*2-1。
不就行了吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2014-1-9 17:42:30 | 显示全部楼层
gxqcn 发表于 2014-1-9 17:28
分解两个类似问题不就行了吗:
  • 4 个不同的正整数之和为 500,得到后各数*2;
  • 4 个不同的正整数之和 ...

  • 行,难点在于“4 个不同的正整数之和”而不是“4 个正整数之和”
    毋因群疑而阻独见  毋任己意而废人言
    毋私小惠而伤大体  毋借公论以快私情
    发表于 2014-1-9 18:11:58 | 显示全部楼层
    500的表示成4个不同的正整数之和有 842263 种.
    502的表示成4个不同的正整数之和有 852514 种.
    所以1000表示成4个奇偶性质相同的不同正整数之和 有  842263 + 852514 = 1694777 种
    毋因群疑而阻独见  毋任己意而废人言
    毋私小惠而伤大体  毋借公论以快私情
     楼主| 发表于 2014-1-28 18:03:57 | 显示全部楼层
    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$
    毋因群疑而阻独见  毋任己意而废人言
    毋私小惠而伤大体  毋借公论以快私情
     楼主| 发表于 2014-3-31 20:48:48 | 显示全部楼层
    $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$
    毋因群疑而阻独见  毋任己意而废人言
    毋私小惠而伤大体  毋借公论以快私情
    发表于 2014-4-7 12:14:17 | 显示全部楼层
    本帖最后由 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}`表示虚数单位)
    当然也可以对母函数用泰勒展开求通项,结果是等价的:
    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. ans =

    22.      1694777
    复制代码

    点评

    To suwukong:是的,打掉了一项,我修改一下:)  发表于 2014-4-7 18:28
    母函数式子中(x^3+x^6+x^{12}+\cdots)应该是(x^3+x^6+x^9+\cdots)  发表于 2014-4-7 17:43
    我这是为了不失一般性。假如n=100000000,或者是100个不同的数之和呢?你要隔板多少次?头得弄晕了。  发表于 2014-4-7 13:53
    To fungarwai: 对于kastin提出新的求解方案,请不要有排斥心里,更不能有不恰当的言论!  发表于 2014-4-7 13:51
    我都把问题推到隔板法了,你还搞这货......  发表于 2014-4-7 13:02
    毋因群疑而阻独见  毋任己意而废人言
    毋私小惠而伤大体  毋借公论以快私情
     楼主| 发表于 2014-4-7 13:09:06 | 显示全部楼层
    本帖最后由 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}}|$

    可能会用德·摩根定理
    毋因群疑而阻独见  毋任己意而废人言
    毋私小惠而伤大体  毋借公论以快私情
    发表于 2014-4-7 13:51:39 | 显示全部楼层
    fungarwai 发表于 2014-4-7 13:09
    在想这个问题时发现了一个公式,请各位帮忙求证

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

    有点像是容斥定理的变形
    毋因群疑而阻独见  毋任己意而废人言
    毋私小惠而伤大体  毋借公论以快私情
    发表于 2014-4-7 15:37:07 | 显示全部楼层
    本帖最后由 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
    检验:
    1. SeriesCoefficient[
    2.   x^16/(1 - x^2) /(1 - x^6) /(1 - x^4)^2, {x, 0, n}] // FunctionExpand
    3. % /. n -> 1000
    复制代码
    毋因群疑而阻独见  毋任己意而废人言
    毋私小惠而伤大体  毋借公论以快私情
    您需要登录后才可以回帖 登录 | 欢迎注册

    本版积分规则

    小黑屋|手机版|Archiver|数学研发网 ( 苏ICP备07505100号  

    GMT+8, 2017-11-24 08:02 , Processed in 0.216785 second(s), 25 queries .

    Powered by Discuz! X3.2

    © 2001-2013 Comsenz Inc.

    快速回复 返回顶部 返回列表