https://cs.stackexchange.com/questions/368
-
16-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian解决方案
为了计算多种类型的组合对象，例如在这种情况下的树，有强大的数学工具（符号方法），使您可以从描述中如何构建组合对象从描述中获得这种计数。这涉及生成功能。
一个很好的参考是 分析组合学 由已故的Philipe Flajolet和Robert Sedgewick撰写。它可以从上面的链接获得。
已故的赫伯特·威尔夫（Herbert Wilf）的书 生成功能学 是另一个免费来源。
而且当然 具体数学 GKP是宝库。
对于二进制树，它是这样的：首先，您需要对树的明确定义。
二进制树是一棵根树，每个非叶子节点都完全具有2度。
接下来，我们必须同意我们想打电话 规模 一棵树。
现在，我们必须得出如何构建这些组合对象的描述。对于二进制树 递归分解 可能。
令$ MATHCAL {a} $为第一个类型的所有二进制树的集合，然后我们有：
它读为：“二进制树类的对象是节点或节点，然后是两个二进制树。”这可以写为集合的等式：
$ MATHCAL {a} = { bullet } cup bigl（ { bullet } times times times mathcal {a} times times times mathcal {a} bigr）$$
通过引入列举此类组合对象的生成函数$ a（z）$，我们可以将设置方程转换为涉及生成函数的方程式。
$$ a（z）= z+za^2（z）$$
$$ a（z）= frac {1 pm sqrt {1-4z^2}}} {2z} $$
现在，我们只需要牛顿的（广义）二项式定理：
$$（1+x）^a = sum_ {k = 0}^ infty binom {a} {k} x^k $$
$ a = 1/2 $和$ x = -4z^2 $，将生成功能的封闭形式扩展回电源系列。我们这样做是因为，$ z^n $的系数只是尺寸$ n $的组合对象的数量，通常写为$ [z^n] a（z）$。但是，在这里，我们关于树的“大小”概念迫使我们寻找$ z^{2n+1} $的系数。经过一点点杂耍二项式和阶乘杂物之后，我们得到了：
$$ [z^{2n+1}] a（z）= frac {1} {n+1} binom {2n} {n} {n}。$$
如果我们从大小的第二个概念开始，则递归分解为：
我们获得了不同类别的组合对象$ MATHCAL {B} $。它读到：“二进制树类的对象是叶子或一个间节点，然后是两个二进制树。”
$$ b（z）= frac {1- sqrt {1-4z}}} {2z} $$
提取系数产量
$$ [z^n] b（z）= frac {1} {n+1} binom {2n} {n} {n}。$$
类$ MATHCAL {A} $和$ MATHCAL {B} $同意计数，因为带有$ N $内部节点的二进制树具有$ N+1 $叶子，因此总共$ 2N+1 $节点。
在最后一个情况下，我们必须更加努力：
并通过生成功能重写
$$ begin {align} c（z）＆= z+2zc（z）+zc^2（z） d（z）＆= 1+zc^2（z） end end {align} $$
求解二次方程
$$ begin {align} c（z）＆= frac {1-2z- sqrt {1-4Z}}}} {2z} {2z} d（z）＆= frac {1- sqrt {1-4z }} {2z} end {align} $$
再次得到
$$ [z^n] c（z）= frac {1} {n+1} binom {2n} {n} {n} quad n ge1 qquad [z^n] d（z）= frac { 1} {n+1} binom {2n} {n} quad n ge0 $$
请注意 加泰罗尼亚生成功能 是
$$ e（z）= frac {1- sqrt {1-4z}}} {2} $$
它列举了 一般树. 。那是树木对节点程度无限制的树。
$$ MATHCAL {e} = { bullet } times mathrm {seq}（ mathcal {e}）$$
它读为：“一类一般树的对象是一个节点，然后是可能的一般树的空序列。”
$$ e（z）= frac {z} {1-e（z）} $$
与 Lagrange-Bürmann倒置公式 我们得到
$$ [z^n] e（z）= frac {1} {n+1} binom {2n} {n}
旋转对应关系 （在链接文章的末尾解释），这使我们两个将每棵树存储为二进制树。
请注意，如果我们不区分类$ Mathcal {C} $中的左和右兄弟姐妹，我们将获得另一类的树$ Mathcal {t} $：
一元树。 $$ MATHCAL {t} = { bullet } times times mathrm {seq} _ { le2}（ mathcal {t}）$ $它们具有生成函数$ $ t（z）= frac {1-z- sqrt {1-2z-3z^2}}} {2z} $$，但是它们的系数不同。您会得到motzkin number $$ [z^n] t（z）= frac {1} {n} sum_k binom {n} {k} {k} {k} binom {nk} {k-1} {k-1}。$$
哦，如果您不喜欢生成功能，也有很多其他证据。看 这里, ，在某些地方，您可以将二进制树的编码用作戴克单词，并从它们的递归定义中得出复发。然后解决这种复发也给出了答案。但是，符号方法首先使您免于提出复发，因为它直接与组合对象的蓝图合作。
其他提示
产生的功能是一个非常强大，非常有用魔杖。下面解决第一个问题(为什么会有$C_n$树)是有点不可思议的。因此，可爱。
例。 产生一棵树的5美元$节点我们开始有顺序在美元+1美元生$5+1美元时，美元和-1$发生5美元$倍。例如, $+-++-+--++-$.在这些前缀以最小的(也可能是负面的)的总和，选择最长;在这种情况下, $+-++-+--$.采取这种前缀从一开始，并把它放在结束；在这种情况下，我们得到$++-+-++-+--$.现在改变$+$入$T$美元-$入$E$;在这种情况下，我们获得 TTETETTETEE.删除$T$从一开始，增加一个$E$在结束；在这种情况下，我们获得 TETETTETEEE.这是描述的树 T(E,T(E,T(T(E,T(E,E)),E))).下面有一些解释为什么这是一个双向注入.一旦你确信这计数是很容易的。有$\binom{5+6}{5}$序美元\1号$，然后我们划分的5美元+6$因为我们选择了一个可能的循环排列。
第一个双向注入. 一个典型定义的树木在是毫升 type tree = T of tree * tree | E;那是一棵树有两个(下令)子树，或者它是空的。这里是如何树木的构成： T(T(E,E),T(T(E,E),T(E,E))).滴下绒毛我们可以简单地写信 TTEETTEETEE.所有这些说明将结束 E, ，因此它是多余： TTEETTEETE.(注意，空树，现在对应的空串。) 这些字符串拥有的财产，每个前缀至少有许多Ts如Es，并在他们总共有$n$Ts和$n$Es，其中$n$数量的节点的树。
第二下的双射. 我们现在更换T+1和E-1.因此，我们正在寻找列与$n$值+1美元n$值-1，并与总结的所有前缀$\ge0$.
第三双向注入. 我们现在改变的需求为前缀的一点：我们要求的总和每个非空前缀美元>0$.这个可能我们让$n+1美元的价值+1and$n$值-1.(否则的总和的整串将是0并将无法满足所述条件为前缀。) 这些序列必须开始与+1.因此，他们真的都和以前一样，除了他们有一个+1坚持在开始。
阮内的财产。 现在要忘记我们的序列片刻，考虑一些有限的序列 整数 $x_1$,$\ldots\,$,$x_m$的总额是1。如果所有非空前缀有积极的款项，那么没有循环排列的该序列具有相同的财产。为什么？好吧，假设美元k e1$这样的美元x_k,\ldots,x_m,x_1、\ldots，x_{k-1}$还有所有的非空前缀积极的。然后$x_1+\cdots+x_{k-1}\ge1$(财产的序列从开始$x_1$)美元x_k+\cdots+x_m\ge1$(财产的序列从开始$x_k$);因此,$x_1+\cdots+x_m\ge2$，这违反了假定的总和为整个序列是1。
此外，鉴于某些序列的用总额1,总有一个循环排列，使所有非空前缀有积极的总和。(这是真实的，即使实际数字。)
结论。 现在让我们来算序列的+1和-1是在一个双向注入树木。美元2n+1美元的数字，我们必须选择$n+1美元的平等+1，其他人将被-1.有${2n+1\选择n+1}$的方式这样做。但是，只有1美元$美元2n+1美元序列数迄今为止的积极的前缀。因此，这些根源，有序的二进制的树木是：
$${1\over2n+1}{2n+1\选择n+1}={1\over2n+1}{2n+1 +1}{2n\选择n}={1 +1}{2n\选择n}$$
