Re: [理工] [離散] 整數解個數

[privatewind (傷神客)]

※ 引述《taco205130 (taco)》之銘言：
: X1+X2+X3+Xn=M
: 且  X1<X2<X3....<Xn  求非零正整數解
: 很典型的問題..
: 可是我一直想不起來  之前的筆記跟書都不在身邊
: 希望大家幫幫忙 感謝了
這題要求通解，是不實際的(後面就會說明)
但是我們卻可以去求它的生成函數!!

令 X1+Y2 = X2, X1+Y2+Y3=X3 ...

X1+ X1+Y2 + X1+Y2+Y3 + X1+Y2+Y3+ .... + X1+Y2+Y2+Y3+...+Yn = M

n*X1 + (n-1)*Y2 + ... + Yn = M

又令 Zn=Yn-1 ,and Z1=X1-1
n*Z1 + (n-1)*Z2 + ... + Zn = M - (n+1)*n/2

看到這裡，大概就知道只能求它的生成函數了
      1           1                1
GF: ------ * ---------- * ... * -------
     1-nX     1-(n-1)X            1-X

接下來就是請勇者把他拆開求系數啦!~

--
錯了，請多多包函，我離散還沒唸呀=3=

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.126.187.85
※ 編輯: privatewind     來自: 59.126.187.85        (09/30 17:13)
※ 編輯: privatewind     來自: 59.126.187.85        (09/30 17:15)
→ a016258:你可以show 一下 n=2,m=3 跟 n=3,m=6 只有一組解嗎?
※ 編輯: privatewind     來自: 59.126.187.85        (09/30 19:07)
※ 編輯: privatewind     來自: 59.126.187.85        (09/30 19:10)
→ daniel770624:解得沒錯@@~
推 daniel770624:對Y>X^[(n+1)*n/2]*1/[(1-X^n)*(1-X^(n-1))..*(1-X)]
→ daniel770624:對Z>1/[(1-X^n)*(1-X^(n-1))..*(1-X)]