LoginSignup
14
6

More than 3 years have passed since last update.

@miwo

アルカンの構造異性体を数える

Posted at

はじめに

アルカンの構造異性体を数え上げたい。

とりあえずググると以下の文献がヒットしました。

入谷　寛「アルカンの構造異性体の組合せ論的数え上げ」１９９９年
(https://www.jstage.jst.go.jp/article/jchemsoft/5/2/5_2_65/_pdf)

アルキル基の炭素数ごとの組み合わせの数を再帰的に計算しておき、中心の炭素原子に付く四つのアルキル基の組み合わせを全列挙して求めているらしい。

この方法でも良いですが、アルカンの重心に着目した方が場合分けが少なくて済みます。

アルカンの重心

炭素原子を頂点、結合を枝とみなすと、アルカンは木グラフと同じ構造をしていることがわかります。

一般に木グラフの頂点数を$n$とすると、隣接する部分木の頂点数が全て$n/2$以下になる頂点を重心と呼びます。
重心は木グラフに対して必ず存在し、一つまたは二つです（重心が二つの場合は必ず隣接しています）。

以下の記事に詳しく書いてあります。
ツリーの重心分解 (木の重心分解) の図解

つまり重心に着目すれば、アルカンを重心の数で二種類に分類できます。

重心が一つの場合

重心となる炭素を一つ指定し、残りの炭素を四つのアルキル基に振り分けます。そして、あらかじめ求めておいた炭素数ごとのアルキル基の場合の数を掛け合わせます。

この時、炭素の振り分け方が、$(2,2,1,0)$のように同じ数の炭素を持つアルキル基の組が生じた場合、重複組合せを使って計算します。

重心が二つの場合

重心が二つになる場合はアルカンの炭素数は必ず偶数です。つまり二つの重心を結ぶ結合でアルカンを切ると、炭素数がそれぞれ$n/2$の部分木が二つできます。

よって炭素数$n/2$のアルキル基二つの組み合わせですから、重複組合せで計算できます。

アルキル基の場合の数を求める

$A(n)$を炭素数nのアルキル基の場合の数とします。

まず、一つの炭素をアルキル基の結合部位として決めると、その炭素上には残り三つの結合箇所があります。その三箇所に付く炭素の数をそれぞれ$n_1,n_2,n_3$とすると、場合の数は

$$A(n)=A(n_1)*A(n_2)*A(n_3)$$

となります($n_1+n_2+n_3=n-1$です)。
ただし、$n_1=n_2$など同じ数の炭素が割り振られた場合には重複組合せを使います。この場合($n_3$は異なるとする)

$$A(n)={}_{A(n_1)} H _2 * A(n _3)$$

となります。

したがって炭素数$n$のアルキル基の組み合わせの数$A(n)$は

$$A(n)=\sum A(n_1)*A(n_2)*A(n_3)$$

ただし$\sum$は$n_1+n_2+n_3=n-1$を満たす組$(n_1,n_2,n_3)$について全て求め,値が同じになる場合は重複組合せを使います。

なお初期値として$A(0)=1,A(1)=1$としておきます。

コード

上記の計算をPythonで実装しました。

#重複組合せ
#bに関しては2,3,4しかとりえない
def H(a,b):
    if(b==2):
        return int((a+1)*(a)/2)
    if(b==3):
        return int((a+2)*(a+1)*(a)/6)
    if(b==4):
        return int((a+3)*(a+2)*(a+1)*(a)/24)

#炭素数nのアルキル基の場合の数を求める
def A_calc(n):
    ans=0
    for i in reversed(range(n+1)):
        for j in reversed(range(n-i+1)):
            if(i<j or j<n-i-j):
                continue
            if(i==j):
                if(j==n-i-j):
                    ans+=H(A[i],3)
                else:
                    ans+=H(A[i],2)*A[n-i-j]
            else:
                if(j==n-i-j):
                    ans+=A[i]*H(A[j],2)
                else:
                    ans+=A[i]*A[j]*A[n-i-j]
    return ans

def A_init(n):
    for i in range(1,n+1):
        A[i]=A_calc(i-1)

#炭素数nのアルカンの異性体数を求める
def calc(n):
    ans=0
    #二重心の場合の組み合わせの数
    if(n%2==0):
        ans+=H(A[int(n/2)],2)
    #一重心の場合の組み合わせの数
    n-=1
    for i in reversed(range(int(n/2)+1)):
        for j in reversed(range(n-i+1)):
            if(i<j):
                continue
            for k in reversed(range(n-i-j+1)):
                if(j<k or k<n-i-j-k):
                    continue
                if(i==j):
                    if(j==k):
                        if(k==n-i-j-k):
                            ans+=H(A[i],4)
                        else:
                            ans+=H(A[i],3)*A[n-i-j-k]
                    else:
                        if(k==n-i-j-k):
                            ans+=H(A[i],2)*H(A[k],2)
                        else:
                            ans+=H(A[i],2)*A[k]*A[n-i-j-k]
                else:
                    if(j==k):
                        if(k==n-i-j-k):
                            ans+=A[i]*H(A[j],3)
                        else:
                            ans+=A[i]*H(A[j],2)*A[n-i-j-k]
                    else:
                        if(k==n-i-j-k):
                            ans+=A[i]*A[j]*H(A[k],2)
                        else:
                            ans+=A[i]*A[j]*A[k]*A[n-i-j-k]
    return ans

#炭素数Nまで計算
N=100

#アルキル基の構造異性体数の計算
A=[1]*(N+1)
A_init(N)

for i in range(1,N+1):
    print(str(i)+":"+str(value[i]))

結果

n=100までの計算結果を載せます。

炭素数 構造異性体の数
1 1
2 1
3 1
4 2
5 3
6 5
7 9
8 18
9 35
10 75
11 159
12 355
13 802
14 1858
15 4347
16 10359
17 24894
18 60523
19 148284
20 366319
21 910726
22 2278658
23 5731580
24 14490245
25 36797588
26 93839412
27 240215803
28 617105614
29 1590507121
30 4111846763
31 10660307791
32 27711253769
33 72214088660
34 188626236139
35 493782952902
36 1295297588128
37 3404490780161
38 8964747474595
39 23647478933969
40 62481801147341
41 165351455535782
42 438242894769226
43 1163169707886427
44 3091461011836856
45 8227162372221203
46 21921834086683418
47 58481806621987010
48 156192366474590640
49 417612400765382273
50 1117743651746953259
51 2994664179967370601
52 8031081780535296710
53 21557771913572631012
54 57919180873148437629
55 155745431857549699100
56 419149571193411835359
57 1128939578361332874088
58 3043043571906827227693
59 8208615366863753967823
60 22158734535770411337280
61 59858097847706866186452
62 161805725349297357085018
63 437671691526158937281842
64 1184616185385310844445863
65 3208285066181475823869402
66 8694130712024868342403886
67 23573796134448175682793870
68 63955159527348139685377612
69 173603007393950250856911655
70 471484798515330370663154990
71 1281151315764638224337854660
72 3482965749140691312601097169
73 9473447386804490528250511954
74 25779306238954404876145971152
75 70183211512214096507878098288
76 191156381393249393606196098347
77 520874195248906782620764355276
78 1419908915343952143819621933179
79 3872282575137005482812776727067
80 10564476906946674987130573457355
81 28833609436277333069522282218039
82 78725585464391037009418229905462
83 215027809474796675305384999330747
84 587531723826577193769359039199494
85 1605913778494711520533283701961789
86 4391002908093323432491492371267469
87 12010257907756938982759765847470017
88 32861295558120887111747295181467690
89 89940959024891576595737588553744985
90 246245150242821441575701401999382586
91 674391606297983434165408987077158377
92 1847515048012613354023477766033405133
93 5062818112121161198806186654779267278
94 13877857529584521326121016967719147670
95 38051836070803836967530576140540665884
96 104363664561059272859344623125934479555
97 286312976836850191330107088865050136610
98 785684759853087704231889779084438607888
99 2156596319845084997631339456532030866433
100 5921072038125809919755273760677280659392

graph

まとめ

アルカンの構造異性体数は指数関数的に増加していることがわかった。

機会があれば立体異性体も数えたい。

14
6
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
14
6