烷烴同分異構(gòu)體數(shù)目公式？

本質(zhì)上就是一個無標(biāo)號無根樹帶度數(shù)限制的計數(shù)問題.

將問題一般化：求 n 個點的無標(biāo)號無根樹的個數(shù), 且每個點的度數(shù)不超過m。

烷基 (有根樹)：首先考慮計算烷基的個數(shù) (即有根樹)。

考慮暴力 DP.。設(shè)狀態(tài)為 f(i,j,k)f(i,j,k)，表示當(dāng)前共有 ii個點。

最大的子樹大小為 jj，且根的度數(shù)為 kk。對于狀態(tài) f(i,j,k)f(i,j,k)，通過枚舉最大子樹的個數(shù) l 和次大子樹的大小 size。

有f(i,j,k)=∑l∑s+f(i?jl,size,k?l){s+l?1l}f(i,j,k)=∑l∑s+f(i?jl,size,k?l){s+l?1l}。

其中 s=∑ja=1∑m?1b=0f(j,a,b)s=∑a=1j∑b=0m?1f(j,a,b)。

組合數(shù)是用來可重集計數(shù)的。這是O(n3m2)O(n3m2)的。

顯然可以前綴和優(yōu)化，但是空間撐不住。還可以做得更好。考慮如何省掉 jj 這一維狀態(tài)。即設(shè)狀態(tài)為 f(i,j)f(i,j)。表示當(dāng)前共有 ii 個點，根的度數(shù)為 kk。

考慮 DP 的一個技巧: 強行規(guī)定轉(zhuǎn)移順序。即，先 1...n1...n 枚舉 size，表示強制用最大子樹大小為 size 的情形來轉(zhuǎn)移。

不妨設(shè)s=∑m?1k=0f(size,k)s=∑k=0m?1f(size,k)，那么對于一個 f(i,j)f(i,j)。

再枚舉一個最大子樹 (即子樹大小為 size 的子樹) 的個數(shù) k。

我們便有轉(zhuǎn)移f(i,j)←f(i,j)+f(i?size×k,j?k){s+k?1k}f(i,j)←f(i,j)+f(i?size×k,j?k){s+k?1k}這是 O(n2m2)O(n2m2) 的。如果是算烷基的話，便是 O(n2)O(n2) 的。

烷烴 (無根樹)：只要某個點 uu 滿足其子樹大小都 ≤n2≤n2，那么這個點是這顆樹的重心。比較顯然的是, 重心最多只會有兩個，并且有兩個重心的情形，兩個重心一定相鄰。

并且另一個重心做根的時候，這個重心的子樹大小為 n2n2。(當(dāng)然 nn 必須要是偶數(shù))

很多無根樹同構(gòu)的問題就可以通過重心轉(zhuǎn)化為有根樹同構(gòu)。烷烴就可以這么計數(shù)。因為我們可以在 DP 烷基的時候。

強制size<n2size<n2(注意是小于)，這樣求出的 f(i,j)f(i,j) 就是點數(shù)為 ii 且重心度數(shù)為 jj 的無根樹個數(shù)。那么答案為：∑mk=0f(n,k)+[n(mod2)=0]{∑m?1k=0f(n2,k)+12}。