作者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/cn.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