Re: [理工] 離散 Catalan number 括號方法
※ 引述《Heyso (Heyso)》之銘言：
: Catalan Number看到頭痛還是很多問題
: 請教版上大大
: https://imgur.com/a/N9mxmPH
: 例題47中，求的是n個變數可以有幾種括號方法
: 前面的例題45中有規定每次只能結合兩項
: 書上轉換成RU的方式來解
: https://imgur.com/a/ukpRiNQ
: 但小弟不太懂
: 1.為何只保留左括號和前3個變數
只去掉右刮弧，把左括弧當成運算子(operator)，就是 pre-order。
任意一棵二元樹，將其樹葉當成運算元(operand)，非樹葉節點當運算子(operator)。
以 pre-order 排序，再去掉最後一個算元，
則上述由算子與算元組成的字串恰為 Dyck word，也就是等於合法的RU字串。
: 2.RRRUUU的組合中，不就相當於結合三項了嗎
: 為何還是合法的?
RRRUUU
(((123
補上4
(((1234
將上面的字串看成pre-order，把左括弧當運算子
(((12)3)4)
: 3.RRURUU(圖片中第三個組合)若加入x4和右括號
: 可以寫成((x1(x2x3x4)))和((x1(x2x3)x4))兩種方法
: 一個是合法的，另一個不是
: 那為什麼還要省略掉第四個變數呢
為了湊出合法的RU字串，否則會多出一個U。
-----
轉換步驟整理如下:
<A> monotonic lattice paths
RURRUU
<A to B>
R → (
U → )
<B> Dyck word
( )(( ) )
<B to C>
( ______ ) ______
│ ↓ │ ↓
│ 左子樹 │ 右子樹
└──┬──┘
↓
根
( )(( ) )
a 1 abc 2 c 3 b 4
<C> binary tree
a
/ \
1 b
/ \
c 4
/ \
2 3
<C to D>
父
┌──┴──┐
↓ ↓
( 葉 葉 )
a bc c ba
(1((2 3)4))
<D> expression (運算式)
(1((2 3)4))
<D to E>
去掉右刮弧後
再去掉最後一個運算元
<C to E>
先pre order
再去掉最後一個樹葉節點
<E>
(1((2 3
或
a1bc2 3
<E to A>
左括弧 → R
運算元 → U
或
非樹葉節點 → R
樹葉節點 → U
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.248.67.227
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1530596995.A.5D9.html
※ 編輯: JKLee (211.72.73.139), 07/03/2018 18:40:16
推
07/03 21:14,
5年前
, 1F
07/03 21:14, 1F
→
07/03 21:15,
5年前
, 2F
07/03 21:15, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：