[其他] 離散一題

看板Math作者 (俊偉)時間3年前 (2020/10/15 17:11), 編輯推噓0(0推 0噓 23→)
留言23則, 2人參與, 3年前最新討論串9/15 (看更多)
題目:https://imgur.com/a/dqZwWZL (a),(b),(C)-i已解 C(n,k)表from n choose k (c)-i: 我得到的expression: C(2n,n)-C(2n,n-1)=1/(n+1) * C(2n,n) (c)-ii覺得怪怪 largest value where the path contains (i,i) 不是應該是legal paths from (0,0) to (i,i) -> F[i] 和legal paths from (i,i) to (n,n) -> F[n-i] 所以應該是F[i] * F[n-i]嗎 F[n-i-1]是怎麼來的? 我哪個地方想錯 (c)-iii 完全沒想法，求解 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.224.186.234 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1602753068.A.401.html
→
10/16 10:36, 3年前 , 1F
c-ii是指將所有的legal path分類 分在第i類的legal
10/16 10:36, 1F
→
10/16 10:38, 3年前 , 2F
path滿足他最後一次經過x=y這條線時 是在(i,i) 他之
10/16 10:38, 2F
→
10/16 10:40, 3年前 , 3F
前可能可以碰到很多個(k,k) 如果k比i小的話 但他之
10/16 10:40, 3F
→
10/16 10:41, 3年前 , 4F
後不會碰到(m,m) 對所有的m比i大
10/16 10:41, 4F
→
10/16 10:42, 3年前 , 5F
所以第i類的總數是 [從(0,0)走到(i,i)的個數] 乘上
10/16 10:42, 5F
→
10/16 10:45, 3年前 , 6F
[從(i+1,i)到(n,n-1)但不超越x-1=y的個數] 即
10/16 10:45, 6F
→
10/16 10:48, 3年前 , 7F
F[i]*F[n-i-1] 所以對所有的i<n 我們有F[n]是這n-1
10/16 10:48, 7F
→
10/16 10:50, 3年前 , 8F
類的總和 F[0]*F[n-1]+F[1]*F[n-2]+...+F[n-1]*F[0]
10/16 10:50, 8F
→
10/16 10:52, 3年前 , 9F
C(2n,n)/(n+1)有個專有名詞Catalan number 上面這個
10/16 10:52, 9F
→
10/16 10:54, 3年前 , 10F
是Catalan number的遞迴式
10/16 10:54, 10F
→
10/16 10:55, 3年前 , 11F
iii我在懷疑出錯題目了 他應該是要問"有n個節點的
10/16 10:55, 11F
→
10/16 10:59, 3年前 , 12F
binary tree"的個數 (就是Catalan number 遞迴式的
10/16 10:59, 12F
→
10/16 11:02, 3年前 , 13F
證明請見文章代碼#1VG0YxQP) 但在binary tree中
10/16 11:02, 13F
→
10/16 11:05, 3年前 , 14F
degree是2的node不只有1個 binary tree已經和一般
10/16 11:05, 14F
→
10/16 11:05, 3年前 , 15F
tree的概念不太一樣了 冏
10/16 11:05, 15F
→
10/16 11:09, 3年前 , 16F
雖然題目想強加left subtree和right subtree的概念
10/16 11:09, 16F
→
10/16 11:11, 3年前 , 17F
但binary tree是允許subtree中left或right subtree
10/16 11:11, 17F
→
10/16 11:12, 3年前 , 18F
可以是空的
10/16 11:12, 18F
→
10/16 11:13, 3年前 , 19F
最簡單的看法是考慮n=3 滿足題目所述的spanning
10/16 11:13, 19F
→
10/16 11:14, 3年前 , 20F
tree的個數是3 但3不是任何一個Catalan number
10/16 11:14, 20F
→
10/16 13:58, 3年前 , 21F
這樣看起來c-i, c-ii, c-iii根本就在講同一件事...
10/16 13:58, 21F
→
10/16 15:39, 3年前 , 22F
應該是 題目應該就是想表達 "方格走法數問題" 和
10/16 15:39, 22F
→
10/16 15:40, 3年前 , 23F
"二元樹個數問題" 會產生一樣的generating function
10/16 15:40, 23F
‣ 更多 LiquidTLO 的文章
文章代碼(AID): #1VY18iG1 (Math)
討論串 (同標題文章)
完整討論串 (本文為第 9 之 15 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共15篇)
‣ 更多 LiquidTLO 的文章
文章代碼(AID): #1VY18iG1 (Math)