烷烴同分異構體個數的計數方法

同分異構體個數的計數，是一個經典的計數問題。然而由於其複雜性，直到20世紀，這個問題才得以解決，本文介紹一種求解烷烴同分異構體個數的DP方法。

首先，要解決這個問題，我們需要把求烷烴同分異構體個數的過程化為求烷基同分異構體個數。烷烴的問題之所以難以求解，因為烷烴的結構，相當於一棵所有結點度數小於等於4的無根樹。由於無根，要求解其個數，只能遍歷其所有的可能連接方式，然後判斷每種方式間是否結構相同。如這樣進行求解，會導致複雜度難以承受。因此，我們選擇將其降為求解相同碳數烷基的個數。

求解相同碳數烷基的同分異構體個數，在《THE NUMBER OF STRUCTURALLY ISOMERIC ALCOHOLS OFTHE METHANOL SERIES》（http://pubsdc3.acs.org/doi/pdf/10.1021/ja01359a027）一文中有詳細的介紹。大意為將烷基分為（n個碳構成的1°烷基個數），（2°），（3°），而後利用組合的方式可以進行遞推，得到n碳的烷基個數。

在求得烷基同分異構體個數後，如何將烷烴的問題化歸到烷基的問題呢？我們可以根據奇偶進行討論。

如碳數為偶：

①可以被斷為兩個n/2碳大小的烷基

此種情況下，計數

②不能被斷為兩個n/2碳大小的烷基

此種情況下，必能找到唯一一個3°或4°碳作為分子中心，使得其所連接的每個烷基大小均小於n/2碳，使用組合計數可得這一部分烷烴的個數。

如碳數為奇：

①可以被斷為一(n-1)/2和一(n+1)/2大小的烷基

根據(n+1)/2大小的烷基是否由一(n-1)/2大小的烷基連接一亞甲基構成進行討論。

②不能被斷為兩個n/2碳大小的烷基

此種情況下，必能找到唯一一個3°或4°碳作為分子中心，使得其所連接的每個烷基大小均小於n/2碳，使用組合計數可得這一部分烷烴的個數。

附代碼：同分異構體個數計數

PS: 由於此問題的DP為根據烷基同分異構體個數的DP，因而要求n個碳烷烴的同分異構體個數，必須先處理出1——n-1個碳烷基的同分異構體個數，另外實現的時候由於只是粗暴模擬，複雜度較高。

推薦閱讀：