推 karaokstar:這樣會不會少兩種case x1 odd x3 even跟x1 even x3 odd 02/17 17:07
推 karaokstar:因為=18 所以四個數必須四偶 二偶二奇 四奇 所以沒少QQ 02/17 17:58
※ 引述《death888 (ZZZZ)》之銘言：
: Determine how many integer solutions there are to x1+x2+x3+x4=18 if 0<=xi<=7
: for all 1<=i<=4 and both x2 and x4 are odd.
: 請問有人可以幫忙算一下嗎
: 我算到(x^2-4x^10+6x^18-4x^26+x^34)Σrx^rΣrx^2r
: 非負整數解好像沒有 怪怪的
---
2 2
考慮 f(x) = (1 + x + ... + x^7) * (x + x^3 + x^5 + x^7)
(1 - x^8)^2 x^2 * (1 - x^8)^2
= ────── * ───────── if |x|<1
(1 - x)^2 (1 - x^2)^2
x^2 * (1+x)^2 * (1 - x^8)^4
= ──────────────
(1 - x^2)^4
2 4 ∞ 3+k 2k
= x (1 + 2x + x^2)(1 - x^8) * [ Σ C *x ]
k=0 3
所以 x^18 項的係數
4 m 3+k 4 m 3+k
= Σ C *(-1) * C + Σ C *(-1) * C
8m+2k=16 m 3 8m+2k=14 m 3
4 11 4 7 4 3 4 10 4 6
= C C - C C + C C + C C - C C
0 3 1 3 2 3 0 3 1 3
= 165 - 140 + 6 + 120 - 80
= 71
ps:
最後的結果可以整理成:
4 11 10 4 7 6 4 3
C *[ C + C ] - C *[ C + C ] + C C
0 3 3 1 3 3 2 3
4 4 4 4 4 4 4 4
= C *[ H + H ] - C *[ H + H ] + C H
0 8 7 1 4 3 2 0
^^^^^^^^^^^
(1)
該結果可以用排容原理去解釋
例如 (1)式的意思代表:
x1 + x2 + x3 + x4 = 18 constrained with x2 and x4 are odd
的所有非負整數解組合數
簡單的想法是根據加法原理，將問題 partition 成兩種 case
分別是 "x1 and x3 are odd" 和 "x1 and x3 are even"
就能簡單的求出共有 H(4,8) + H(4,7) 的所有組合數
其它的 term 也是一樣的想法，可以自己想一下~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.47.130
※ 編輯: doom8199 來自: 140.113.47.130 (02/17 14:05)