Probabilistic enumeration and equivalence of nonisomorphic trees

この論文は、ラベルなし木の数に関するオッターの漸近公式に対する新しい確率的証明と、頂点数が増大するにつれてランダムなポリア木とランダムなラベルなし木の間の総変動距離がゼロに収束することを示す近似結果を提示し、その手法を木に類似したグラフのクラスへ拡張するものである。

要約

この論文は、一見すると難しそうな「数学の木の形」について書かれたものですが、実は**「同じ形をした木を数える方法」と「木をランダムに選んだとき、その形がどうなるか」**という、とても直感的なテーマを扱っています。

著者のベンディクト・シュフラーさんは、複雑な計算を使わずに、**「確率（サイコロを振るような感覚）」**を使って、昔から知られていた有名な公式を新しく証明し、さらに驚くべき発見をしました。

以下に、専門用語を排して、日常の例え話で解説します。

---

1. 物語の舞台：「名前のない木」と「名前のある木」

まず、2 種類の「木」について考えましょう。

• 名前のある木（ラベル付き木）：
  木に「1 番、2 番、3 番…」と名前（シール）が貼ってある状態です。

  • 例え： 家族写真。誰が誰かはっきりしています。「兄が左、弟が右」なら、それは「兄が右、弟が左」とは別の写真です。
  • 数え方は簡単で、有名な「ケイリーの定理」を使えば、木の数は一気に計算できます。

• 名前のない木（ラベルなし木・フリー木）：
  木に名前が貼っていません。ただの「形」だけを見ている状態です。

  • 例え： 抽象画や、シルエットだけ。
  • 重要なポイント： 「名前のある木」をいくつか集めて、名前を剥がして形だけ見ると、同じ形になるものがいくつもあります。
  • 逆に、「名前のない木」1 本に対して、それを「名前のある木」にする方法が、木によって何通りも違うことがあります（図 1 のように、枝のバランスが偏っている木は、名前を貼るパターンが少ないのです）。

昔の数学者オッターさんは、「名前のない木」の数が、木が大きくなるにつれてどう増えるかという**「おおよその公式」**を見つけました。しかし、その証明は非常に難しい数学（解析学）を使っていたのです。

2. この論文のすごいところ：「確率」で証明する

シュフラーさんは、難しい計算ではなく、**「ランダムに木を選んでみる」**というアプローチで、オッターさんの公式を証明し直しました。

• 新しい証明：
  「名前のある木（ポリアの木）」をランダムに選んで、名前を剥がして「名前のない木」に変えてみます。すると、不思議なことに、「名前のない木」をランダムに選んだときと、ほとんど同じ分布（形）になることが分かりました。

  これまで、名前のある木から名前のない木へ情報を移すのは、非常に面倒な「修正（補正）」が必要だと思われていました。しかし、シュフラーさんは**「実は、名前を剥がすだけで、ほぼ完璧に同じものになる」**と証明しました。

3. 核心となる発見：「少しだけ小さくすれば、同じ！」

これがこの論文の最大のハッピースポットです。

• 従来の考え方：
  「名前のある木」を「名前のない木」に近づけたいなら、**「根（幹の一番下）に、小さな木をいくつかくっつけて、全体のサイズを調整する」**という、少し複雑な操作が必要だと言われていました。
  （例：本物の木に、小さな盆栽を根元に置いたようなイメージ）

• シュフラーさんの発見（定理 1.2）：
  「そんな面倒なことはしなくていいよ！」
  名前のある木から、ただ**「根（どの木が根か）を忘れる（名前を剥がす）」だけで、ランダムに選んだ「名前のない木」とほぼ同じ**になります。

  • 例え話：
    巨大な森で、ランダムに木を 1 本選びます。

    1. 方法 A： その木に「根」を指定して、名前を貼った状態（ポリアの木）。
    2. 方法 B： その木から「根」の情報を消して、ただの「形」として見る（フリーの木）。

    以前は、「方法 A の木を、方法 B の木に近づけるには、根の周りを少しいじらないとダメだ」と思われていました。
    しかし、シュフラーさんは**「方法 A の木から、ただ根の情報を消すだけで、方法 B の木と見分けがつかなくなる（確率的に等しくなる）」**と示しました。

  • なぜこれがすごいのか？
    これまで「名前のある木」で証明できたこと（例えば、木の高さの平均や、枝の広がり方など）を、「名前のない木」にもそのまま適用できることを意味します。面倒な「修正作業」が不要になり、数学的な世界がぐっとシンプルになったのです。

4. さらに広がる世界：木以外の「木のようなグラフ」

この発見は、単なる「木」だけでなく、**「木に似た構造を持つ他の図形（グラフ）」**にも適用できます。

• 例え： 木は枝分かれしていますが、少し枝が絡み合っても、全体として「木のような形」をしていれば、この「名前を剥がすだけで同じになる」という法則が成り立ちます。
• これにより、平面に描ける複雑な図形（平面グラフ）など、これまで解けなかった問題への新しい道が開けました。

まとめ

この論文は、以下のようなことを伝えています。

1. 「名前のある木」と「名前のない木」は、実は非常に近い関係にある。
2. 昔から知られていた「木の数え方の公式」を、**「確率（ランダムさ）」**という新しいレンズを使ってシンプルに証明した。
3. 最も重要な発見は、**「名前のある木から根の情報を消すだけで、名前のない木とほぼ同じになる」**という、驚くほどシンプルで強力な事実だった。
4. これにより、複雑な数学的な計算を省き、より多くの種類の「木のような形」を研究できるようになった。

一言で言えば：
「木を数える難問を、**『ランダムに選んで、根を忘れる』**というシンプルな操作で解決し、数学の世界を少しだけシンプルで美しいものにした論文」です。

技術概要

ベンディクト・シュフラー（Benedikt Stufler）による論文「非同型な木の確率的列挙と同等性（Probabilistic enumeration and equivalence of nonisomorphic trees）」の技術的な要約を以下に記します。

1. 研究の背景と問題設定

背景:

• ラベル付き木とラベルなし木: ケイリー（Cayley）の定理により、$n$ 個の頂点を持つラベル付き木の数は $n^{n-2}$ で与えられます。しかし、同型（isomorphism）を考慮した「ラベルなし木（非同型木）」の列挙ははるかに困難です。
• 2 種類の木: ラベルなし木には、根を持たない「自由木（free trees, $f_n$）」と、根を持つ「ポリア木（Pólya trees, $a_n$）」の 2 種類があります。
• 既存の理論: オッター（Otter, 1948）は、ポリア木と自由木の漸近式を導出しました。
  • ポリア木: $a_n \sim c_A n^{-3/2} \rho^{-n}$
  • 自由木: $f_n \sim c_F n^{-5/2} \rho^{-n}$
  • ここで $\rho \approx 0.338$ は生成関数の特異点です。
• 既存手法の限界: これまでの証明は、解析的組合せ論（特異点解析）や「非対称方程式（dissymmetry equation）」に依存していました。また、ランダムなポリア木からランダムな自由木への性質の転送（transfer）については、従来の手法では「中心から少し離れた部分木を付加する」といった複雑な近似定理（Stufler, 2019）しか得られていませんでした。

問題:

1. オッターの漸近公式に対する、新しい確率的証明の構築。
2. ランダムなポリア木とランダムな自由木が、頂点数 $n \to \infty$ で**統計的に同等（asymptotically equivalent）**であることを示し、より単純かつ強力な近似定理を確立すること。
3. このアプローチを、次数制限付きの木や、木のようなグラフクラス（サブクリティカルクラス）へ拡張すること。

---

2. 手法とアプローチ

本論文の核心は、対称性（symmetry）と固定点（fixed points）の確率的な振る舞いを利用した新しいアプローチにあります。

主要な手法:

• 対称性の列挙: $n$ 個の頂点集合上の対称群 $S_n$ が木集合に作用します。軌道（orbit）が非同型木に対応します。
• 対称性の分解: 対称性 $(T, \sigma)$ を、$\sigma$ の固定点の数を $k$ として分類します。特に、固定点が 0 個の対称性（Sym0）と、少なくとも 1 つの固定点を持つ対称性を区別します。
• 生成関数と確率変数:
  • 対称性の指数生成関数 $Sym(U)(z)$ は自由木の生成関数 $F(z)$ と一致します。
  • 固定点の数を $k$ とする対称性の集合に対応する生成関数を解析し、それを確率変数の和 $S_N$（$N$ はある確率変数、$X_i$ は i.i.d.）の分布として解釈します。
• 局所極限定理の適用: ブロズネル（Bloznelis）やヒルバーディンク（Hilberdink）の定理を用いて、$S_N = n$ となる確率の漸近挙動を評価します。
• 中偏差不等式（Medium Deviation Inequality）: 固定点の数がその期待値から $n^\alpha$ ($1/2 < \alpha < 1$) 以上逸脱する確率が指数関数的に小さいことを示します。

---

3. 主要な結果と貢献

3.1 オッターの公式の新しい確率的証明（定理 1.1）

• 従来の「非対称方程式」を用いない、純粋に確率論的な手法で、オッターの漸近公式（$f_n \sim c_F n^{-5/2} \rho^{-n}$）を再証明しました。
• 定数 $c_F$ を、特定の確率変数 $X$ の期待値 $E[X]$ を用いて $c_F = \frac{1}{\sqrt{2\pi} E[X]^{3/2}}$ として明示的に導出しました。

3.2 ポリア木と自由木の漸近的同等性（定理 1.2）

• 最も重要な貢献: ランダムなポリア木 $A_n$ の根を忘れた木 $F(A_n)$ と、ランダムな自由木 $F_n$ の間の全変動距離（Total Variation Distance）が $n \to \infty$ で 0 に収束することを証明しました。
  $$\lim_{n \to \infty} d_{TV}(F(A_n), F_n) = 0$$
• より精密な評価として、任意の集合 $E$ に対して以下の不等式が成り立つことを示しました（$1/2 < \alpha < 1$）：
  $$|P(F(A_n) \in E) - P(F_n \in E)| \le \exp(-c n^{2\alpha-1}) + P(F(A_n) \in E) C n^{\alpha-1}$$
• 意義: これにより、以前必要だった「ランダムな自由木は、少し小さいポリア木に小さな木を根に付けたもの」という複雑な近似（$n - O_p(1)$ 構造）は不要であり、単に根を忘れたポリア木そのものが自由木と統計的に区別できないことが示されました。これにより、ポリア木で証明された確率過程の収束性や中心極限定理が、自由木へ直接転送可能になります。

3.3 拡張結果（セクション 3）

• 次数制限付きの木（Proposition 3.1）: 頂点の次数を特定の集合 $\Omega$ に制限した場合でも、適切に定義されたポリア木（根の次数を $\Omega$ に、他の頂点を $\Omega^*$ に制限）と自由木は漸近的に同等であることを示しました。
• 木のようなグラフクラス（サブクリティカルクラス, Proposition 3.2）: 木のような振る舞いをする非ラベル付きグラフのクラス（サブクリティカルクラス）に対しても、同様の漸近的同等性が成り立つことを証明しました。これは、ブロック安定なグラフクラスにおける根付きグラフと非根付きグラフの関係にも適用されます。

---

4. 結論と学術的意義

• 手法の革新性: 解析的組合せ論の複雑な特異点解析や非対称方程式に依存せず、対称性の確率的構造と局所極限定理を用いることで、木の数え上げと分布の同等性をより直感的かつ強力に扱えることを示しました。
• 理論的統合: ランダムなポリア木とランダムな自由木が「本質的に同じ」であるという事実を明確化し、両者の間の転送定理を大幅に簡素化しました。これにより、自由木の構造（ブラウン木への収束など）の研究が、より扱いやすいポリア木の研究に帰着できるようになります。
• 将来への展望: このアプローチは、平面グラフ（planar graphs）など、より複雑な非ラベル付き構造の漸近列挙や、そのランダムな形状の解析に応用可能な汎用性を持っています。特に、未解決問題であった平面グラフの非同型な数の漸近挙動への道筋を開く可能性があります。

総じて、本論文は離散数学と理論計算機科学における非ラベル付き構造の列挙理論において、確率的な視点から重要な進展をもたらした研究です。