お風呂や夜寝る前は、子供達（兄弟２人）といろんな話をしたりします．
今日もお風呂でこんな話をしていました。
私 「今度、〇〇君のところとかと一緒にご飯食べに行くんだよ。」
「確か、その子の下の子２人は双子だって聞いたけど。」
下の子（以下(下)） 「うんそうだよ。似ててどっちか区別がつかないんだよ。」
私 「それは一卵性の双子だねー。」
子供達 「・・・」
私 「双子は２種類あるって知ってる？一卵性と二卵性。」
子供達 「ううん。知らない。」
私 「子供は最初、こんなちっさな卵から始まって、それがどんどん分裂して細胞が増えていくことで人間ができるんだけど。」
子供達 「うん。」
私 「一卵性の双子っていうのは、最初、卵が一つで、それが２つになって、それがそれぞれ分裂して、分裂したものがそれぞれ成長して２人ができるんだよ。で、二卵性は・・・」
と言いかけたところで、(下)が、
(下) 「最初から２つの卵で、それぞれが・・・・ってこと？」
と言いました。とても勘が鋭いようです。
私 「そうそう、最初から卵が２つあるわけね。で、それぞれが分裂して、人間が２人できるってわけ。」
さらに続けて、
私 「だから、一卵性は全く同じ人間が２人できることになるんだよ。」
子供達 「でも、兄弟で喧嘩もするんだよ。今日、児童館で(誰々)と(誰々)が兄弟で喧嘩してた。」
私 「そうなんだ。似過ぎてて兄弟で喧嘩になることもあるよね。」
話しているうちに双子ではなくて普通の兄弟の話になってしまいました。
とりあえず、子供達は、双子の仕組みがすぐにわかったようでした。他にも、
私 「DNAって知ってる？」
と聞いてみました。私も生物専攻ではありませんでしたので、DNAを小学生にどうやって説明したら良いか頭の中でよくよく考えながら聞きました。
(下) 「んー、どこかで聞いたことあるような？」
私 「DNAっていうのは、その ... その人間の作り方が書いてある説明書みたいなものだよ。細胞の中に、その詳しい説明書が書いてあって、それを読むと、この人の手はこうやって作りなさい、とか、髪の毛はこんな感じにしなさい、とか爪はこんな形でお願いしますとか書いてある。で、一卵性の双子は最初の卵が一つだけだから、２人の説明書には同じことが書いてある。だからまったく同じ人間が作れるんだよ。でも、・・・」
２人の兄弟を指して、
私 「君たち２人は、説明書がほんのちょっとだけ違うんだ。(下)のDNAには(下)の髪の毛を作りなさいと書いてあって(上)のDNAには(上)の髪の毛を作りなさいと書いてある、(上)の頭に(下)の髪の毛が生えてきたりはしないんだ。」
子供達 「ふーん」
(下) 「DNAって目で読めるの？」
と聞いてくるので、DNAも顕微鏡で見ようとすれば見れること(本当は、光学顕微鏡では見えなくて、電子顕微鏡でもわずかにしか見えません．またX線回析を行うことでようやくその構造が見えるらしい)、他にもDNAの形が2重螺旋の形をしていることをワトソンとクリックが突き止めてノーベル賞を取ったこと、そのような話は分子生物学と言って、生物学の発見は、新種の虫を発見するだけではないことなど話しました。
一卵性の双子は全く同じ説明書だから、性別も同じであることなど。二卵性は性別が違うこともあるなどの話もしました。
そしてお風呂からみんな上がった後、私も、数学者らしく、
私 「双子は２種類あったけど、三つ子は何種類いるかわかる？」
と一般の $n$ つ子に拡張するような話にしてみました。すると、
(下) 「３つ」
とすぐに答えました。下の子は、なんだか直感で答えることが多いようです。そして上の子は実に慎重派で、じっくり考えることが多いです。
(下) 「だって、一つの卵がばぁって分かれて３つになる場合と、１つが２つになってもう１つがそのままの。で３つの卵の場合。」
瞬時に答えた割に、完全に場合分けができていました。そして、
私 「じゃあ四つ子の場合は？」
やっぱりすぐさま、
(下) 「４つじゃないの？」
と言いました。 $n$ つ子の種類は $n$ 個という規則があると思ったでしょうか？
そして(上)も参戦してきました。
(上) 「２つが2,2にわかれる場合と、3,1にわかれる場合があるよ。でも、四つ子や五つ子ってあるの？」
私 「最初が1つの卵の場合はそれが4つになる場合で一通り、最初が卵2つの場合は2,2と3,1の場合があるから二通り。最初が３つの場合は、どれか一つの卵が２つになる場合で一通り。最初が４つの場合は一通り、結局全部で5通り。四つ子や五つ子もごく稀にいるよ。日本でも昔五つ子ちゃんが有名になった例があるよ。」
そして、その後、話は双子とは全く違う有名人の話になったりしました．
ここから少しだけ数学の話。
一般に $n$ つ子の生まれ方の数は？
一般に $n$ つ子の生まれ方は上記の意味で何種類あるのか？
何通りあるか子供達に教えながら、分割数のことを考えていました。
分割数 $p(n)$ とは、自然数 $n$ を自然数の和で書く書き方の数として定義されます．つまり、
$n=3$ ならば、$3$ の和としての書き方は、$1+1+1$、$2+1$、$3$ の三種類なので、
$$p(3)=3$$
となります．
$n=4$ ならば、$4$ の和としての書き方は、$1+1+1+1$、$2+1+1$、$2+2$、$3+1$、$4$ の五種類なので、
$$p(4)=5$$
となります．
これは、ぴったり、 $n$ つ子が生まれるパターンの数と一致します．
つまり、一つ一つの和の成分数が、最初の卵の数と考えるのです．
$n=4$ では、$1+1+1+1$ は、四卵性
$2+1+1$ は、三卵性
$p(1)=1$, $p(2)=2$, $p(3)=3$ ときて、この数列が等差数列かと思い $p(4)$ が $4$ かと思ったら、$p(4)=5$ となります．
二卵性の異なるパターンが２種類あってその分1つ増えると考えることもできるでしょうか．
ただ、この方法で行っても、
$p(5)=7$, $p(6)=11$, $p(7)=15$, $p(8)=22$, $p(9)=30$
とどんどん増えていくので、最初の等差数列からはかなり離れていきます．一般に、分割数を忠実に計算する$n$ に関する公式は知られていません．もちろん、どんなに大きい分割数も、真面目に、$n$ が小さい方から計算していけば、いずれ計算できます．
分割数の計算の仕方なんてあるのか？と思うかもしれませんが、
有名なのは、母関数として
$$\sum_{n=0}^\infty p(n)x^n=\prod_{k=1}^\infty\frac{1}{1-x^k}$$
という綺麗な関係式が知られています．ここでは、$p(0)=1$ と定義しています．
この式は、さらにこの恒等式から派生して分割数に付随する他の数列に対しても同じような恒等式が存在します．
分割数はそのものは整数論や組み合わせ論においても現在でも活発に研究されており、多くの研究成果があります．分割数に関するまとまった文献は下の参考文献(1.) をみよ．
前期の線形代数続論演習でもやったように、$n$ 次のべき零行列の線形変換としての分類(ジョルダン標準形のタイプの数)はまさにヤング図形、つまり分割数 $p(n)$ の分だけ存在していました．
分割数は、定義は簡単ですが、その性質は、まったく奥深いものです．
あのラマヌジャンも分割数に関する研究をしています．
卵が分裂して $n$ つ子ができる過程の数を数えたら？
次は、分割数から派生して、卵が分裂して新しく幾つかの卵ができるまでの過程のパターン数も数えてみようと思いました．ここでは、分裂とは、一つの卵が幾つかの卵に分けられて独立な個体となることをいうことにします．とりあえず、簡単のため一卵性の $n$ つ子のでき方の場合だけ考えます．
どういうことかというと、
1個の卵が、いきなり、幾つかに分裂するのではなく、一つの卵は一度に2分裂までしか別れないとルールを決めておきます．その分裂が順を追って幾つかの卵になるとします．また、卵一つ一つには、まだ個性はないとして、対称的な分裂は無視します．また、異なる卵が次の段階でそれぞれ二分裂する早さは気にしないことにします．どちらが早くても同じ分裂とするのです．
そうすると、例えば一卵性の四つ子の分裂の過程は、
$$(1)\to (1+1)=((1)+1)\to ((1+1)+1)= (((1)+1)+1)\to (((1+1)+1)+1)=4$$
となるパターンと
$$(1)\to (1+1)=((1)+1)\to ((1+1)+1)=((1+1)+(1))\to ((1+1)+(1+1))=4$$
((1+(1+1))+1) は、 (((1+1)+1)+1) と同じ分裂パターンとなります．
もちろん、(1+(1+(1+1))) や (1+((1+1)+1)) も同じ分裂パターンとみなします．それらは、並べ方が違うだけで、それらの卵を空間において眺めたら分裂の仕方として区別がつかないからです．
それが、対称なものを無視するという意味です．
つまり、上の式で言えば、一般に自然数 $n$ を幾つかの 1 の和で書いたとき、交換法則で得られるものは無視したものと考えても良いでしょう．
交換法則で得られたものを無視しないで数えたものをカタラン数(リンク)と言います．
つまり、カタラン数とは、かっこのつけ方をすべて数えるということになります．
カタラン数は、古くからよく知られ、これも数学の様々な場面に現れます．
今数えたいものは、かっこの付け替えを無視し、グラフとして同じものは同じとみなしたものです．
しかし、ある組み合わせ的対象の数え上げにおいて、情報を落としたもの数えるからといって決して数えやすくなるわけではありません．
また、グラフ理論で言えば、リーフ(leaf)の数が丁度 $n$ である、全二分木(full binary tree)
の同相類（各リーフにはorderが付いていない）といえばよいでしょうか？上の２つの分裂のパターンをbinary tree で描くと下のようになります．
一番先にある4つのノードが四つ子に対応します．一つ一つのノードは、その瞬間の卵だと思えます．
ここで binary tree の用語説明
そもそも tree とは、ある一つの root から生える閉路のないグラフのことで、一つのノードから辺(edge )が下に伸びていくとします．ノードの各段階をレベル(level)といい、あるノードからひとつの辺によって連結されるノードを子(child)と言います．子のいないノードのことをリーフ(leaf)と言います．二分木(binary tree) とは、各ノードの子が2つ以下のものを言います．また、全二分木(full binary tree)とは、各ノードの子は0個か2個のどちらかのものを言います．
なので、rootをもつfull binary treeは、頂点として１、２、３価のものしかなく、１価の頂点はリーフであり、２価の頂点はただ１つのrootであり、それ以外はすべて３価の頂点ということになります．まとめれば、ここでやっていることは、連結な１, ２, ３価グラフのうち、ただ一つの２価頂点を持つものを、１価頂点の数でまとめて数え上げるということです．
リーフの数が $n$ であるようなfull binary tree のグラフ(同相類,unordered と言っても良い)を分裂グラフということにします．一卵性五つ子の分裂グラフは下の３つになります．
リーフの数が $n$ の分裂グラフの数を $a(n)$ と定義して実験してみると、
$a(1)=1,a(2)=1,a(3)=1,a(4)=2,a(5)=3,a(6)=6$ まで計算をすることができました．
この数列は簡単に定義できるのできっと知られていると思い、数列百科事典(リンク)で調べながら検索することにしました．
この数列百科事典は望みの整数列を見つけるのにとても便利です．
$n=7,8$ の場合も紙にグラフを全て書いてみました．
$a(7)$ は $10$ 個あり, $a(11)$ は $20$ であることがわかりました．
ただ、逐一このような素朴な書き出し法で書き出していっても、この計算が本当に合っているのか不安だし、このまま続けていって規則がわからないのでは、少し大きい $a(n)$ を求めるには少々不便です．何か良い $a(n)$ の計算方法はないか？と考えました．
考えてみると、最初の root のノードを取り去ることで、分裂グラフが２つの小さな分裂グラフに分けられることに気がつきました．
つまり、リーフが $n$ のfull binary treeをルートのノードで切ってやると、(リーフの和が $n$ となる)２つのfull binary tree が表れます．つまり、全体のfull binary tree の数は、2つのfull binary tree のそれぞれの組み合わせで計算できるということです．
なので、$a(7)$ を計算するには、$a(6)a(1)+a(5)a(2)+a(4)a(3)$ を計算すれば良いということになります．$n$ が奇数のときは左右でリーフの数が違うのでそれぞれのリーフの数の積がそのパターンの tree のパターンの数ということになります．
よって、改めて $a(7)=11$ が得られました．さっき自分で書き出していた個数は10個でしたので、もう一度書き出したグラフを見直してみると、見落としがあることに気がつきました．
なるほど、これは良い方法を見出したと思い、次に、$n=8$ の場合も、もう一度計算しようとしました．まずは、$a(7)a(1)+a(6)a(2)+a(5)a(3)=20$ まで計算します．左右で4,4の場合を考察は別にしてやると、$a(4)=2$ の場合をそれぞれ A,B としてrootの先にくっつけるてやると、左右の対称性は無視しないといけないので、$(A,A), (B,B), (A,B)$ の3パターンしかないことになります．
なので、 さっきの20に3を足して $a(8)=23$ と正しい答えを得ることができました．
やはり、これも先ほど数えた数は、$20$ でしたので、数え損ないが3もあったことになります．
さらに、奇数の $a(9)$ はさっきの方法で計算して、
機械的に、$a(9)=\sum_{k=1}^4a(k)a(9-k)=46$ と算出されました．ここまでくると、手計算では大変だったでしょうね．さっきの数列百科事典での候補は大分絞られてきました．
この計算方法で次々計算しますと、$a(10)=98$, $a(11)=207$, $a(12)=451$ となりました．
この数列と一致する、百科事典に載っている数列は、もう
今日もお風呂でこんな話をしていました。
私 「今度、〇〇君のところとかと一緒にご飯食べに行くんだよ。」
「確か、その子の下の子２人は双子だって聞いたけど。」
下の子（以下(下)） 「うんそうだよ。似ててどっちか区別がつかないんだよ。」
私 「それは一卵性の双子だねー。」
子供達 「・・・」
私 「双子は２種類あるって知ってる？一卵性と二卵性。」
子供達 「ううん。知らない。」
私 「子供は最初、こんなちっさな卵から始まって、それがどんどん分裂して細胞が増えていくことで人間ができるんだけど。」
子供達 「うん。」
私 「一卵性の双子っていうのは、最初、卵が一つで、それが２つになって、それがそれぞれ分裂して、分裂したものがそれぞれ成長して２人ができるんだよ。で、二卵性は・・・」
と言いかけたところで、(下)が、
(下) 「最初から２つの卵で、それぞれが・・・・ってこと？」
と言いました。とても勘が鋭いようです。
私 「そうそう、最初から卵が２つあるわけね。で、それぞれが分裂して、人間が２人できるってわけ。」
さらに続けて、
私 「だから、一卵性は全く同じ人間が２人できることになるんだよ。」
子供達 「でも、兄弟で喧嘩もするんだよ。今日、児童館で(誰々)と(誰々)が兄弟で喧嘩してた。」
私 「そうなんだ。似過ぎてて兄弟で喧嘩になることもあるよね。」
話しているうちに双子ではなくて普通の兄弟の話になってしまいました。
とりあえず、子供達は、双子の仕組みがすぐにわかったようでした。他にも、
私 「DNAって知ってる？」
と聞いてみました。私も生物専攻ではありませんでしたので、DNAを小学生にどうやって説明したら良いか頭の中でよくよく考えながら聞きました。
(下) 「んー、どこかで聞いたことあるような？」
私 「DNAっていうのは、その ... その人間の作り方が書いてある説明書みたいなものだよ。細胞の中に、その詳しい説明書が書いてあって、それを読むと、この人の手はこうやって作りなさい、とか、髪の毛はこんな感じにしなさい、とか爪はこんな形でお願いしますとか書いてある。で、一卵性の双子は最初の卵が一つだけだから、２人の説明書には同じことが書いてある。だからまったく同じ人間が作れるんだよ。でも、・・・」
２人の兄弟を指して、
私 「君たち２人は、説明書がほんのちょっとだけ違うんだ。(下)のDNAには(下)の髪の毛を作りなさいと書いてあって(上)のDNAには(上)の髪の毛を作りなさいと書いてある、(上)の頭に(下)の髪の毛が生えてきたりはしないんだ。」
子供達 「ふーん」
(下) 「DNAって目で読めるの？」
と聞いてくるので、DNAも顕微鏡で見ようとすれば見れること(本当は、光学顕微鏡では見えなくて、電子顕微鏡でもわずかにしか見えません．またX線回析を行うことでようやくその構造が見えるらしい)、他にもDNAの形が2重螺旋の形をしていることをワトソンとクリックが突き止めてノーベル賞を取ったこと、そのような話は分子生物学と言って、生物学の発見は、新種の虫を発見するだけではないことなど話しました。
一卵性の双子は全く同じ説明書だから、性別も同じであることなど。二卵性は性別が違うこともあるなどの話もしました。
そしてお風呂からみんな上がった後、私も、数学者らしく、
私 「双子は２種類あったけど、三つ子は何種類いるかわかる？」
と一般の $n$ つ子に拡張するような話にしてみました。すると、
(下) 「３つ」
とすぐに答えました。下の子は、なんだか直感で答えることが多いようです。そして上の子は実に慎重派で、じっくり考えることが多いです。
(下) 「だって、一つの卵がばぁって分かれて３つになる場合と、１つが２つになってもう１つがそのままの。で３つの卵の場合。」
瞬時に答えた割に、完全に場合分けができていました。そして、
私 「じゃあ四つ子の場合は？」
やっぱりすぐさま、
(下) 「４つじゃないの？」
と言いました。 $n$ つ子の種類は $n$ 個という規則があると思ったでしょうか？
そして(上)も参戦してきました。
(上) 「２つが2,2にわかれる場合と、3,1にわかれる場合があるよ。でも、四つ子や五つ子ってあるの？」
私 「最初が1つの卵の場合はそれが4つになる場合で一通り、最初が卵2つの場合は2,2と3,1の場合があるから二通り。最初が３つの場合は、どれか一つの卵が２つになる場合で一通り。最初が４つの場合は一通り、結局全部で5通り。四つ子や五つ子もごく稀にいるよ。日本でも昔五つ子ちゃんが有名になった例があるよ。」
そして、その後、話は双子とは全く違う有名人の話になったりしました．
ここから少しだけ数学の話。
一般に $n$ つ子の生まれ方の数は？
一般に $n$ つ子の生まれ方は上記の意味で何種類あるのか？
何通りあるか子供達に教えながら、分割数のことを考えていました。
分割数 $p(n)$ とは、自然数 $n$ を自然数の和で書く書き方の数として定義されます．つまり、
$n=3$ ならば、$3$ の和としての書き方は、$1+1+1$、$2+1$、$3$ の三種類なので、
$$p(3)=3$$
となります．
$n=4$ ならば、$4$ の和としての書き方は、$1+1+1+1$、$2+1+1$、$2+2$、$3+1$、$4$ の五種類なので、
$$p(4)=5$$
となります．
これは、ぴったり、 $n$ つ子が生まれるパターンの数と一致します．
つまり、一つ一つの和の成分数が、最初の卵の数と考えるのです．
$n=4$ では、$1+1+1+1$ は、四卵性
$2+1+1$ は、三卵性
$3+1$, $2+2$ は、二卵性
$4$ は一卵性
$p(1)=1$, $p(2)=2$, $p(3)=3$ ときて、この数列が等差数列かと思い $p(4)$ が $4$ かと思ったら、$p(4)=5$ となります．
二卵性の異なるパターンが２種類あってその分1つ増えると考えることもできるでしょうか．
ただ、この方法で行っても、
$p(5)=7$, $p(6)=11$, $p(7)=15$, $p(8)=22$, $p(9)=30$
とどんどん増えていくので、最初の等差数列からはかなり離れていきます．一般に、分割数を忠実に計算する$n$ に関する公式は知られていません．もちろん、どんなに大きい分割数も、真面目に、$n$ が小さい方から計算していけば、いずれ計算できます．
分割数の計算の仕方なんてあるのか？と思うかもしれませんが、
有名なのは、母関数として
$$\sum_{n=0}^\infty p(n)x^n=\prod_{k=1}^\infty\frac{1}{1-x^k}$$
という綺麗な関係式が知られています．ここでは、$p(0)=1$ と定義しています．
この式は、さらにこの恒等式から派生して分割数に付随する他の数列に対しても同じような恒等式が存在します．
分割数はそのものは整数論や組み合わせ論においても現在でも活発に研究されており、多くの研究成果があります．分割数に関するまとまった文献は下の参考文献(1.) をみよ．
前期の線形代数続論演習でもやったように、$n$ 次のべき零行列の線形変換としての分類(ジョルダン標準形のタイプの数)はまさにヤング図形、つまり分割数 $p(n)$ の分だけ存在していました．
分割数は、定義は簡単ですが、その性質は、まったく奥深いものです．
あのラマヌジャンも分割数に関する研究をしています．
卵が分裂して $n$ つ子ができる過程の数を数えたら？
次は、分割数から派生して、卵が分裂して新しく幾つかの卵ができるまでの過程のパターン数も数えてみようと思いました．ここでは、分裂とは、一つの卵が幾つかの卵に分けられて独立な個体となることをいうことにします．とりあえず、簡単のため一卵性の $n$ つ子のでき方の場合だけ考えます．
1個の卵が、いきなり、幾つかに分裂するのではなく、一つの卵は一度に2分裂までしか別れないとルールを決めておきます．その分裂が順を追って幾つかの卵になるとします．また、卵一つ一つには、まだ個性はないとして、対称的な分裂は無視します．また、異なる卵が次の段階でそれぞれ二分裂する早さは気にしないことにします．どちらが早くても同じ分裂とするのです．
そうすると、例えば一卵性の四つ子の分裂の過程は、
$$(1)\to (1+1)=((1)+1)\to ((1+1)+1)= (((1)+1)+1)\to (((1+1)+1)+1)=4$$
となるパターンと
$$(1)\to (1+1)=((1)+1)\to ((1+1)+1)=((1+1)+(1))\to ((1+1)+(1+1))=4$$
となるパターンの2つということになります．
つまり、一卵性四つ子の作り方として、1 の足し算の仕方の数と言っても良いし、別の観点からはトーナメント表の書き方の数と言っても良いわけです．しかし、上のルールから、
((1+(1+1))+1) は、 (((1+1)+1)+1) と同じ分裂パターンとなります．
もちろん、(1+(1+(1+1))) や (1+((1+1)+1)) も同じ分裂パターンとみなします．それらは、並べ方が違うだけで、それらの卵を空間において眺めたら分裂の仕方として区別がつかないからです．
それが、対称なものを無視するという意味です．
つまり、上の式で言えば、一般に自然数 $n$ を幾つかの 1 の和で書いたとき、交換法則で得られるものは無視したものと考えても良いでしょう．
交換法則で得られたものを無視しないで数えたものをカタラン数(リンク)と言います．
つまり、カタラン数とは、かっこのつけ方をすべて数えるということになります．
カタラン数は、古くからよく知られ、これも数学の様々な場面に現れます．
今数えたいものは、かっこの付け替えを無視し、グラフとして同じものは同じとみなしたものです．
しかし、ある組み合わせ的対象の数え上げにおいて、情報を落としたもの数えるからといって決して数えやすくなるわけではありません．
また、グラフ理論で言えば、リーフ(leaf)の数が丁度 $n$ である、全二分木(full binary tree)
の同相類（各リーフにはorderが付いていない）といえばよいでしょうか？上の２つの分裂のパターンをbinary tree で描くと下のようになります．
ここで binary tree の用語説明
そもそも tree とは、ある一つの root から生える閉路のないグラフのことで、一つのノードから辺(edge )が下に伸びていくとします．ノードの各段階をレベル(level)といい、あるノードからひとつの辺によって連結されるノードを子(child)と言います．子のいないノードのことをリーフ(leaf)と言います．二分木(binary tree) とは、各ノードの子が2つ以下のものを言います．また、全二分木(full binary tree)とは、各ノードの子は0個か2個のどちらかのものを言います．
なので、rootをもつfull binary treeは、頂点として１、２、３価のものしかなく、１価の頂点はリーフであり、２価の頂点はただ１つのrootであり、それ以外はすべて３価の頂点ということになります．まとめれば、ここでやっていることは、連結な１, ２, ３価グラフのうち、ただ一つの２価頂点を持つものを、１価頂点の数でまとめて数え上げるということです．
リーフの数が $n$ であるようなfull binary tree のグラフ(同相類,unordered と言っても良い)を分裂グラフということにします．一卵性五つ子の分裂グラフは下の３つになります．
$a(1)=1,a(2)=1,a(3)=1,a(4)=2,a(5)=3,a(6)=6$ まで計算をすることができました．
この数列は簡単に定義できるのできっと知られていると思い、数列百科事典(リンク)で調べながら検索することにしました．
この数列百科事典は望みの整数列を見つけるのにとても便利です．
$n=7,8$ の場合も紙にグラフを全て書いてみました．
$a(7)$ は $10$ 個あり, $a(11)$ は $20$ であることがわかりました．
ただ、逐一このような素朴な書き出し法で書き出していっても、この計算が本当に合っているのか不安だし、このまま続けていって規則がわからないのでは、少し大きい $a(n)$ を求めるには少々不便です．何か良い $a(n)$ の計算方法はないか？と考えました．
考えてみると、最初の root のノードを取り去ることで、分裂グラフが２つの小さな分裂グラフに分けられることに気がつきました．
つまり、リーフが $n$ のfull binary treeをルートのノードで切ってやると、(リーフの和が $n$ となる)２つのfull binary tree が表れます．つまり、全体のfull binary tree の数は、2つのfull binary tree のそれぞれの組み合わせで計算できるということです．
なので、$a(7)$ を計算するには、$a(6)a(1)+a(5)a(2)+a(4)a(3)$ を計算すれば良いということになります．$n$ が奇数のときは左右でリーフの数が違うのでそれぞれのリーフの数の積がそのパターンの tree のパターンの数ということになります．
よって、改めて $a(7)=11$ が得られました．さっき自分で書き出していた個数は10個でしたので、もう一度書き出したグラフを見直してみると、見落としがあることに気がつきました．
なるほど、これは良い方法を見出したと思い、次に、$n=8$ の場合も、もう一度計算しようとしました．まずは、$a(7)a(1)+a(6)a(2)+a(5)a(3)=20$ まで計算します．左右で4,4の場合を考察は別にしてやると、$a(4)=2$ の場合をそれぞれ A,B としてrootの先にくっつけるてやると、左右の対称性は無視しないといけないので、$(A,A), (B,B), (A,B)$ の3パターンしかないことになります．
なので、 さっきの20に3を足して $a(8)=23$ と正しい答えを得ることができました．
やはり、これも先ほど数えた数は、$20$ でしたので、数え損ないが3もあったことになります．
さらに、奇数の $a(9)$ はさっきの方法で計算して、
機械的に、$a(9)=\sum_{k=1}^4a(k)a(9-k)=46$ と算出されました．ここまでくると、手計算では大変だったでしょうね．さっきの数列百科事典での候補は大分絞られてきました．
この計算方法で次々計算しますと、$a(10)=98$, $a(11)=207$, $a(12)=451$ となりました．
この数列と一致する、百科事典に載っている数列は、もう
Wedderburn-Etherington数 (Wedderburn-Etherington numbers)
しかありませんでした．早速wiki(リンク)で調べてみると、果たして思った通りの数列でした．
漸化式も、
$$a(2n-1)=\sum_{k=1}^na(k)a(2n-k-1)$$
$$a(2n)=\frac{a(n)(a(n)+1)}{2}+\sum_{k=1}^{n-1}a(k)a(2n-k)$$
となり、全く同じです．この数は、組み合わせ論や数論では非常によく知られているらしく、性質は、上に述べたようなものでした．
参考文献
- George E. Andrew and Kimmo Eriksson, Integer partitions, Cambridge University Press
0 件のコメント:
コメントを投稿