Re: [理工] 離散生成函數

[A4P8T6X9 (殘廢的名偵探)]

※ 引述《PTT007 (鍵盤007)》之銘言：
: (1)
: There are five kinds of balls: red, black, white, blue, and green.
: We draw balls 8 times and then there are 5^8 combinations for these drawings.
: (a) How many of these 5^8 drawings contain all the five colors of balls?

我會討論，因為一定要有5種顏色，所以剩下3個地方，有111(皆不同顏色)，21(2同一不
同)，3(皆同)。

所以，

第一種：C(5,3)*8!/2^3 (因為有三種，兩個顏色相同)
第二種：C(5,2)*8!/3!*2
第三種：C(5,1)*8!/4!


: (b) How many drawing of (a) contain exactly three colors in the first 4 balls
: of drawing the 8 times?


: (2)
: Consider the equation x+y+z=11, where x,y and z are nonegative integers.
: How many solutions does it have if the condition 5>=x>=2, 6>=y>=3, 7>=z>=4
: is satisfied?

相當於求x^11次方的係數。

(x^2+x^3+x^4+x^5)(x^3+x^4+x^5+x^6)(x^4+x^5+x^6+x^7)

=x^9(1-x^4/1-x)(1-x^4/1-x)(1-x^4/1-x)  (提出x^2, x^3, x^4)

=x^9(1-x^4)^3(1-x)^(-3)

=x^9(1-3x^4+...)Σ(r=0~∞)C(3+r-1,r)x^r


 所以11次方的係數是 C(4,2)。


其實這題上界可以忽略，把2，3，4分別給xyz之後，只剩下2，不管怎樣分都不會爆，相當
於解 x+y+z=2 ，其中x, y, z >=0 ，解出來就是 C(2+3-1,2)=C(4,2)


: 求詳解

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.120.228.19
推 PTT007:感謝
→ PTT007:想請問第一題的(b)小題怎麼解？
→ mango3888:a用生成函數解應該是 每個顏色至少一個 令成（x+x^2+x^3
→ mango3888:……)^5 求x^8的係數
→ mango3888:應該好想很多
推 mango3888:b 先取哪三個顏色c(5,3) 因為四個必定要有三個顏色 所以
→ mango3888:多一個球有三種取法乘3 作排列4!/2! 此時前四顆排完 最
→ mango3888:後就隨便取c(5,3)x3x(4!/2!)x5^4
→ mango3888:以上個人見解 未必正確：）
→ A4P8T6X9:後面是接續a的，所以每一個顏色也都要出現一次。
→ A4P8T6X9:目前沒想法。
推 mango3888:喔喔續a 那我解錯了 sorry
推 jeremy4849:（b) 答案供參考 http://ppt.cc/SoW1
→ A4P8T6X9:不是前4個恰3個同色？
推 jeremy4849:我猜是前5個球，恰有三色
推 jeremy4849:說錯 前四個球
→ jeremy4849:那我算錯摟
推 patabon:我認為是前四顆洽有三色
推 patabon:另外題目是討論取出後之排列，而非取出之組合
→ patabon:則生成函數應是(e^x-1)^5 求x^8/(8)!之coe 這展開相當殘暴
→ patabon:所以A大以情況來討論，我覺得是較佳的方法
推 mango3888:恩恩 應該是排列才對 想錯嘍。