Re: [離散] 生成函數解遞減序列

[cometic ( )]

※ 引述《wsx02 ()》之銘言：
: {0,1,..,9}取5個數的方法數
: 1. 這5個數為decreasing order
: 補習班老師給C(9,5)+C(9,4)
: 2. 這5個數為non-increasing order
: 補習班老師給H(10,5)-1
: 請問這兩題如果用生成函數該怎麼解?
: 謝謝


1.

f(x_0,x_1,...,x_9)=(1+x_0)(1+x_1)...(1+x_9)

所求為deg(f)=5之係數:

也就是f(x,x,...,x)的x^5之係數=(1+x)^10的x^5之係數

C(10,5)=C(9,5)+C(9,4)

2.
  g(x_0,x_1,...,x_9)

=(1+(x_0)+(x_0)^2+...)(1+(x_1)+(x_1)^2+...)...(1+(x_9)+(x_9)^2+...)

所求為deg(g)=5之係數:

也就是g(x,x,...,x)的x^5之係數

=(1/(1-x))^10的x^5之係數=(10)(11)(12)(13)(14)/(5!)=C(14,5)=H(10,5)

--

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.34.121
※ 編輯: cometic         來自: 140.114.34.121       (12/02 19:11)
推 wsx02       :謝謝