Re: [理工] [離散]-排列組合
※ 引述《IDontBite (大便兔子)》之銘言：
: 從坐標原點(0,0)走到(n,n),
: 走法只能往上或往右(每步1單位),
: 自己的 y 座標必須恆小於等於 x 座標,
: (也就是必須在 x = y 這條線下方)
: 問走法有幾種?
: 答案是
: 2n
: C
: n
: _________
: (n+1)
: 想了好久都不懂為什麼, 有請高手0.0
你隔壁那個戴眼鏡的~他這麼說:
以代號R表示向右一步Right
以代號U表示向上一步Up
那此題目等於RURURRUUR.....等共2N個字做排列~
any time: 當時已走的 R的數量 ≧ 當時已走的 U的數量
亦等同 ()()(())括號做排列， 因為無 )( 此種括號排列
any time:當時已走的 "("的數量 ≧ 當時已走的 ")"的數量
[方法一]
全部的走法有:
2n
C
n
不合法的走法:
2n 2n!
C = _____________
n-1 (n+1)!(n-1)!
將一個R換成U
n+1 是U 向上一步
n-1 是R 向右一步
則這路徑的其中必有某處【當時已走的 U數量 > 當時已走的 R數量 】
=>使得 路徑高過 [x = y 這條線]
(就是不管怎麼走~必有違規的走法=就是超過x = y)
(全部的走法)-(不合法的走法)= 合法的走法
即可
---------------------
[方法二]
例如N=5
全部走法:
10
C
5
例R U R R U U R U R U
不合法的走法:
將第一個違法的字~與剩下來的字隔開
例 "U" | R R R U U R U R U
| | | | | | | | | | <=反向處理
U U U R R U R U R
---------------------------
變成 U U U U R R U R U R
也就是
10! 10
____ = c
4!6! 4
(全部的走法)-(不合法的走法)= 合法的走法
=========================================
2n
C
n
_________
(n+1)
其實這個公式叫 nth Catalan number
本身是求 n個點的有序二元樹 共有幾種
要用遞迴證明~非常難寫~
但是功用可套到各種等價題目~~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.137.203.215
※ 編輯: qazwsxee 來自: 114.137.203.215 (08/06 22:28)
※ 編輯: qazwsxee 來自: 114.137.203.215 (08/06 22:28)
※ 編輯: qazwsxee 來自: 114.137.203.215 (08/06 22:29)
※ 編輯: qazwsxee 來自: 114.137.203.215 (08/06 22:31)
推
08/06 22:31, , 1F
08/06 22:31, 1F
→
08/06 22:36, , 2F
08/06 22:36, 2F
推
08/06 22:50, , 3F
08/06 22:50, 3F
推
02/12 21:04, , 4F
02/12 21:04, 4F
討論串 (同標題文章)