[其他] 離散一題

[LiquidTLO (俊偉)]

題目: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
→ hwanger     : c-ii是指將所有的legal path分類 分在第i類的legal
→ hwanger     : path滿足他最後一次經過x=y這條線時 是在(i,i) 他之
→ hwanger     : 前可能可以碰到很多個(k,k) 如果k比i小的話 但他之
→ hwanger     : 後不會碰到(m,m) 對所有的m比i大
→ hwanger     : 所以第i類的總數是 [從(0,0)走到(i,i)的個數] 乘上
→ hwanger     : [從(i+1,i)到(n,n-1)但不超越x-1=y的個數] 即
→ hwanger     : F[i]*F[n-i-1] 所以對所有的i<n 我們有F[n]是這n-1
→ hwanger     : 類的總和 F[0]*F[n-1]+F[1]*F[n-2]+...+F[n-1]*F[0]
→ hwanger     : C(2n,n)/(n+1)有個專有名詞Catalan number 上面這個
→ hwanger     : 是Catalan number的遞迴式
→ hwanger     : iii我在懷疑出錯題目了 他應該是要問"有n個節點的
→ hwanger     : binary tree"的個數 (就是Catalan number 遞迴式的
→ hwanger     : 證明請見文章代碼#1VG0YxQP) 但在binary tree中
→ hwanger     : degree是2的node不只有1個 binary tree已經和一般
→ hwanger     : tree的概念不太一樣了 冏
→ hwanger     : 雖然題目想強加left subtree和right subtree的概念
→ hwanger     : 但binary tree是允許subtree中left或right subtree
→ hwanger     : 可以是空的
→ hwanger     : 最簡單的看法是考慮n=3 滿足題目所述的spanning
→ hwanger     : tree的個數是3 但3不是任何一個Catalan number
→ LiquidTLO   : 這樣看起來c-i, c-ii, c-iii根本就在講同一件事...
→ hwanger     : 應該是 題目應該就是想表達 "方格走法數問題" 和
→ hwanger     : "二元樹個數問題" 會產生一樣的generating function