※ 引述《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