【１】はしがき

　炭化水素の中で単結合のみで構成されている飽和炭化水素（アルカン，パラフィン系）は分子式ＣkＨ2k+2をもつ．炭素原子Ｃの原子値は４，水素原子Ｈの原子値は１である．

　　　　Ｈ　　　　　　　Ｈ　Ｈ　　　　　　　Ｈ　Ｈ　Ｈ

　　　　｜　　　　　　　｜　｜　　　　　　　｜　｜　｜

　　Ｈ−Ｃ−Ｈ　　　Ｈ−Ｃ−Ｃ−Ｈ　　　Ｈ−Ｃ−Ｃ−Ｃ−Ｈ

　　　　｜　　　　　　　｜　｜　　　　　　　｜　｜　｜

　　　　Ｈ　　　　　　　Ｈ　Ｈ　　　　　　　Ｈ　Ｈ　Ｈ

メタン，エタン，プロパンのＣを・（頂点），Ｃ−Ｃ結合を−（辺）で表すことにすると，それぞれ

　　　　・　　　　　　　・−・　　　　　　　・−・−・

のようにグラフで表現できる．

　ブタン，ペンタン，ヘキサンは

　　・−・−・−・　　・−・−・−・−・　　　・−・−・−・−・−・

となるが，それぞれに構造異性体があり，

（ｋ＝４）

　　　　・

｜

　　・−・−・

（ｋ＝５）

　　　　　　・　　　　　　　・

　　　　　　｜　　　　　　　｜

　　・−・−・−・　　　・−・−・

　　　　　　　　　　　　　｜

　　　　　　　　　　　　　　・

（ｋ＝６）

　　　　　　　　・　　　　　　　　・　　　　　　　　・

　　　　　　　　｜　　　　　　　　｜　　　　　　　　｜

　　・−・−・−・−・　　・−・−・−・−・　　・−・−・−・

　　　　　　　　　　　　　　　　　　　　　　　　　｜

　　　　　　　　　　　　　　　　　　　　　　　　　　・

　　　　・　・

　　　　｜　｜

　　・−・−・−・

　すなわち，

　　位数　　：１，２，３，４，５，６，・・・，ｋ，・・・

　　異性体数：１，１，１，２，３，５，・・・，ｆ（ｋ），・・・

となる．

　ところが，異性体数ｆ（ｋ）の一般的なｋに対する数え上げ公式はないという話を聞いて驚かされた．その数を完全に決定することは簡単ではないにしてもそれなりの漸近評価を与えることはできるだろうと思ったのだが，訊ねてみたところ，どれくらいのオーダーで増えるのかという漸近公式もわからないという．今回のコラムではこの辺の事情について考えてみることにした．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】木グラフ

グラフとは点（頂点ｖ）とそれらを結ぶ線（辺ｅ）とからできている１次元図形のことであるが，そのうち，閉路を含まない連結グラフのことを木（グラフ）と呼ぶ．

　炭素の原子値は４であるが，そのような制限を取り除けば，

　　　　・

　　　　｜

　　・−・−・

　　　／　＼

　　・　　　・

も可能となる．

　これも木グラフであるから，同型でない木グラフの総数をｇ（ｋ）とおくと

　　位数　　：１，２，３，４，５，６，・・・，ｋ，・・・

　　ｇ（ｋ）：１，１，１，２，３，６，・・・，ｇ（ｋ），・・・

となる．ともあれ，制限のついた飽和炭化水素の構造異性体数ｆ（ｋ）よりも木グラフの総数ｇ（ｋ）の数え上げの方がより一般的な問題であると考えられる．そこでｆ（ｋ）を求める代わりにｇ（ｋ）を求めてみることにする．

１８５７年，ケーリーは知り合いの化学者からの依頼でＣkＨ2k+2の構造異性体の数を数えようとしていたときに多くの「木グラフ」の性質を発見した．木の性質のひとつとして，木の頂点数をｖ，辺数をｅとすると

　　ｖ＝ｅ＋１

が成り立つが，これはオイラーの定理：ｖ−ｅ＋ｆ＝１においてｆ＝０としたものである．すなわち，連結でありかつ閉路を含まないという必要十分条件を満たしていて，飽和炭化水素の場合，ｖ＝３ｋ＋２であるからｅ＝３ｋ＋１で与えられるという意味にほかならない．

　位数ｋに対して同等でない木はいくつあるのか？・・・これがケーリーの考えた問題であり，同等でない木の総数を与える公式（ケーリーの公式）が知られている．ケーリーの公式とは「位数ｋの完全グラフのすべての異なる全域木の総数はｋ^(k-2)で与えられる」というものである．

　　位数ｋ　　　　　　：１，２，３，　４，　　５，　　　６，ｋ

　　同等でない木の総数：１，１，３，１６，１２５，１２９６，ｋ^(k-2)

［補］位数ｋのグラフでどの２点も隣接しているとき完全グラフという．正ｋ角形＋すべての対角線をイメージすればよく，ｖ＝ｋ，ｅ＝kＣ2である．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

　このように同等でない木の総数はきれいで簡単な式で表現できる．ところが残念なことに位数ｋの同形でない木の総数ｇ（ｋ）を与える公式は知られていないという．

　　位数ｋ　　　　　　：１，２，３，　４，　　５，　　　６，・・・

　　同等でない木の総数：１，１，３，１６，１２５，１２９６，・・・

　　同型でない木の総数：１，１，１，　２，　　３，　　　６，・・・

そこでせめて下界・上界だけでも求めておきたいと思う．

　位数ｋの同等でない木はｋ^(k-2)個ある．たとえばｋ＝４では各頂点にＡ，Ｂ，Ｃ，Ｄとラベルを付けた場合，同等でない木は１６種類あるというわけである．もし頂点にラベルがなければブタンとイソブタンのように同型の木は２種類あるわけであるから，同型でない木グラフの個数はこれよりもかなり少ない．

　同型になるものは高々ｋ！個である（上の例では４！個の同等でない木が存在するが同型なグラフは２個だけであり，数えすぎであるが・・・）．したがって，同値類の総数は

　　ｋ^(k-2)／ｋ！

以上になるので，ｋ頂点の木グラフで同型でないものの総数もこの値以上になる．

　下界の漸近挙動を調べるために，スターリングの公式

　　ｋ！〜（２π）^(1/2)ｋ^(k+1/2)ｅｘｐ（−ｋ）

を用いると

　　ｋ^(k-2)／ｋ！〜（２π）^(-1/2)ｋ^(-2-1/2)ｅｘｐ（ｋ）

となって，ｋが大きいときはほぼ指数関数的ｅｘｐ（ｋ）に増加することが理解される．

　なお，ｋ＞１に対して，不等式

　　ｅ（ｋ／ｅ）^k≦ｋ！≦ｅｋ（ｋ／ｅ）^k

が成り立つから

　　ｋ^(k-2)／ｋ！≧ｅｘｐ（ｋ−１）／ｋ^3

となって，下界は少なくともｅｘｐ（ｋ−１）／ｋ^3である．

　また，上界については，同型でないｋ頂点の木グラフは高々４^kしかないことが証明できて，以上のことをまとめると

　　ｅｘｐ（ｋ−１）／ｋ^3≦ｇ（ｋ）≦４^k

となることがわかるのである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【３】あとがき

　ここでは木グラフの場合も含んで一般のグラフについて考えることにする．すなわち閉路を含んでもよいし連結でなくてもよいものとする．

　ｖ＝ｋの場合，異なるグラフの総数は２^(kC2)であるが，同形でないグラフの個数はこれよりもかなり少ない．たとえばｋ＝３のときは８個のグラフがあるが，同型でないものは４つしかない．ｋ＝４の同型でないグラフの個数は１１個である．

　　位数ｋ　　　　　　　　：１，２，３，　４，・・・

　　同等でないグラフの総数：１，２，８，６４，・・・

　　同型でないグラフの総数：１，２，４，１１，・・・

　前節と同様の議論により，同値類の総数は

　　２^(kC2)／ｋ！

以上になるので，ｋ頂点のグラフで同型でないものの総数もこの値以上になる．

　　ｌｏｇ（２^(kC2)／ｋ！）＝kＣ2−ｌｏｇｋ！

　　　　　　　　　　　　　　≧ｋ^2／２−ｋ／２−ｋｌｏｇｋ

　　　　　　　　　　　　　　＝ｋ^2／２（１−１／ｋ−２ｌｏｇｋ／ｋ）

ｋが大きいときｌｏｇ（２^(kC2)／ｋ！）はｋ^2／２とほぼ同じ振る舞いをすることがわかる（この相対誤差はｋ→∞のとき０に収束する）．すなわち，ｋ頂点の同型でないグラフの総数はｅｘｐ（ｋ^2）のオーダーで増加し，たとえば２^kよりもずっと大きいことがわかる．また，２^(kC2)に較べそれほどゆっくり増加するわけでもないこともわかるだろう．

　これは漸近評価であるが，グラフの正確で実用的な数え上げに関しては，ポリアが化学者から高分子の異性体がいくつあるかを求めることを依頼されて，有名なポリアの数え上げ理論を発見している．ここではポリアの定理の詳細については記さないが，置換群によってもたらされる同値類の個数（バーンサイドの定理）に基づいて数え上げを行うものである．

　群の概念は，代数方程式の解の置換の研究として誕生した歴史をもつが，今日では自然科学の多くの分野に応用され，たとえば，化学における分子構造やタンパク質やＤＮＡの配列の決定に関しても，群論が重要な役割を果たしていることはご存知であろう．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝