作者LiquidTLO (俊偉)
看板Math
標題[其他] 離散一題
時間Thu Oct 15 17:11:04 2020
題目:
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://webptt.com/m.aspx?n=bbs/Math/M.1602753068.A.401.html
1F：→ hwanger : c-ii是指將所有的legal path分類 分在第i類的legal 10/16 10:36
2F：→ hwanger : path滿足他最後一次經過x=y這條線時 是在(i,i) 他之 10/16 10:38
3F：→ hwanger : 前可能可以碰到很多個(k,k) 如果k比i小的話 但他之 10/16 10:40
4F：→ hwanger : 後不會碰到(m,m) 對所有的m比i大 10/16 10:41
5F：→ hwanger : 所以第i類的總數是 [從(0,0)走到(i,i)的個數] 乘上 10/16 10:42
6F：→ hwanger : [從(i+1,i)到(n,n-1)但不超越x-1=y的個數] 即 10/16 10:45
7F：→ hwanger : F[i]*F[n-i-1] 所以對所有的i<n 我們有F[n]是這n-1 10/16 10:48
8F：→ hwanger : 類的總和 F[0]*F[n-1]+F[1]*F[n-2]+...+F[n-1]*F[0] 10/16 10:50
9F：→ hwanger : C(2n,n)/(n+1)有個專有名詞Catalan number 上面這個 10/16 10:52
10F：→ hwanger : 是Catalan number的遞迴式 10/16 10:54
11F：→ hwanger : iii我在懷疑出錯題目了 他應該是要問"有n個節點的 10/16 10:55
12F：→ hwanger : binary tree"的個數 (就是Catalan number 遞迴式的 10/16 10:59
13F：→ hwanger : 證明請見文章代碼#1VG0YxQP) 但在binary tree中 10/16 11:02
14F：→ hwanger : degree是2的node不只有1個 binary tree已經和一般 10/16 11:05
15F：→ hwanger : tree的概念不太一樣了 冏 10/16 11:05
16F：→ hwanger : 雖然題目想強加left subtree和right subtree的概念 10/16 11:09
17F：→ hwanger : 但binary tree是允許subtree中left或right subtree 10/16 11:11
18F：→ hwanger : 可以是空的 10/16 11:12
19F：→ hwanger : 最簡單的看法是考慮n=3 滿足題目所述的spanning 10/16 11:13
20F：→ hwanger : tree的個數是3 但3不是任何一個Catalan number 10/16 11:14
21F：→ LiquidTLO : 這樣看起來c-i, c-ii, c-iii根本就在講同一件事... 10/16 13:58
22F：→ hwanger : 應該是 題目應該就是想表達 "方格走法數問題" 和 10/16 15:39
23F：→ hwanger : "二元樹個數問題" 會產生一樣的generating function 10/16 15:40