免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 组合问题

4 个不同的正整数之和为 1000,这四个数要么全为偶数,要么全为奇数,这样的四元数组(不考虑顺序)有多少个?
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

分奇偶讨论一下就行了,全为偶数时设 $a=2x$ 等,等价于 4 个正整数之和为 $500$,用隔板法得 $C_{499}^3$;全为奇数时设 $a=2x-1$ 等,等价于 4 个正整数之和为 $502$,用隔板法得 $C_{501}^3$。结果就是 $C_{499}^3+C_{501}^3$。

TOP

错了,没注意到不同的整数,再想想

TOP

唔,“不同”二字让这题的水很深呐,题目哪来的啊?

TOP

回复 4# kuing


    你好2货kuing   from nexus 5

TOP

回复  kuing

你好2货kuing   from nexus 5
Tesla35 发表于 2014-1-4 23:08

你好2货555  from 555

TOP

本帖最后由 乌贼 于 2014-1-5 00:32 编辑

$(4,8,16,972),(6,10,12,972)$算不算两组

TOP

回复 7# 乌贼

当然算了。

TOP

回复 6# kuing


    擦论坛不太好用

TOP

从$1000=2\times 500=1+2+3+4+\cdots+31+4$中任取$3$个,余下之和为第四个数,$C_{31}^3=4495$

TOP

从$1000=2\times 500=1+2+3+4+\cdots+31+4$中任取$3$个,余下之和为第四个数,$C_{31}^3=4495$ ...
乌贼 发表于 2014-1-5 02:25

不对吧……

TOP

可以这样转化一下问题
(A≠B≠C≠D)=U-(A=B)-(A=C)-(A=D)-(B=C)-(B=D)-(C=D)+2(A=B=C)+2(A=B=D)+2(A=C=D)+2(B=C=D)-3(A=B=C=D)
由对称性得
(A≠B≠C≠D)=U-6(A=B)+8(A=B=C)-3(A=B=C=D)

TOP

回复 11# kuing
是不对,漏多了

TOP

回复 12# tommywong
看不懂

TOP

回复 14# 乌贼

大概是容斥原理
不过仍然不太好算
用母函数神马的计算量也不少

TOP

本帖最后由 乌贼 于 2014-1-5 17:58 编辑

还不如用排除法,先考虑$1$配$2,3,4,\cdots$的情况,依次$2$配,$3$配,$4$配,$5$配……
这题对我来说太难了,先想想由$3$个不同偶数组成的,其和为$100$的数组有多少。

TOP

大概是这样
$X=502,C_{501}^3-6(251)(250)+8(167)-3(0)$
$X=500,C_{499}^3-6(250)(249)+8(166)-3(1)$

TOP

写一下母函数的方法。

设这四个不同正整数为 $a$, $b$, $c$, $d$,由对称性不妨设 $1\leqslant a<b<c<d$。

(1)若这四个数全为偶数,可设 $a=2(1+x)$, $b=2(2+x+y)$, $c=2(3+x+y+z)$, $d=2(4+x+y+z+w)$,其中 $x$, $y$, $z$, $w\in\mbb N$,则
\[a+b+c+d=1000 \iff 4x+3y+2z+w=490,\]
即此类四元数组的个数为方程 $4x+3y+2z+w=490$ 的非负整数解的组数,即
\[(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)(1+x^3+x^6+\cdots)(1+x^4+x^8+\cdots)\]
的展开式的 $x^{490}$ 项的系数,亦即
\[\frac1{(1-x)(1-x^2)(1-x^3)(1-x^4)}\]
的展开式的 $x^{490}$ 项的系数;

(2)若这四个数全为奇数,可设 $a=2(1+x)-1$, $b=2(2+x+y)-1$, $c=2(3+x+y+z)-1$, $d=2(4+x+y+z+w)-1$,其中 $x$, $y$, $z$, $w\in\mbb N$,则
\[a+b+c+d=1000 \iff 4x+3y+2z+w=492,\]
即此类四元数组的个数为方程 $4x+3y+2z+w=492$ 的非负整数解的组数,类似于(1)那样,即为
\[\frac1{(1-x)(1-x^2)(1-x^3)(1-x^4)}\]
展开式的 $x^{492}$ 项的系数。

综合(1)(2),可知题目所求的数目,即两类四元数组的个数之和,乃是
\begin{align*}
f(x)&=\frac{x^2}{(1-x)(1-x^2)(1-x^3)(1-x^4)}+\frac1{(1-x)(1-x^2)(1-x^3)(1-x^4)}\\
&=\frac1{(1-x)^4(1+x)^2(1+x+x^2)}
\end{align*}
的展开式的 $x^{492}$ 项的系数。

设 $f(x)$ 展开成部分分式为
\[f(x)=\frac A{(1-x)^4}+\frac B{(1-x)^3}+\frac C{(1-x)^2}+\frac D{1-x}
+\frac E{(1+x)^2}+\frac F{1+x}+\frac G{1-\omega x}+\frac H{1-\omega^2x},\]
其中 $\omega=\cos120\du+\sin120\du\cdot i$。可以计算出
\[A=\frac{1}{12},B=\frac{1}{6},C=\frac{29}{144},D=\frac{3}{16}, E=\frac{1}{16},F=\frac{3}{16},G=\frac{3+\sqrt3i}{54},H=\frac{3-\sqrt3i}{54}.\](不知有没有什么简单的算法?上面这步我用软件求的)

我们将各项分别展开再求和,为此先搞一个展开公式,设 $g(x)=(1-kx)^\alpha$,易得其 $n$ 阶导数为
\[g^{(n)}(x)=(-k)^n\alpha(\alpha-1)\cdots(\alpha-n+1)(1-kx)^{\alpha-n},\]
于是 $g(x)$ 在 $x=0$ 处的展开式为
\[g(x)=1+(-k)\alpha x+\frac{(-k)^2\alpha(\alpha-1)}{2!}x^2+\cdots+ \frac{(-k)^p\alpha(\alpha-1)\cdots(\alpha-p+1)}{p!}x^p+\cdots,\]
特别地,当 $\alpha =-m-1$, $m\in\mbb N$ 时,就得到展开公式
\begin{align*}
\frac1{(1-kx)^{m+1}}&=1+k(m+1)x+\frac{k^2(m+1)(m+2)}{2!}x^2+\cdots+ \frac{k^p(m+1)(m+2)\cdots(m+p)}{p!}x^p+\cdots\\
&=1+\binom{m+1}1kx+\binom{m+2}2k^2x^2+\cdots+\binom{m+p}pk^px^p+\cdots\\
&=\sum_{p=0}^\infty\binom{m+p}mk^px^p,
\end{align*}
于是
\begin{align*}
f(x)=\sum_{p=0}^\infty\left( A\binom{3+p}3+B\binom{2+p}2+C(1+p)+D +E(1+p)(-1)^p+F(-1)^p+G\omega^p+H\omega^{2p}\right)x^p,
\end{align*}
令 $p=492$ 即得 $f(x)$ 展开式的 $x^{492}$ 项的系数为
\[A\binom{495}3+B\binom{494}2+493C+D +493E+F+G+H,\]
代入前面计算出的系数值即得结果为 $1694777$。
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

回复 18# kuing
膜拜!

TOP

本帖最后由 tommywong 于 2014-1-25 08:17 编辑

修正:(A≠B≠C≠D)=U-(A=B)-(A=C)-(A=D)-(B=C)-(B=D)-(C=D)+2(A=B=C)+2(A=B=D)+2(A=C=D)+2(B=C=D)-6(A=B=C=D)+(A=D)∩(B=C)+(A=C)∩(B=D)+(A=B)∩(C=D)
由对称性得(A≠B≠C≠D)=U-6(A=B)+8(A=B=C)-6(A=B=C=D)+3(A=B)∩(C=D)

$U=C_{X-1}^3$

$X=2x,(A=B)∩(C=D)=C_{x-1}^1=x-1$

$X=4x,(A=B=C=D)=C_{x-1}^0=1$

$E(X=\sum_{i=1}^m [1,n]_1+k[1,n]_1)=\sum_{i=1}^{[\frac{X-m}{k}]} C_{m-1+(X-m)remk+k(i-1)}^{m-1}$

$X=2x,(A=B)=\sum_{i=1}^{x-1} C_{2i-1}^1=(x-1)^2$

$(A=B=C)=\sum_{i=1}^{[\frac{X-1}{3}]} C_{(X-1)rem3+3(i-1)}^0=[\frac{X-1}{3}]$

$X=502,(C_{501}^3)-6(250)^2+8(167)-6(0)+3(250)=20460336$

$X=500,(C_{499}^3)-6(249)^2+8(166)-6(1)+3(249)=20214312$

TOP

返回列表 回复 发帖