[理工] stack permutation

看板Grad-ProbAsk作者 (ㄚ冰)時間8年前 (2017/09/02 13:53), 編輯推噓3(3推 0噓 15→)
留言18則, 4人參與, 最新討論串1/1
公式是說n個data輸出次序 可能數為1/(n+1) * C(2n,n) 想知道這是怎麼推倒出來的 很概念的講法也沒關係 我想不太出來這個要怎麼推 ><謝謝了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.15.196 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1504331597.A.779.html
推
09/02 14:12, , 1F
n個data的輸出次序可以想成一棵具有n個node的binary tre
09/02 14:12, 1F
→
09/02 14:12, , 2F
e的結構數目，記作An好了。
09/02 14:12, 2F
→
09/02 14:12, , 3F
固定Root的點，左子樹跟右子樹則剩下n-1個node可以擺，
09/02 14:12, 3F
→
09/02 14:13, , 4F
如果左邊擺1個node右邊就是擺n-2個node。
09/02 14:13, 4F
→
09/02 14:13, , 5F
，如果左邊擺2個node右邊就是擺n-2個，依此類推下去
09/02 14:13, 5F
→
09/02 14:14, , 6F
如果用寫成遞迴公式的話就是An=A1*An-2+A2*An-3+....+An
09/02 14:14, 6F
→
09/02 14:14, , 7F
-3*A2+An-2*A1
09/02 14:14, 7F
→
09/02 14:15, , 8F
再搭配生成函數下去求解得你所說的公式，如果沒有學離
09/02 14:15, 8F
→
09/02 14:15, , 9F
散的話直接記下來就好，推導的過程有點麻煩。
09/02 14:15, 9F
推
09/02 14:25, , 10F
洪X的資料結構有
09/02 14:25, 10F
→
09/02 15:15, , 11F
謝謝這個後面的算法我會了
09/02 15:15, 11F
→
09/02 15:16, , 12F
我是再複習剛好看到，他有教可是我沒記得他有證過，可
09/02 15:16, 12F
→
09/02 15:16, , 13F
能我恍神了
09/02 15:16, 13F
→
09/02 15:18, , 14F
想起來離散有教這個(二元樹個數，不過要用到摺積的題
09/02 15:18, 14F
→
09/02 15:18, , 15F
目不太多就印象很不深
09/02 15:18, 15F
推
09/02 17:55, , 16F
特殊型遞迴幾乎都在講這個，我看了兩遍才稍微看懂 囧
09/02 17:55, 16F
→
09/02 21:01, , 17F
還行因為之前念訊號系統，整學期一直在叫我們算摺積
09/02 21:01, 17F
→
09/02 21:01, , 18F
囧
09/02 21:01, 18F
‣ 更多 TMDTMD2487 的文章
文章代碼(AID): #1PgaTDTv (Grad-ProbAsk)