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


last updated 99.07.25

恐れ入りますが、Netscape Navigatorは表示のズレがひどいので、Internet Explorerをお使いください。


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

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

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


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


□ 問題の説明

<<アルカンの表現>>

    n = 2の場合(C2H4) 

         H  H          
         |  |          
     H−C−C−H    ===>  簡単のため、水素を     C−C
         |  |                 省略して右のように
         H  H                 炭素(C)の結合の
                                みを記述する
 
    省略形の場合、炭素どうしの結合のない部分は水素と結合している。

    省略形での記述例

    C−C−C         C−C−C     C−C−C−C
                          |            |  |
                          C            C  C
    
    下記のような炭素どうしの2重結合やループはない。

    C=C        C−C
                 |  |
                 C−C
 
<<構造異性体とは>>

   炭素どうしの結合状態に着目したとき、結合関係が同じものは同一としてあつかう。   
   (1)と(2)は同じ、(6)は(3)と同じです。

  (1)  C−C−C−C−C−C     (2)  C−C−C−C−C
                                                         |
                                                         C

  (3)  C−C−C−C−C         (4)  C−C−C−C−C
                     |                           |
                     C                           C

  (5)  C−C−C−C             (6)  C−C−C−C−C
             |  |                            |
             C  C                            C
  
  (7)         C
                |
         C−C−C−C
                |
                C

   (1),(3),(4),(5)は別物となります。


問題の「構造異性体の数を求める」とは、nが与えられたとき、上記の例の(2)や(6)は(1)、(3)と同じなので数えないようにして全く異なるものがいくつあるかをもとめることです。


A1:パズルとして、シラミツブシに探索する方法

パズルとしてみると結構面白い問題です。
残念ながら、あまり大きなNの数は求められません
N=16までで 9秒かかりました。やはり、N=20あたりが限界です。

説明文 A1memo.txt
A1addendum.txt
ソース A1unit.cpp
A1unit.h
結果 A1result.txt


A2:組合わせ論による方法

「組み合わせ論入門」(G.ポリア他著)にあるCnH2n+1OHの構造異性体の説明を参考にして、アルカン(CnH2n+2)の構造異性体を数えてみました。高橋さんのHPで紹介のあった入谷先生の論文の方法とはチョットだけ違います。こちらは、正しいかどうかはあまり自信がありません。
一応論文の結果と照合して、N=40までは一致しましたので大丈夫だろうとおもいます。
N=45までで40ミリ秒でとけました。(うそみたいな感じでしょ)
A1の方法が馬鹿みたいみたいにおもわれてきます。

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


しかし、答えを知っていて問題を解くのは楽ですね。
最初に出た結果は、N=17,21,25,29,..で間違っていました。
たぶん、正解を知らなければ、このままになっていたでしょう。

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


Home
Up
Back
Next