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

[XII (Mathkid)]

※ 引述《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     : 想請問XII這些數學知識都是從哪些書學到的?
→ XII         : Enumerative Combinatorics, Stanley
推 yyc2008     : 感謝
→ XII         : 這本是比較經典的(但比較雜)
推 steve1012   : 謝謝！！ 我仔細想想
推 steve1012   : 想請教一下何謂空前大 是指目前最大嗎
對
推 steve1012   : 想問一開始設內奸是怎麼來的
→ steve1012   : 打錯 設s是怎麼來的
其實 (-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   : 我後來想到的是分成group 以後直接讓最高的擺前面
→ steve1012   : 矮的讓他擋 排列數剛好是畫圓圈的個數 就是stirling
→ steve1012   : 的定義
→ steve1012   : 好像就是你第一個講的 另外想請教一下這在書裡的哪
→ steve1012   : 張 想好好讀一下這本不過好像有兩側頗多 想跳著看
→ XII         : 第一章就有了
→ XII         : 另外也推薦 A Course in Enumeration, Aigner