アルカン(CnH2n+2)の構造異性体の数

last updated 99.07.25

恐れ入りますが、Ｎｅｔｓｃａｐｅ　Ｎａｖｉｇａｔｏｒは表示のズレがひどいので、Ｉｎｔｅｒｎｅｔ　Ｅｘｐｌｏｒｅｒをお使いください。

高橋k謙一郎さんのＨＰの掲示板でアルカンの構造異性体の数を求める話が話題になりました。

この問題は、グラフ理論の入門書にも記述されていたりして、結構有名な問題のようです。
しかし、一般のｎに対して求める方法は、入門書レベルの本には出ていないようです。掲記の掲示板では、組合せ論的に解く下記の論文の紹介があり一件落着となりました。

「アルカンの構造異性体の組合せ論的数え上げ」入谷寛先生の論文 (http://cssjweb.chem.eng.himeji-tech.ac.jp/jcs/v5n2/a3/abstj.html)

パズルとしても面白く、チョット興味があったのでチャレンジして、２通りの方法で解いてみました。

□ 問題の説明

<<アルカンの表現>>

    ｎ ＝ ２の場合（Ｃ2Ｈ4） 

         Ｈ  Ｈ          
         ｜  ｜          
     Ｈ－Ｃ－Ｃ－Ｈ    ＝＝＝＞  簡単のため、水素を     Ｃ－Ｃ
         ｜  ｜                 省略して右のように
         Ｈ  Ｈ                 炭素（Ｃ）の結合の
                                みを記述する
 
    省略形の場合、炭素どうしの結合のない部分は水素と結合している。

    省略形での記述例

    Ｃ－Ｃ－Ｃ         Ｃ－Ｃ－Ｃ     Ｃ－Ｃ－Ｃ－Ｃ
                          ｜            ｜  ｜
                          Ｃ            Ｃ  Ｃ
    
    下記のような炭素どうしの２重結合やループはない。

    Ｃ＝Ｃ        Ｃ－Ｃ
                 ｜  ｜
                 Ｃ－Ｃ
 
<<構造異性体とは>>

   炭素どうしの結合状態に着目したとき、結合関係が同じものは同一としてあつかう。   
   （１）と（２）は同じ、（６）は（３）と同じです。

  （１）  Ｃ－Ｃ－Ｃ－Ｃ－Ｃ－Ｃ     （２）  Ｃ－Ｃ－Ｃ－Ｃ－Ｃ
                                                         ｜
                                                         Ｃ

  （３）  Ｃ－Ｃ－Ｃ－Ｃ－Ｃ         （４）  Ｃ－Ｃ－Ｃ－Ｃ－Ｃ
                     ｜                           ｜
                     Ｃ                           Ｃ

  （５）  Ｃ－Ｃ－Ｃ－Ｃ             （６）  Ｃ－Ｃ－Ｃ－Ｃ－Ｃ
             ｜  ｜                            ｜
             Ｃ  Ｃ                            Ｃ
  
  （７）         Ｃ
                ｜
         Ｃ－Ｃ－Ｃ－Ｃ
                ｜
                Ｃ

   （１），（３），（４），（５）は別物となります。

問題の「構造異性体の数を求める」とは、ｎが与えられたとき、上記の例の（２）や（６）は（１）、（３）と同じなので数えないようにして全く異なるものがいくつあるかをもとめることです。

＜Ａ１：パズルとして、シラミツブシに探索する方法＞

パズルとしてみると結構面白い問題です。
残念ながら、あまり大きなＮの数は求められません
Ｎ＝１６までで９秒かかりました。やはり、Ｎ＝２０あたりが限界です。

	説明文	A１memo.txt A1addendum.txt
	ソース	A１unit.cpp A１unit.h
	結果	A１result.txt

＜Ａ２：組合わせ論による方法＞

「組み合わせ論入門」（Ｇ．ポリア他著）にあるＣnＨ2n+1ＯＨの構造異性体の説明を参考にして、アルカン（ＣnＨ2n+2）の構造異性体を数えてみました。高橋さんのＨＰで紹介のあった入谷先生の論文の方法とはチョットだけ違います。こちらは、正しいかどうかはあまり自信がありません。
一応論文の結果と照合して、Ｎ＝４０までは一致しましたので大丈夫だろうとおもいます。
Ｎ＝４５までで４０ミリ秒でとけました。（うそみたいな感じでしょ）
Ａ１の方法が馬鹿みたいみたいにおもわれてきます。

	説明文	A2memo.txt A2addendum.txt
	ソース	A2unit.cpp A2unit.h
	結果	A2result.txt

しかし、答えを知っていて問題を解くのは楽ですね。
最初に出た結果は、Ｎ＝１７，２１，２５，２９，．．で間違っていました。
たぶん、正解を知らなければ、このままになっていたでしょう。

最初に答えを出した人はエライ！！

Home

Back

Next