ordered tree和原本binary的差別在於他不限制child的個數, child有次序之分, 但只有一個child時就不像binary tree有分左右; 假設 a_n 為 number of rooted ordered tree on n vertices, 你可以把tree用DFS的方式traverse一便, 在第一次經過一個點 v 時就放一個左括號, 在所有的 v 的 child都被你掃完最後又回到 v 時就放一個右括號, 如此一來, root那一點所對應的括號如果不要看的話(因為那個括號一定在最外面), 這a_n棵樹便可一一對應至root以外那n-1個點用上述的方法所形成之括號的方法, 所以a_n = c_(n-1), 大致上是這樣
另外還有一種很簡潔的方法可以解出a_n, 是用symbolic的概念來解, 不過你可能會不太習慣這種方法, 那就隨便看看就好: 假設 A(x) 為 a_n 之生成函數, A(x) = x + xA(x) + xA(x)^2 + xA(x)^3 +..., 其中第一項的 x 代表的是root那一點, A(x)的次方就代表root有幾個child, 則 A(x) = x/(1-A(x)) = (1-(1-4x)^(1/2))/2 = xC(x), where C(x) is the G.F. of Catalan number
ordered tree和原本binary的差別在於他不限制child的個數, child有次序之分, 但只有一個child時就不像binary tree有分左右; 假設 a_n 為 number of rooted ordered tree on n vertices, 你可以把tree用DFS的方式traverse一便, 在第一次經過一個點 v 時就放一個左括號, 在所有的 v 的 child都被你掃完最後又回到 v 時就放一個右括號, 如此一來, root那一點所對應的括號如果不要看的話(因為那個括號一定在最外面), 這a_n棵樹便可一一對應至root以外那n-1個點用上述的方法所形成之括號的方法, 所以a_n = c_(n-1), 大致上是這樣
回覆刪除另外還有一種很簡潔的方法可以解出a_n, 是用symbolic的概念來解, 不過你可能會不太習慣這種方法, 那就隨便看看就好:
假設 A(x) 為 a_n 之生成函數,
A(x) = x + xA(x) + xA(x)^2 + xA(x)^3 +...,
其中第一項的 x 代表的是root那一點,
A(x)的次方就代表root有幾個child,
則 A(x) = x/(1-A(x)) = (1-(1-4x)^(1/2))/2
= xC(x), where C(x) is the G.F. of Catalan number
感謝助教回答 ^^
回覆刪除另外請問一下 這樣子寫的話 要證明他可以轉換成括號配對問題的正確性嗎
回覆刪除我剛剛翻DS課本
好像tree有一種表示法就是括號表示法(nested表示法)
差別好像是走到leaf的話就不加括號
助教的解法好像是無論走到什麼點都用括號括起來(一樣是nested 表示法)
這樣子 忽然能夠理解會什麼能這樣解了 XD
嗯, 有時間的話正確性得盡量說明, 當然你也可以用你說的nested表示法來描述, 觀念上應該都是相通的
回覆刪除