我試著把人數降低來算:
假設有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... 我還想不出對這個解法好一點的詮釋...
有請各位高手替我想想看了~
感恩!