YLL討論網

How many ways are there first to pick a subset of r people from 50 people (each of a different height), and next to pick a second subset of s people such that everyone in the first subset is shorter than everyone in the second subset (explain it carefully.)

我試著把人數降低來算:
假設有3個人，身高分別是1、2、3 ，且已依照身高排序了
也假設兩個subset裡至少要有一個人
首先，把這三個人分成兩堆: [1]+[2,3] or [1,2]+[3]兩種情形
則... 所有可能情況有:

first subset	second subset
{1}	{2}
{1}	{3}
{1}	{2,3}
{2}	{3}
{1,2}	{3}

前三列是[1]+[2,3]下的所有分法；後三列則是[1,2]+[3]下的分法；中間那個第三列重疊了...
看起來很像是要用排容原理
可是到這裡我就卡住了... 不知道該如何往下想...
是不是我想錯了?
或是，有其它更有效率的解法嗎?
感謝幫助^_^"

................................................
我似乎想到一個疑似正確的解法...
r=1, s=2
C(3,1+2) = 1
r=1, s=1
C(3,1+1) = 3
r=2, s=1
C(3,2+1) = 1
so total is 1+3+1=5 ways to do it.
but... 我還想不出對這個解法好一點的詮釋...
有請各位高手替我想想看了~
感恩!

你的解法是對的，答案就是 ₅₀C_(r+s) ，解釋亦很簡單：
首先， ₅₀C_(r+s) 代表在50個人當中找r+s個人出來的組合數；
關鍵的是，在每(r+s)組合當中，s個人的高度比r個人高的組合只有一個，故答案就是 ₅₀C_(r+s) ；

e.g. 設總人數為10: 依序高度順序為A,B,C,D,...,J; r=2, s=3, r+s=5;
從10固人當中找5個出來的組合數為 ₁₀C₅ = 252, {A,B,C,D,E}, {A,B,C,D,F}, ..., {F,G,H,I,J}
而在每個組合當中, 在r中的2人必為最矮的2人，而s中的3人必為最高的3人
=> r與s的分佈在每個組合中只有一個可能... {A,B,C,D,E} -- r={A,B}, s={C,D,E}