舉報了,标題與内容嚴重不符
烷基計數
注意到烷基相當于是有根樹,這樣會簡單很多
我們用 引理處理子樹同構,列出式子就是
考慮倍增,那麼 在目前環節均是已知項,牛頓疊代就可以了
烯烴計數
我們枚舉雙鍵的位置,設兩邊的 為 ,那麼答案就是
我們用 表示烷基的生成函數,那麼
苯的同系物計數
同樣設 表示烷基的生成函數,然後令
苯環有 6 種置換,枚舉每一種置換
烷烴計數
可以發現,上面 3 中有機物的計數都可以看做 “有根” 的情況,這是較為簡單的
而烷烴計數就是無根的情況,這是較為麻煩的,我們枚舉重心統計,将不是重心的容斥掉
令 表示
非常遺憾的是,這種方法是 的
我們需要尋找一種更高妙的解法
一種思路是我們直接算出 ,最後除以 ,但顯然是錯誤的,因為我們隻會統計 “等價類個數” 次,這咋整?
(兩個點等價當且僅當分别删去這兩個點後的森林相同)
考慮重心作為根,十分 的是除重心之外的兩個點若在一個等價類則其父親邊也在一個等價類
當重心為 1 個點或重心有兩個點但兩邊不同構時,我們有 "點等價類個數” - “邊等價類個數” = 1
否則我們有 "點等價類個數” - “邊等價類個數” = 0,故可以寫出答案
Upd:
芳香烴計數:
芳香烴:含有一個或多個苯環的烴
我們類似烷烴計數,先搞一個 “芳香基” 計數,這個是很容易的
這也能牛頓疊代 /jk
接着我們枚舉重心
若 為奇數
若重心為苯環:保留 前 項
若重心為碳原子:保留 前 項