今回のコラムでは，数列の次の項を予想するという数列のパズルを取り上げたいのですが，まず（その１１）のカタラン数列｛Ｃn｝
｛Ｃn｝＝｛１，２，５，１４，４２，１３２，４２９，１４３０，４８６２，１６７９６，・・・｝
の補足から始めたいと思います．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【１】カタラン数
カタラン数は，凸ｎ角形を対角線で三角形分割する仕方は何通りあるかとか，ｎ対のかみ合い括弧の種類数などいろいろな場面で登場する数なのですが，
Ｃn＝2nＣn／（ｎ＋１）＝（２ｎ）！／ｎ！（ｎ＋１）！，
Ｃn＝2n+1Ｃn／（２ｎ＋１），
あるいは
Ｃn＝2nＣn−2nＣn-1＝１，２，５，１４，４２，・・・
と表されます．
カタラン数から一般項が何かを予想するのは難しいのですが，ここでは
Ｃn＝2nＣn／（ｎ＋１） （Ｃ0＝１）
がわかっているものとして，母関数
Ｆ（ｔ）＝ΣＣnｔ^n
を求めてみます．
この級数は，第０項：Ｃ0＝１から始まるので，そのまま項比をとると
ａn+1ｘn+1/ａnｘn=(n+1/2)(n+1)/(n+2)*4x/(n+1)
したがって，
Ｆ（ｘ）＝2Ｆ1(1/2,1,2,4x)=2/{1+(1-4x)^(1/2)}
＝{1-(1-4x)^(1/2)}/2x
(1-4x)^(1/2)＝Σ(-4)^k1/2Ck･ｘ^k
より
Ｃn＝-1/2(-4)^(n+1)1/2C(n+1)
これをさらに式変形すれば，
Ｃn＝2nＣn／（ｎ＋１）
になる．この結果，二項展開を丹念に使えば
{1-(1-4x)^(1/2)}/2x=Σ2nCnx^n/(n+1)
が得られるはず・・・．
この方法は試してはいないのですが，かなり面倒そうです．実はカタラン数に対しては，漸化式
Ｃn＝ΣＣkＣn-k-1＝Ｃ0Ｃn-1＋Ｃ1Ｃn-2＋・・・＋Ｃn-1Ｃ0
が成り立つので，母関数は
Ｆ（ｔ）＝ΣＣnｔ^n＝ΣＣkｔ^kΣＣn-k-1ｔ^n-k＋１
＝Ｆ（ｔ）・ｔＦ（ｔ）＋１
すなわち，
ｔＦ（ｔ）^2−Ｆ（ｔ）−１＝０
なる２次方程式を満たすことが知られています．
Ｃ0＝１を満足させなければならないので，複号は負号をとると，
Ｆ（ｔ）＝{1-(1-4x)^(1/2)}/2x
がでてきます．
凸ｎ角形を対角線で三角形分割する仕方は何通りあるかという問題は，回転や反転で同型になるものを同じと数えると，
１，１，１，３，４，１２，２７，８２，２２８，７３３，２２８２，７５２８，・・・
となることを付記しておきたいと思います．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【２】飽和炭化水素の構造異性体数
炭化水素の中で単結合のみで構成されている飽和炭化水素（アルカン，パラフィン系）は分子式ＣkＨ2k+2をもつ．炭素原子Ｃの原子値は４，水素原子Ｈの原子値は１である．
Ｈ Ｈ Ｈ Ｈ Ｈ Ｈ
｜ ｜ ｜ ｜ ｜ ｜
Ｈ−Ｃ−Ｈ Ｈ−Ｃ−Ｃ−Ｈ Ｈ−Ｃ−Ｃ−Ｃ−Ｈ
｜ ｜ ｜ ｜ ｜ ｜
Ｈ Ｈ Ｈ Ｈ Ｈ Ｈ
メタン，エタン，プロパンのＣを・（頂点），Ｃ−Ｃ結合を−（辺）で表すことにすると，それぞれ
・ ・−・ ・−・−・
のようにグラフで表現できる．
ブタン，ペンタン，ヘキサンは
・−・−・−・ ・−・−・−・−・ ・−・−・−・−・−・
となるが，それぞれに構造異性体があり，
（ｋ＝４）
・
｜
・−・−・
（ｋ＝５）
・ ・
｜ ｜
・−・−・−・ ・−・−・
｜
・
（ｋ＝６）
・ ・ ・
｜ ｜ ｜
・−・−・−・−・ ・−・−・−・−・ ・−・−・−・
｜
・
・ ・
｜ ｜
・−・−・−・
すなわち，
位数 ：１，２，３，４，５，６，７， ８， ９，１０， １１， １２， １３，・・・，ｋ，・・・
異性体数：１，１，１，２，３，５，９，１８，３５，７５，１５９，３５７，７９９，・・・，ｆ（ｋ），・・・
となる．
ところが，異性体数ｆ（ｋ）の一般的なｋに対する数え上げ公式はないということである．また，同型でない木グラフの総数をｇ（ｋ）とおくと
位数 ：１，２，３，４，５，６， ７， ８， ９， １０， １１，１２， １３，・・・，ｋ，・・・
ｇ（ｋ）：１，１，１，２，３，６，１１，２３，４７，１０６，２３５，５５１，１３０１，・・・，ｇ（ｋ），・・・
これらの詳細についてはコラム「飽和炭化水素の構造異性体数」を参照されたい．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【３】円の最大分割数（その１）
（問）１つの円をｎ本の弦で分割する．その際，分割によってできる領域が最も多くなるようにする．最大分割領域数Ｓnはいくつになるか？
（答）パンケーキをｎスライスしたときの最大ピース数を求めよという問題ですが，この問題は実は円という条件を取り去っても同じ答えになります．すなわち，平面をｎ本の線で分割する．その際，分割によってできる領域が最も多くなるようにする．最大分割領域数Ｓnはいくつになるか？
分割される領域数が最大になるためには，新しい線（弦）を引くとき，それ以前のすべての線（弦）と新しい交点で交わるようにします．既存の交点を通ると分割される領域が最大数にならないからです．
Ｓ0＝１，Ｓ1＝２，Ｓ2＝４，Ｓ3＝７
はすぐに求められます．このことからｎ本目の線（弦）を引くと新しい領域がｎ個増えることがわかります．これを式で表すと
Ｓn＝Ｓn-1＋ｎ
Ｓn＝Ｓn-1＋ｎ
Ｓn-1＝Ｓn-2＋ｎ−１
・・・・・・・・・・
Ｓ1＝Ｓ0＋１
Ｓ0＝１
を辺々加えると，一般式
Ｓn＝１＋（１＋２＋３＋・・・＋ｎ）＝１＋ｎ（ｎ＋１）／２
＝（ｎ^2＋ｎ＋２）／２
が得られます．
Ｓ0＝１，Ｓ1＝２，Ｓ2＝４，Ｓ3＝７，
Ｓ4＝１１，Ｓ5＝１６，Ｓ6＝２２，Ｓ7＝２９，
Ｓ8＝３７，Ｓ9＝４６，Ｓ10＝５６，・・・
と続くというわけです．
パンケーキではなく，ケーキをｎスライスしたときの最大ピース数を求めよという問題では，
Ｓn＝（ｎ＋２）（ｎ＋３）／６
Ｓ0＝１，Ｓ1＝２，Ｓ2＝４，Ｓ3＝８，
Ｓ4＝１５，Ｓ5＝２６，Ｓ6＝４２，Ｓ7＝６４，
Ｓ8＝９３，Ｓ9＝１３０，Ｓ10＝１７６，・・・
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【４】円の最大分割数（その２）
（問）円周上にｎ点をとり，円周上の点同士をすべて互いに弦で結ぶ．その際，円の分割によってできる領域が最も多くなるようにする．最大分割領域数Ｍnはいくつになるか？
（答）Ｍ1＝１，Ｍ2＝２は明らか．また，円に内接する三角形，四角形，五角形を描くと
Ｍ3＝４，Ｍ4＝８，Ｍ5＝１６
このことから，
Ｍn＝２^(n-1)
であると予想されます．しかし，この式ではＭ0＝１／２となってしまい，Ｍ0＝１とならないことが気にかかるところです．
ｎ＝６の場合を実際にやってみると，正六角形のように３本の線が１点で交わってしまう場合は最大領域数にならないのでＮＧですが，第６の点が既存の弦の交点を通らないように注意すると，Ｍ6＝３２ではなく，Ｍ6＝３１となることがわかります．
ここで
Ｍn＝２^(n-1)
は間違いであることに気づかされるのですが，さらに
Ｍ7＝５７，Ｍ8＝９９，Ｍ9＝１６３
となり，数列
｛１，２，４，８，１６，３１，５７，９９，１６３，・・・｝
は，公比２の等比数列
｛１，２，４，８，１６，３２，６４，１２８，２５６，・・・｝
から大きく離れていきます．
それでは一般式はどのように表されるのでしょうか？ 図を描きながらパターンを探してみると，円周上に３点がある場合は三角形の外側に３つの領域，内側に１つの領域，４点の場合は四角形の外側に４つの領域，内側に４つの領域ができる．
４＝３＋１，８＝４＋４
円周上に５点がある場合は五角形の外側に５つの領域，すぐ内側に１０個の三角形領域，中心部に五角形がひとつある．
１６＝５＋１０＋１
円周上に６点がある場合は六角形の外側に６つの領域，すぐ内側に１８個の三角形領域，その内側に３つの五角形と３つの四角形，そして中心部に三角形がひとつある．
３１＝６＋１８＋６＋１
しかしこのパターンからはどうしてもこれといったアイディアが浮かばないのですが，領域の数は弦の数や交点の数と関係していることは明らかであって，前者はnＣ2，後者はnＣ4で計算されます．
図なしにこれ以上説明することは難しいので，結論を述べますが
［参］コンウィイ・ガイ「数の本」シュプリンガー・フェアラーク東京
には，すべての領域にラベルを与えると，ラベルを含む数の個数は０，１，２，３，４のいずれかであって，２項係数の和
Ｍn＝n-1Ｃ0＋n-1Ｃ1＋n-1Ｃ2＋n-1Ｃ3＋n-1Ｃ4
＝１＋（ｎ−１）＋（ｎ−１）（ｎ−２）／２＋（ｎ−１）（ｎ−２）（ｎ−３）／６＋（ｎ−１）（ｎ−２）（ｎ−３）（ｎ−４）／２４
＝（ｎ^4−６ｎ^3＋２３ｎ^2−１８ｎ＋２４）／２４
となることが示されています．
パスカルの三角形のはじめの５項の和というわけですが，
n-1Ｃ0＋n-1Ｃ1＋n-1Ｃ2＋n-1Ｃ3＋n-1Ｃ4＋・・・＋n-1Ｃn-1＝２^(n-1)
ですから，ｎが大きくなればその答えは２^(n-1)からますます離れていくというわけです．
Ｍ1＝１，Ｍ2＝２，Ｍ3＝４，Ｍ4＝８，Ｍ5＝１６，
Ｍ6＝３１，Ｍ7＝５７，Ｍ8＝９９，Ｍ9＝１６３，Ｍ10＝２５６，
Ｍ11＝３８６，Ｍ12＝５６２，Ｍ13＝７９４，Ｍ14＝１０９３，
Ｍ15＝１４７１，Ｍ16＝１９４１，Ｍ17＝２５１７，Ｍ18＝３２１４，
Ｍ19＝４０４８，Ｍ20＝５０３６，Ｍ21＝６１９６，Ｍ22＝７５４７，
Ｍ23＝９１０９，Ｍ24＝１０９０３，Ｍ25＝１２９５１，Ｍ26＝１５２７６，
Ｍ27＝１７９０２，Ｍ28＝２０８５４，Ｍ29＝２４１５８，Ｍ30＝２７８４１，
Ｍ31＝３１９３１，・・・
数列
｛Ｍn｝＝｛１，２，４，８，１６，３１，５７，９９，１６３，・・・｝
をこの問題を提起したモーザーにちなんでモーザー数列と呼ぶことにすると，モーザー数列は先入観から間違った答えを予想してしまう例としてしばしば引き合いにだされるものになっています．
なお，カタラン数列のはじめの４項１，２，５，１４は初項１から始まって前項を３倍して１を引いたものに一致するのですが，５項目以降は異なってしまいます．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【５】畳の敷き方数
（問）ｎ×２ｍの長方形の部屋にｎ×ｍ枚の畳を敷く場合の敷き方は何通りあるか？
（答）
ｍ／ｎ １ ２ ３ ４ ５
１ 1 2 3 5 8
２ 1 5 11 36 95
３ 1 13 41 281 1183
４ 1 34 153 2245 14824
５ 1 89 571 18061 185928
ｍ＝１の行はフィボナッチ数列となるのですが，その他の行はどのような数列になるのでしょうか？ トリボナッチ数列，テトラナッチ数列，ペンタナッチ数列，ヘキサナッチ数列・・・とその変形（ａn＝ａn-2＋ａn-5，ａn＝ａn-2＋ａn-3（パドヴァン数列・ペラン数列），ａn＝ａn-1＋ａn-3，ａn＝２ａn-1＋ａn-2（ペル数列），ａn＝ａn-2＋ａn-3＋ａn-4，・・・）でないことはすでに検討済みです．
しかし，ａn＝（ａn-1）^2−ａn-2のような数列の可能性があり，手がかりを求めて，
［参］Sloane, A handbook of integer sequences, Academic Press
を参照してみたのですが，該当する数列は掲載されておりませんでした．
なお，（ｎ，２ｍ）＝（６，６）の場合に分断線が現れないように畳を敷くことができません．それ以外の場合は分断線が生じないように畳を敷くことができることが証明されています．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝