Re: 台大離散

[wodahs (還我明日香!!)]

※ 引述《h04mp6286 (H28)》之銘言：
: ※ 引述《you00360842 (handsome chien)》之銘言：
: : X1+X2+...+Xn=r
: : 1<=X1<X2<....<Xn<=r
: : ㄧ開始以為trivial
: : 結果沒等號
: : 算出c(r,n)
: : 可是列幾個例子暴力法卻沒任何規律
: : 求解
: 這題目超難
: 敝人的超強同學提供一個想法
: 若今天題目是x+y+z=15
: x,y,z三者皆異(x<y<z)
: 令y=x+u
:   z=y+w=x+u+w
: 問題就變成3x+2u+w=15 (x,u,w>0)
: 此題應該可以比照辦理吧
: 變成n*x1+(n-1)*y2+(n-2)*y3+...+1*yn=r (x1,y2~yn>0)
: 然後就不會解了q_q
: 有強者可以解下去嘛？


明天要考成大 睡前靈光一閃想到一種解法

因為題目已知 1 <= X1 < X2 < X3 < ... <= r

推得  X1 >= 1, X2 >=2, X3 >=3, ...., Xn >=n, 其中 n<=r

令    Y1=X1-1, Y2=X2-2, Y3=X3-3, ..., Yn=Xn-n, Y1,...,Yn>=0

所以  Y1+Y2+ ... +Yn = (X1+X2+ ..+Xn) - (1+2+ ...+n)

因為題目已知 X1+X2+ ... + Xn = r

推得  Y1+Y2+ ... +Yn = r -(1+2+ ... +n) = r - n(1+n)*(1/2) = r-n-0.5

這題 將X平移成Y 來求非負整數個數解

因此答案為

  n+r-n-0.5-1        r-1.5
(              ) = (         )
   r-n-0.5           r-n-0.5



這是我想到的解法....這題出的好漂亮
換一種寫法 考試一緊張就完全寫不出來惹.....


--
╔══════════════════╗
║即使前路茫茫無盡  我的雙手仍抱著光明╚══════╗
║告別的時候  靜下來的心  歸於無有的身體 叫耳朵細聽 ║
║生存的奇妙  死亡的不可思議  花與風與城市 都同一樣 ║
╚═════════════════════════╝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.169.206.171
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1423587633.A.F3E.html
推 you00360842: 這樣可能出現Yi>Yj , i<j  吧
推 a95641126: 妳這亂解的把？
→ mkchiun1028: 這樣解可能出現 Y1=5 Y2=2-->X1=6 X2=4, X1>X2的情況
推 mkchiun1028: 我蠻確定這題答案是生成函數
推 mkchiun1028: 1/((1-x)(1-x^2)...(1-x^n)) 之中x^r的係數(有驗算過
→ mkchiun1028: 但這個生成函數係數求不出來
推 mkchiun1028: 更正：x^(r-n(n+1)/2)的係數
→ shcyril: xd
推 jeffliao1: 樓上答案應該是對的 跟我一樣~
→ jeffliao1: 做法就跟這篇一樣 只是不是求非負整數解
→ jeffliao1: 而是算r-n(n+1)/2的partition個數 就是看上面那個生成
→ jeffliao1: 函數的係數
→ JacobSyu: 寫完生成函數  好...要就給不要就算了....
→ wodahs: 看完大家的解說 終於懂了自己的盲點!! 感謝上面諸君強者!!