关于卡特兰数

学术版

ppip @ 2022-09-01 20:05:01

同时，我们令长度为 $2n$ 的“卡特兰序列”为满足如下条件的任意一个序列： - 有 $n$ 个 $1$ 和 $n$ 个 $-1$； - 任意前缀和 $\geq0$。显然，长度为 $2n$ 的“卡特兰序列”数量也是 $H_n$. 那么，有没有可能令每一棵 $n$ 个结点的二叉树和长度为 $2n$ 的“卡特兰序列”一一对应呢？

by RedLycoris @ 2022-09-01 20:13:21

@ppip 1则新增1个儿子并让指针指向该儿子，-1则回退一格？

有人能帮忙指出哪儿错了吗感觉会生成多叉树

by TensorFlow_js @ 2022-09-01 20:13:59

借楼求问卡特兰数

by Ew_Cors @ 2022-09-01 20:14:52

@paulzrm +1-1+1-1+1-1？

by RedLycoris @ 2022-09-01 20:15:51

@Ew_Cors 是这么错的，但不知道哪儿有问题

能生成树，而且能满足任意前缀和>=0和总和为0

by RedLycoris @ 2022-09-01 20:16:08

哦我懂了

by RedLycoris @ 2022-09-01 20:16:53

那这是树的括号序，，，

by RedLycoris @ 2022-09-01 20:17:25

麻了真的只能和二叉树对上吗

by Register_int @ 2022-09-01 20:40:10

@ppip 谔谔，参考卡特兰的组合意义，然后二叉树->括号序->卡特兰

by Register_int @ 2022-09-01 20:42:02

@paulzrm 多叉树要加括号吧

by RedLycoris @ 2022-09-01 20:49:18

@Register_int

(()()()())

1 1 -1 1 -1 1-1 1 -1 -1

咋对应二叉树啊

| 下一页