#はじめに
アルカンの構造異性体を数え上げたい。
とりあえずググると以下の文献がヒットしました。
入谷 寛「アルカンの構造異性体の組合せ論的数え上げ」１９９９年
(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 |
#まとめ
アルカンの構造異性体数は指数関数的に増加していることがわかった。
機会があれば立体異性体も数えたい。