Re: [中學] 排列組合排隊問題

看板Math作者XII (Mathkid)時間9年前 (2016/07/13 14:20)推噓5(5推 0噓 10→)

留言15則, 3人參與討論串2/2 (看更多)

※ 引述《steve1012 (steve)》之銘言： : 題目如下 : 假設我們現在有n個人都有不同的身高 : 現在我希望n個人排成一列從左邊看只能看到x個人從右邊看只能看到y個人 : (身高矮的會被擋住) : 這樣的話給定 n x y 會有幾種排隊的方式？換個符號 (把原來的 x,y 換成 p,q) 設 n 為正整數, 將 1,...,n 排成一列, 且由左至右有 p 個空前大, 由右至左有 q 個空前大則方法數有幾種? 設 |s(n,k)| 為 1,...,n 的排列中有 k 個由左至右的空前大的排列個數 (ps. s(n,k) 即為 Stirling number of first kind |s(n,k)| 亦為 S_n 中的 permutation 的 cycle decomposition 有 k 個 cycle 的 permutation 數易知 |s(n+1,k)| = n*|s(n,k)|+|s(n,k-1)|) 則易知 x(x+1)...(x+n-1) = Σ_{1≦k≦n} |s(n,k)| x^k 故所求為 |s(n-1,p+q-2)|*C(p+q-2,p-1) 或所求 = [x^p y^q] (xy)(x+y)(x+y+1)...(x+y+n-2) ([x^p y^q] 表求 x^p y^q 之係數) = [x^{p-1} y^{q-1}] (x+y)(x+y+1)...(x+y+n-2) = C(p+q-2,p-1)*(1~n-2 任選相異 n-p-q+1 個乘積之和) eg. n=5, p=3, q=2 有 13254, 21354, 23154,... => 12 個 12534, 13524, 14523,... => 6 個 ==> 共 18 個 [x^3 y^2] (xy)(x+y)(x+y+1)(x+y+2)(x+y+3) = [x^2 y] (x+y)(x+y+1)(x+y+2)(x+y+3) = C(3,2)(1+2+3) = 18 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.138.109.9 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1468390815.A.43F.html ※ 編輯: XII (101.138.109.9), 07/13/2016 14:24:40

推

yyc2008

07/13 21:37, , 1^F

07/13 21:37, 1^F

→

XII

07/13 23:11, , 2^F

07/13 23:11, 2^F

推

yyc2008

07/13 23:12, , 3^F

07/13 23:12, 3^F

→

XII

07/13 23:17, , 4^F

07/13 23:17, 4^F

推

steve1012

07/14 07:35, , 5^F

07/14 07:35, 5^F

推

steve1012

07/14 07:49, , 6^F

07/14 07:49, 6^F

對

推

steve1012

07/14 07:53, , 7^F

07/14 07:53, 7^F

→

steve1012

07/14 07:53, , 8^F

07/14 07:53, 8^F

其實 (-1)^{n-k}*s(n,k) 本來是 S_n 的 permutation 中可分為 k 個 disjoint cycle 的 permutation 個數但可以把這 k 個 cycle 排好, 視為有 k 個空前大的 permutation eg. (3 8 1)(6 5 4 7)(2 9) = (7 6 5 4)(8 1 3)(9 2) 但你也可以不要管 s(n,k), 直接看第二個做法: 用生成函數來看, 可得所求為 C(p+q-2,p-1)*(1~n-2 任選相異 n-p-q+1 個乘積之和) ※ 編輯: XII (140.122.136.15), 07/14/2016 11:53:16

→

steve1012

07/14 14:56, , 9^F

07/14 14:56, 9^F

→

steve1012

07/14 14:56, , 10^F

07/14 14:56, 10^F

→

steve1012

07/14 14:56, , 11^F

07/14 14:56, 11^F