地下で根を張った後、一本の茎が地上に出ると、ある接点から必ず２つに分かれ、その端
点はそのまま枝を伸ばしていくか、もしくは花を付ける。もちろん２つとも花を付けてもよいが、
その場合はその枝はそれ以上伸びることはない。新しく伸びた枝はある点でまた必ず２つに
分かれ、同様に端点で枝か花になる。
全部で花が１０個咲いたという育ち方をする種は何通りあるか？なお、花の付き方が異な
るものは異なる種と分類するものとする。
ａｔ さんからのコメントです。（平成２８年４月２７日付け）
内点の数がちょうど9個であるような2分木の総数をもとめればよいので、
(1/10)*comb(18,9)=4862 (答) （→ 参考：「A000108」）
一般に、花の数がちょうど (n+1) 個であるような、この植物の種の総数が b(n) 個あるとし、
B(z)=Σ[n=0〜∞]b(n)*z^n とします。
B(z)は、漸化式：B(z)=1+z*(B(z))^2. を満たすことが分かります。
このB(z)についての2次方程式を解いて、B(z)=(1-√(1-4*z))/(2*z)
よって、 b(z)=(1/(n+1))*comb(2*n,n).
（参考） 「Analytic Combinatorics」の67頁に詳細があります。
ＧＡＩ さんからのコメントです。（平成２８年４月２７日付け）
私の説明が悪かったのか、こちらが意図したものと異なる解釈になってしまいました。
花の個数が2個なら1種
○ ○
|___|
|
3個なら1種
○ ○
|___|
○ ｜
|____|
|
4個なら2種
○ ○ ○ ○
|___| |___|
|______|
|
または
○ ○
|___|
○ ｜
|___|
○ |
|___|
|
5個なら3種（図省略）
のような形態を考えてもらいたくて出題していました。カタラン数では対応しないことになりま
す。
ａｔ さんからのコメントです。（平成２８年４月２７日付け）
なるほど、そうでしたか。そうすると答えは 98通り になりますでしょうか。
花の数がちょうどn個であるようなこの植物の種の総数がb(n)個あるとし、さらにb(1)=1とし
ます。次のような漸化式が成り立ちます。
b(2*n-1)=Σ[k=1〜n-1]b(k)*b(2*n-k-1)，
b(2*n)=Σ[k=1〜n-1]b(k)*b(2*n-k) + comb(b(n)+1,2).
これを使って計算すると、
b(1)=1,
b(2)=comb(b(1)+1,2)=1,
b(3)=b(1)*b(2)=1,
b(4)=b(1)*b(3)+comb(b(2)+1,2)=2,
b(5)=b(1)*b(4)+b(2)*b(3)=3,
b(6)=b(1)*b(5)+b(2)*b(4)+comb(b(3)+1,2)=6,
b(7)=b(1)*b(6)+b(2)*b(5)+b(3)*b(4)=11,
b(8)=b(1)*b(7)+b(2)*b(6)+b(3)*b(5)+comb(b(4)+1,2)=23,
b(9)=b(1)*b(8)+b(2)*b(7)+b(3)*b(6)+b(4)*b(5)=46,
b(10)=b(1)*b(9)+b(2)*b(8)+b(3)*b(7)+b(4)*b(6)+comb(b(5)+1,2)=98
突然変異種分類として、ＧＡＩ さんからの出題です。（平成２８年４月２８日付け）
更にある一群の植物は進化の過程で気まぐれな性質を身につけており、遺伝子が次のよ
うな指令を出していることが分かった。
地下で根を張った後、一本の茎が地上に出るとある接点から２つ、または３つに分かれ、
その端点はそのまま枝を伸ばしていくか、もしくは花を付ける。もちろん枝先全部に花を付け
てもよいが、その場合はその枝はそれ以上伸びることはない。新しく伸びた枝はある点でま
た必ず２つ、または３つに分かれ、同様に端点で枝か花になる。
全部で花が５個、１０個咲いたという育ち方をする種はそれぞれ何通りあるか？なお、花の
付き方が異なるものは異なる種と分類するものとする。
ａｔ さんからのコメントです。（平成２８年４月２８日付け）
数列「A268172」で合っていますでしょうか？
花がちょうどn個のものの総数が h(n) 個だけあるとし、さらに、
h(1)=1 、H(z)=Σ[n=1〜∞]h(n)*z^n
とすると、
H(z)=z+(1/2)*(H(z))^2+(1/2)*H(z^2)+(1/6)*(H(z))^3+(1/2)*H(z)*H(z^2)+(1/3)*H(z^3)
が成り立ちます。これを使えば、各h(n)の値が計算できます。（→ h(5)=9, h(10)=1194）
ＧＡＩ さんからのコメントです。（平成２８年４月２８日付け）
凄い関係式ですね。正解です。具体的に、h(5)=9 を作ってみるのも面白かったです。なか
なか９個にならなかった。
