※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 199.119.244.15
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1468386567.A.B62.html
題目如下
假設我們現在有n個人 都有不同的身高
現在我希望n個人排成一列 從左邊看只能看到x個人 從右邊看只能看到y個人
(身高矮的會被擋住)
這樣的話給定 n x y 會有幾種排隊的方式?
我自己的想法是
首先先把最高的挑出來
從剩下的n-1 個裡面挑(x-1)+(y-1) 個人 C(n-1, x+y-2)
從這些人挑x-1 個放一邊 C(x+y-2, x-1)
但是接下來就卡住了
不知道該如何排剩下 (n-1-x-y+2) 個人
難處在於 一側可能會擺很矮的人
舉例來說 假設身高分別為 1 ,2, 5, 7公分 身高的排列可能是
1 2 7
則在1 2 間不能排人
但要是排成
1 5 7
則2可以排在1,5 或是5,7間 所以會多一些排列的方式
我自己感覺這個題目沒有close form 但不是很確定
想請問大家有沒有什麼想法
謝謝
--