iノードを持つバイナリツリーの数を計算する

Question

biをiノードのバイナリツリーの数とする。計算b10。

これは問題です。

私はこれまでのところ、これらを思い付くことができました：

B0=1 
B1=1 
B2=2 
B3=5 
B4=12 

それはすぐに私が大きくなるにつれて、あまりにも多くのビットを取得します。

誰もBiを計算するより良い方法は、ツリーを描き、それらを数えるのではないと思いますか？

Answer 1

OEISに答えを入力したところ、いくつかの結果が出ました。

有望な結果は、A000669 - n個の葉を持つ植林された樹木の減少数です。以下の例が提供されています：a（4）= 5、植え付けられた樹木を直列に植えたもの：（oooo）、（oo（oo））、（o（ooo））、（o（o（oo）））、 （oo））。それは、私たちの木は必ずしも植えられていないということです。

しかし、ちょっとした作業の後で、B4の値が正しくないことを通知する必要があります - 正解は14です。答えはクリアです。the Catalan numbers。カタロニア語の数字は、あなたがここに提示した問題（Wolfram経由）を含め、奇妙で多様な数を数えます。カタロニア語数字の定義（8）に注目する価値はあります - カタロニア語の数を定義する再発。この合計は、ノードの左側にあるノードの数を決定する（残りは右になる）と考えることができます。

これを簡単に概念化する方法は、Dyck単語を使用する方法です。 Xは「左括弧」を意味し、Yは「0」を意味する。 （私はツリーのリスト表現を使用しています - 左のノードは要素の左側のリストであり、逆も同様です;左または右のリストがない場合、それは葉とみなされます）。適切な場合には右かっこを入れます。次に、以下のようB3のための私達の木は、以下のとおりです。

（（（0）0）0）=> XXXYYY

（（0）0（0））=> XXYYXY

（0（0（ウィキペディアから0）））=> XYXYXY

（（0（0））0）=> XXYXYY

（0（（0）、0））=> XYXXYY

を、5 2 N-このフォームの長さのDyckワードは、XXXYYY、XYXXYY、XYXYXY、XXYYXY、およびXXYXYYです。最後に、クローズドフォーム

Bn = (1/(n + 1)) * (2n choose n) = (2n!)/((n+1)!(n!))