数学研发论坛

 找回密码
 欢迎注册
查看: 5252|回复: 19

[提问] 烷烃同分异构体的计数公式

[复制链接]
发表于 2011-2-16 15:39:44 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
本帖最后由 hujunhua 于 2011-2-18 11:15 编辑

分子式为$C_n H_{2n+2}$的烷烃,有没有一条公式来计算一下它的同分异构体数?
(仅仅考虑树状,不考虑环)

我试着分析了一下,发现这是一个极其复杂的排列组合问题,需要考虑的情况很多。

不知道大家有没有什么有效的方法?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-2-16 15:49:51 | 显示全部楼层
自己搜一下,这不是新问题。

点评

有多少种同分异构体—波利亚定理  发表于 2014-8-9 16:55
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-2-16 16:09:39 | 显示全部楼层
看链接 http://oeis.org/A000602
里面有公式
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-2-17 20:50:38 | 显示全部楼层
跟我提过的百变魔尺问题类似
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-2-17 21:11:16 | 显示全部楼层
4# wayne


抱歉,我看的不大懂...能够解释下吗?

a(n) = A010372(n) + A010373(n/2) for n even, a(n) = A010372(n) for n odd.

这句话的具体运算是怎样的?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-2-17 22:29:25 | 显示全部楼层
a(2n)=A010372(2n)+A010373(n)
a(2n+1)=A010372(2n+1)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-2-18 10:57:06 | 显示全部楼层
我说的是A010372算符的意思…
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-2-18 11:11:06 | 显示全部楼层
这是数组名,按编号命名的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-2-18 17:02:50 | 显示全部楼层
那就是说,这等价于一个递推?
这样的话偶数可以递推..
那么当n是奇数是,不就是只能暴力?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-2-26 13:03:58 | 显示全部楼层
数列A000602

http://oeis.org/A000602

里面有关键字"easy":

it is very easy to produce terms of sequence

可是我觉得要生成这个数列一点也不"easy"。

我高中的时候设计了一个算法,运行一个晚上,只计算到$n=19$。

大一的时候改进了该算法,运行一个晚上,计算到$n=35$。

现在觉得该算法仍然可以改进,但最多只能计算到$n=45$左右。

我觉得这个问题之所以困难,是因为我的算法的执行时间是指数级增长的。

至今还没有想到多项式时间的算法。

看到该数列居然有关键字"easy",觉得很不可思议。

不知道哪位大牛可以给出一个多项式时间的算法呢?

最好能说明原理。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-10-19 17:26 , Processed in 0.071341 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表