※ 引述《pangfeng (P老師)》之銘言：
: 2n個人每人各買一張5元的票.
: n人身上只有10元硬幣一枚, 另外n人身上只有5元硬幣一枚.
: 賣票的人只有票, 沒有錢. 請問有幾種排隊方法可讓每人都買到票?
: (算排隊方法種類時所有10元的人皆視為相同, 且所有5元的人皆視為相同,
: 例如 5 5 5 10 10 10 算一種)
小弟來現醜一下，
因為每個擁有 10 元的人前面一定要有一個擁有 5 元的人買票，
所以可以將一個 (5 10) 順序視為一組。
當 n = 0 時，排列數有 null, 共 b_0 = 1 種。
當 n = 1 時，排列數有 5 10, 共 b_1 = 1 種。
當 n = 2 時，排列數有 5 10 5 10, 5 5 10 10, 共 2 種。
相當於 選定一組 5 10 當作一個二元樹的 root ，
將另一組 5 10 插入這個 root 的左子樹(5 10 的前面)或右子樹(5 10 的中間)。
5 10
/ \
b_l b_r
則其排列數共有 b_2 = b_1*b_0 + b_0*b_1 = 1 + 1 共 2 種。
= (b_1 有, b_r 無) + (b_1 無, b_r 有)
當 n = 3 時，排列數有 5 10 5 10 5 10, 5 10 5 5 10 10,
5 5 10 10 5 10, 5 5 10 5 10 10
5 5 5 10 10 10 共五種，
相當於 b_3 = b_2*b_0 + b_1*b_1 + b_0*b_2 = 2 + 1 + 2 = 5 種
=(兩組分入 b_l) + (b_1, b_r 各分入一組) + (兩組分入 b_r)
同理可推得 b_n = b_(n-1)*b_0 + b_(n-2)*b_1 + ... + b_(n-1)*b_0
接下來一堆數學符號我不會打... 所以略過
反正最後可以證出來答案是 (1/(n+1))*C(2n, n)
--
[10:11] <@llwang> Der Horizont vieler Menschen ist ein Kreis mit Radius
Null - und das nennen sie ihren Standpunkt.
[10:11] <@llwang> (fortune 看到的)
[10:14] <@llwang> 很多人的視野都是一個半徑為零的圓，而他們稱之為他們的觀點。
2005/04/14
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 59.124.152.16