烷系同分异构体个数的计算公式

Question

对任意n大于三的n烷，求同分异构体的个数，递推公式也行。要过程

Answer 1

本质上就是一个无标号无根树带度数限制的计数问题.

将问题一般化：求 n 个点的无标号无根树的个数, 且每个点的度数不超过m。

烷基 (有根树)：首先考虑计算烷基的个数 (即有根树)。

考虑暴力 DP.。设状态为 f(i,j,k)f(i,j,k)，表示当前共有 ii个点。

最大的子树大小为 jj，且根的度数为 kk。对于状态 f(i,j,k)f(i,j,k)，通过枚举最大子树的个数 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)。

组合数是用来可重集计数的。这是O(n3m2)O(n3m2)的。

显然可以前缀和优化，但是空间撑不住。还可以做得更好。考虑如何省掉 jj 这一维状态。即设状态为 f(i,j)f(i,j)。表示当前共有 ii 个点，根的度数为 kk。

考虑 DP 的一个技巧: 强行规定转移顺序。即，先 1...n1...n 枚举 size，表示强制用最大子树大小为 size 的情形来转移。

不妨设s=∑m−1k=0f(size,k)s=∑k=0m−1f(size,k)，那么对于一个 f(i,j)f(i,j)。

再枚举一个最大子树 (即子树大小为 size 的子树) 的个数 k。

我们便有转移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。(当然 nn 必须要是偶数)

很多无根树同构的问题就可以通过重心转化为有根树同构。烷烃就可以这么计数。因为我们可以在 DP 烷基的时候。

强制size<n2size<n2(注意是小于)，这样求出的 f(i,j)f(i,j) 就是点数为 ii 且重心度数为 jj 的无根树个数。那么答案为：∑mk=0f(n,k)+[n(mod2)=0]{∑m−1k=0f(n2,k)+12}。

扩展资料：

烷系同分异构体结构特征：

在烃及其含氧衍生物的分子式中必然含有这样的信息：该有机物的不饱和度。利用不饱和度来解答这类题目往往要快捷、容易得多。下面先介绍一下不饱和度的概念：

设有机物分子中碳原子数为n，当氢原子数等于2n+2时，该有机物是饱和的，小于2n+2时为不饱和的，每少两个氢原子就认为该有机物分子的不饱和度为1。

分子中每产生一个C=C或C=O或每形成一个环，就会产生一个不饱和度，每形成一个C≡C，就会产生两个不饱和度，每形成一个苯环就会产生4 个不饱和度。

例⒉烃A和烃B的分子式分别为C1134H1146和C1398H1278，B的结构跟A相似，但分子中多了一些结构为的结构单元。

则B分子比A分子多了33 个这样的结构单元。(注：构成高分子链并决定高分子结构以一定方式连接起来的原子组合称之为结构单元。）

参考资料来源：百度百科-烷烃

参考资料来源：百度百科-同分异构体

Answer 2

本质上就是一个无标号无根树带度数限制的计数问题.
将问题一般化：求
n
个点的无标号无根树的个数,
且每个点的度数不超过m。
烷基
(有根树)：首先考虑计算烷基的个数
(即有根树)。
考虑暴力
DP.。设状态为 f(i,j,k)f(i,j,k)，表示当前共有 ii个点。
最大的子树大小为 jj，且根的度数为 kk。对于状态 f(i,j,k)f(i,j,k)，通过枚举最大子树的个数
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)。
组合数是用来可重集计数的。这是O(n3m2)O(n3m2)的。
显然可以前缀和优化，但是空间撑不住。还可以做得更好。考虑如何省掉 jj 这一维状态。即设状态为 f(i,j)f(i,j)。表示当前共有 ii 个点，根的度数为 kk。
考虑
DP
的一个技巧:
强行规定转移顺序。即，先 1...n1...n 枚举
size，表示强制用最大子树大小为
size
的情形来转移。
不妨设s=∑m−1k=0f(size,k)s=∑k=0m−1f(size,k)，那么对于一个 f(i,j)f(i,j)。
再枚举一个最大子树
(即子树大小为
size
的子树)
的个数
k。
我们便有转移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。(当然 nn 必须要是偶数)
很多无根树同构的问题就可以通过重心转化为有根树同构。烷烃就可以这么计数。因为我们可以在
DP
烷基的时候。
强制size<n2size<n2(注意是小于)，这样求出的 f(i,j)f(i,j) 就是点数为 ii 且重心度数为 jj 的无根树个数。那么答案为：∑mk=0f(n,k)+[n(mod2)=0]{∑m−1k=0f(n2,k)+12}。
扩展资料：
烷系同分异构体结构特征：
在烃及其含氧衍生物的分子式中必然含有这样的信息：该有机物的不饱和度。利用不饱和度来解答这类题目往往要快捷、容易得多。下面先介绍一下不饱和度的概念：
设有机物分子中碳原子数为n，当氢原子数等于2n+2时，该有机物是饱和的，小于2n+2时为不饱和的，每少两个氢原子就认为该有机物分子的不饱和度为1。
分子中每产生一个C=C或C=O或每形成一个环，就会产生一个不饱和度，每形成一个C≡C，就会产生两个不饱和度，每形成一个苯环就会产生4
个不饱和度。
例⒉烃A和烃B的分子式分别为C1134H1146和C1398H1278，B的结构跟A相似，但分子中多了一些结构为的结构单元。
则B分子比A分子多了33
个这样的结构单元。(注：构成高分子链并决定高分子结构以一定方式连接起来的原子组合称之为结构单元。）
参考资料来源：搜狗百科-烷烃
参考资料来源：搜狗百科-同分异构体

Answer 3

烃构造异构体数目
碳原子数 异构体数 碳原子数 异构体数
1 1
2 1
3 1
4 2
5 3
6 5
7 9
8 18
9 35
10 75
11 4347
12 366319

没有通式呃...
如果你求出来了，这届的诺贝尔化学奖大概就素你的了。本回答被提问者采纳

Answer 4

这是个代数或者图论问题，和化学关系似乎不是太大。直接在OEIS oeis.org 查阅序列1,1,1,2,3,5,9或者直接查询A000602就是n碳烷烃同分异构体的数量序列a(n)，这里有历年对该序列研究的结论和论文，其中一部分可以查看，并没有通项以及递推，只有算法，那目前应该就是没有了。这种类似的问题在OEIS里可能有十几万或者几十万个，就算是放在关系比较大的数学里可能也就是几篇论文...离诺贝尔奖还是有很大一段距离的...