二分木の数を数える

Question

(私は数学の知識がある学生なので、特定の種類の二分木の数を数える方法を知りたいと思っています。)

Wikipediaのページを見てみると、 二分木, 、サイズ $n$ のルート付き二分木の数はこれになるというこの主張に気づきました カタルーニャ語番号:$$C_n = \dfrac{1}{n+1}{2n を選択}$$

しかし、どうやって自分でそのような結果を思いつくことができるのか理解できませんか？この結果を見つける方法はありますか?

さて、サブツリーの順序 (どれが左でどれが右か) を考慮しない場合はどうなるでしょうか?たとえば、私の観点からは、次の 2 つの木は同じであると考えます。

   /\   /\
  /\     /\

同様の方法を適用して、正確に $n$ ノードを持つこれらのオブジェクトの数をカウントすることは可能でしょうか?

Answer 1

この場合のツリーのような多くのタイプの組み合わせオブジェクトをカウントするには、コンビナトリアルオブジェクトの構築方法の説明からそのようなカウントを機械的に導き出すことができる強力な数学ツール（象徴的な方法）があります。これには、関数の生成が含まれます。

優れた参照はです 分析組み合わせ 故フィリップ・フラジョレットとロバート・セッジウィックによって。上記のリンクから入手できます。

故ハーバート・ウィルフの本 生成機能 別の無料ソースです。

そしてもちろん 具体的な数学 GKPは宝庫です。

---

バイナリツリーの場合、それは次のようになります。まず、木の明確な定義が必要です。

バイナリツリーは、すべての非葉のノードが正確に程度2を持つルート化されたツリーです。

次に、私たちが呼びたいものに同意する必要があります サイズ 木の。

左側では、すべてのノードが等しくなります。真ん中では、葉と非葉を区別します。右側には、葉が除去された剪定されたバイナリツリーがあります。 2つのタイプ（左と右）の単位ブランチがあることに注意してください！

これで、これらの組み合わせオブジェクトがどのように構築されるかについての説明を導き出す必要があります。バイナリツリーの場合a 再帰的な分解 可能です。

$ mathcal {a} $を、最初のタイプのすべてのバイナリツリーのセットとし、次のとおりです。

「バイナリツリーのクラスのオブジェクトは、ノードまたはノードに続く2つのバイナリツリーが続くものです。」これは、セットの方程式として書くことができます。

$$ mathcal {a} = { bullet } cup bigl（ { bullet } times mathcal {a} times mathcal {a} bigr）$$

このクラスの組み合わせオブジェクトを列挙する生成関数$ a（z）$を導入することにより、セット方程式を生成関数を含む方程式に変換できます。

$$ a（z）= z+za^2（z）$$

すべてのノードを均等に処理し、そのサイズの概念としてツリー内のノードの数を取得するという私たちの選択は、変数$ z $でノードを「マーク」することによって表されます。

これで、2次方程式$ za^2（z）-a（z）+z = 0 $ for $ a（z）$を解くことができ、通常どおり2つのソリューションを取得できます。

$$ 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}。$$

サイズの2番目の概念から始める場合、再帰分解は次のとおりです。

別のクラスの組み合わせオブジェクト$ mathcal {b} $を取得します。 「バイナリツリーのクラスのオブジェクトは、2つのバイナリツリーが続く葉または内側のノードのいずれかです。」

同じアプローチを使用して、$ mathcal {b} = { square } cup bigl（ { bullet } times mathcal {b} times mathcal {b} bigr）$ $ Into $ mathcal {b} = 1+zb^2（z）$。 「サイズ」はここでは異なるため、変数$ z $は葉ではなく内部ノードのみをマークします。別の生成機能も取得します。

$$ b（z）= frac {1- sqrt {1-4z}} {2z} $$

係数の抽出

$$ [z^n] b（z）= frac {1} {n+1} binom {2n} {n}。$$

class $ mathcal {a} $ and $ mathcal {b} $は、$ n $ nodesのバイナリツリーには$ n+1 $の葉、したがって$ 2n+1 $ nodesが合計であるため、カウントに同意します。

最後のケースでは、もう少し一生懸命働かなければなりません：

これは、空ではないプルーニングバイナリトライの説明です。これを$$ begin {align} mathcal {c}＆= { bullet } cup bigl（ { bullet } times mathcal {c} bigr） cup bigl（ { bullet } times mathcal {c} bigr） cup bigl（ { bullet } times mathcal {c} times mathcal {c} bigr） mathcal {d }＆= { epsilon } cup bigl（ { bullet } times mathcal {c} times mathcal {c} bigr） end {align} $$

生成関数で書き直します

$$ begin {align} c（z）＆= z+2zc（z）+zc^2（z） d（z）＆= 1+zc^2（z） end {align} $$

二次方程式を解きます

$$ begin {align} c（z）＆= frac {1-2z- sqrt {1-4z}} {2z} d（z）＆= frac {1- sqrt {1-4z {1-4z }} {2z} end {align} $$

そしてもう一度取得します

$$ [z^n] c（z）= frac {1} {n+1} binom {2n} {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ürmannInversion Formula 我々が得る

$$ [z^n] e（z）= frac {1} {n+1} binom {2n} {n} $$

そこで、バイナリツリーと同じくらい多くの一般的な木があることを証明しました。一般的なツリーとバイナリツリーの間に双方向があるのも不思議ではありません。バイジェクションは次のように知られています 回転対応 （リンクされた記事の最後で説明）。これにより、2つの一般的なツリーをバイナリツリーとして2つ保存できます。

クラス$ mathcal {c} $の左右の兄弟を区別しない場合、さらに別のクラスの木$ mathcal {t} $：

単一のバイナリツリー。 $$ mathcal {t} = { bullet } times mathrm {seq} _ { le2}（ mathcal {t}）$$生成関数もあります$$ t（z）= frac {1-z- sqrt {1-2z-3z^2}} {2z} $$ただし、係数は異なります。 Motzkin Numbers $$ [Z^n] t（z）= frac {1} {n} sum_k binom {n} {k} binom {nk} {k-1}。$$

ああ、あなたが機能を生成するのが好きでないなら、他にもたくさんの証拠があります。見る ここ, 、バイナリツリーのエンコードをDyckの単語として使用し、再帰的な定義から再発することができるものがあります。その後、その再発を解決することも答えを与えます。ただし、象徴的な方法により、組み合わせオブジェクトの青写真と直接動作するため、そもそも再発を思い付かないようにします。

Answer 2

生成関数は非常に強力で非常に便利な魔法の杖です。最初の質問 (なぜ $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))). 。これが全単射である理由を以下に説明します。それを理解すれば、数えるのは簡単です。$\pm1$ の $\binom{5+6}{5}$ シーケンスがあり、可能な巡回置換の 1 つを選択したため、$5+6$ で除算しました。

最初の全単射。 ML におけるツリーの一般的な定義は次のとおりです。 type tree = T of tree * tree | E;つまり、ツリーには 2 つの (順序付けられた) サブツリーがあるか、空です。ツリーがどのように構築されるかは次のとおりです。 T(T(E,E),T(T(E,E),T(E,E))). 。綿毛を落として、単純に書くことができます TTEETTEETEE. 。そのような説明はすべて次の文で終わります。 E, したがって、これは冗長です。 TTEETTEETE. 。(空のツリーが空の文字列に対応することに注意してください。) これらの文字列には、各プレフィックスが少なくとも Es と同じ数の T を持ち、合計で $n$ T と $n$ Es があるという特性があります。ここで、$n$ はツリーのノードの数です。

2番目の全単射。 ここで、T を +1 に、E を -1 に置き換えます。したがって、$n$ 値 +1、$n$ 値 -1、およびすべての接頭辞の合計 $\ge0$ を持つシーケンスを調べます。

3番目の全単射。 プレフィックスの要件を少し変更します。空ではない各プレフィックスの合計が $>0$ になるように求めます。これを可能にするために、$n+1$ の値を +1 にし、$n$ の値を -1 にします。(そうしないと、文字列全体の合計が 0 になり、プレフィックスの条件を満たせなくなります。) これらのシーケンスは +1 で始まる必要があります。つまり、先頭に +1 が付いていることを除けば、実際には以前と同じです。

ラニーの物件。 ここで、シーケンスのことを少し忘れて、次の有限シーケンスを考えてみましょう。 整数 $x_1$、$\ldots\,$、$x_m$ の合計は 1 です。すべての空でないプレフィックスが正の合計を持つ場合、このシーケンスの巡回置換は同じ特性を持ちません。なぜ？さて、$x_k,\ldots,x_m,x_1,\ldots,x_{k-1}$ も空ではない接頭辞がすべて正であるような $k e1$ があるとします。次に、 $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$ の数値の中から +1 に等しい $n+1$ を選択する必要があり、その他は -1 になります。これを行うには ${2n+1\choose n+1}$ 方法があります。ただし、これまでにカウントされた $2n+1$ シーケンスのうち、正の接頭辞を持つのは $1$ だけです。したがって、ルート化され、順序付けられたバイナリ ツリーの数は次のようになります。

$${1\over2n+1}{2n+1\choose n+1}={1\over2n+1}{2n+1\over n+1}{2n\choose n}={1\over n+ 1}{2n を選択}$$