烷烃同分异构体的计数公式

282842712474

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

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

不知道大家有没有什么有效的方法？

wayne

看链接 http://oeis.org/A000602
里面有公式

mjs1wh

跟我提过的百变魔尺问题类似

282842712474

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

那就是说，这等价于一个递推？
当n为偶数时可以递推，当n是奇数时，就只能暴力？

KeyTo9_Fans

数列A000602

http://oeis.org/A000602

里面有关键字"easy"：

it is very easy to produce terms of sequence

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

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

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

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

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

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

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

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

最好能说明原理。

282842712474

我也觉得不是一个简单的事情，除非真的能够有一个递推公式

wayne

0, 1
1, 1
2, 1
3, 1
4, 2
5, 3
6, 5
7, 9
8, 18
9, 35
10, 75
11, 159
12, 355
13, 802
14, 1858
15, 4347
16, 10359
17, 24894
18, 60523
19, 148284
20, 366319
21, 910726
22, 2278658
23, 5731580
24, 14490245
25, 36797588
26, 93839412
27, 240215803
28, 617105614
29, 1590507121
30, 4111846763
31, 10660307791
32, 27711253769
33, 72214088660
34, 188626236139
35, 493782952902
36, 1295297588128
37, 3404490780161
38, 8964747474595
39, 23647478933969
40, 62481801147341
41, 165351455535782
42, 438242894769226
43, 1163169707886427
44, 3091461011836856
45, 8227162372221203
46, 21921834086683418
47, 58481806621987010
48, 156192366474590639
49, 417612400765382272
50, 1117743651746953270
51, 2994664179967370611
52, 8031081780535296591
53, 21557771913572630901
54, 57919180873148437753
55, 155745431857549699124
56, 419149571193411829372
57, 1128939578361332867936
58, 3043043571906827182530
59, 8208615366863753915949
60, 22158734535770411074184
61, 59858097847706865855186
62, 161805725349297357221898
63, 437671691526158936922623
64, 1184616185385310843585573
65, 3208285066181475821271463
66, 8694130712024868414002815
67, 23573796134448175745408811
68, 63955159527348138708694312
69, 173603007393950249896865875
70, 471484798515330363034639871
71, 1281151315764638215613845510
72, 3482965749140691245110434511
73, 9473447386804490449091871124
74, 25779306238954404972323916397
75, 70183211512214096492433058105
76, 191156381393249393027319384769
77, 520874195248906781713044332539
78, 1419908915343952137338409797325
79, 3872282575137005474139119076135
80, 10564476906946675106953415600016
81, 28833609436277333169440806135431
82, 78725585464391037293036629979444
83, 215027809474796675607407513633870
84, 587531723826577193455385789266377
85, 1605913778494711520354663202536756
86, 4391002908093323425994602631972445
87, 12010257907756938974208750945664835
88, 32861295558120887536942123568548502
89, 89940959024891576997396491928932689
90, 246245150242821439632304475956113295
91, 674391606297983432514229725117306224
92, 1847515048012613337782670842346319120
93, 5062818112121161180862827915688625902
94, 13877857529584521384324419956411729295
95, 38051836070803837001309074456088423358
96, 104363664561059273927704242814298678658
97, 286312976836850192359345859166390622180
98, 785684759853087702778573182234297830503
99, 2156596319845084996862701478402986311496
100, 5921072038125809849884993369103538010139
101, 16260750014333666174953055376699249561110
102, 44667063168726812052821334495766769690630
103, 122726610195426301690448676841677827340780
104, 337281538963751874669853952178948219200633
105, 927143441542280244466720172757699607129825
106, 2549176520305910764377448963173035784835631
107, 7010510656300876673813654064741809461787182
108, 19283877336110239907079044091958051661009951
109, 53055727810105880736027950213934519705620559
110, 146002972524313232817393491844985704938385801
111, 401865724190508834753025926637435418813476039
112, 1106339625432222709435767174129826811545391101
113, 3046369875968510015403046201590835240153395100
114, 8389999420170754836800638580300552381250693062
115, 23111326593011774543116815302964652139347135182
116, 63675155467360117136901070528242608498818046250
117, 175467195960062612437322237574246321515725845634
118, 483616671898832299071277369263305813784565460114
119, 1333167312321418940566764416056977442040495550342
120, 3675740183950426011078357941139728051663026172228
121, 10136322901774027447848977748665383292736169662267
122, 27956983197937526275999613945221497078279509595407
123, 77121096978813982358935411851692069578533009193138
124, 212778592638033483022781655638827961970402357080215
125, 587155794584829621068447884048323985962957796104395
126, 1620497362318232091081355117667505915417499978679013
127, 4473132502312622821884079561929897829404710575328024
128, 12349306792492607803837161096610238756912653878568775
129, 34098849774876383478036291434385545792965491914980650
130, 94167748474814466028838037996326649316233175269577493
131, 260093170948828891650104553710684162327855828421145690
132, 718487205759724277833835055443909476145495116155508155
133, 1985050220521088907210323840127550973214943015739291120
134, 5485110653386099899275645856977233423965042141295771502
135, 15158624968755754576600389921905653584106659889930620820
136, 41898053824932615440265041900412507427220728337249680527
137, 115820822448502452349822520317304132018285539473087897141
138, 320211802888589798701825810680319271475504997973219083170
139, 885411355238188116465394365370757710295372148438998022826
140, 2448550585524918609600214967948504177437555812600018440773
141, 6772180336728084537425567078328320492989943976904644119200
142, 18732796033402227075307540055538834651333956120072379687678
143, 51823958523558404531622255138725304201359354985976024954747
144, 143387634030485523461662580179416231260007790242619239696168
145, 396775836020295064920040342935953476579230225268967120945252
146, 1098070975453594757891511609218085888434254839495604326720679
147, 3039251105982158526063018965393900608357891201531016545453671
148, 8413041613874240075848233530979949485087059914285837491890647
149, 23291051500594069758631194545655502320903778728677961917787017
150, 64487285324785805685734825467573942213924157583096655274158296
151, 178569541961158786360447600422369518262867694211679827307797522
152, 494525085028771691070376002671999818542495469214503552543494392
153, 1369671107847363840368349527801907625890550280754690871159384167
154, 3793941909035282970536126899217159922244816989321008990552343933
155, 10510197366726219419291185594221700080820692107164072063617583537
156, 29118988780427095392911694296588496006042150251385271606702314123
157, 80683801316548713731547508195369620842564695928190934573122040053
158, 223583881196691039626561929582827819978293196688915654006262185620
159, 619638153674192054430980737083649826660231642062541457264064352590
160, 1717428978037773119953669826811378686605009454833429087085211111817
161, 4760601845949152288761851253868434642647478893273231351009713026471
162, 13197353449186709568929592710369551730672357721629256541119049584662
163, 36589226826424289787166608629764201634396432211204018812233928108927
164, 101451975263926040804307438557581821336425438886780992752450611791029
165, 281324901033788598583154170205263556814795889090791609969956549076553
166, 780181677818281299965193432627955631078491817302716837810578348379410
167, 2163828038323756757063639945018570904120396578192324738853110253083851
168, 6001899167570139611127915072874671685163847392112466633395193150607161
169, 16649191065671323727576273232609293462550308875754570697371028619095529
170, 46188686972056579073145176280276791118176099297131728121378351698216964
171, 128149137125681447665302588425507023489080631426025859378879991574150361
172, 355576383032176188837060897590191000068058505378256432541548821711409736
173, 986703913063443346422020725722084251185909113284392827422830038792419867
174, 2738275183964917202164682060710234556685852044781624370789938274187242387
175, 7599818348156354735525837090092498330135165342551619766604085368593605623
176, 21094284799140605474267783653778252494175708547669907184929527663028371844
177, 58554660677719531288883019197284429180673377561888244491058170393359945984
178, 162552183133868639189244204285356619593212307470997836346642760606493409411
179, 451292826786530619879633220482642976940485477290114448603416892241141577694
180, 1253019870825476025726441067676567248038950763298814178748038046446512128926
181, 3479293084378459187212303139960535018989517537846033787292960498791544468857
182, 9661781855977284524013799278118239872342899149756408496918889491272019198160
183, 26832197158239597797570968340612728947891256166650480273266227097169558934791
184, 74522545727244539603451333395337695567614066525612042720018110555143893455632
185, 206990881176753531116559188573370889805581604324744059300494333307748123498957
186, 574971719221297425559348824161112797452658996937464320320048053830834065076638
187, 1597250942564001477500533605167309927398304330031144648098072721512668593957703
188, 4437423571982333312534972159110678450135834859468229274326790786916695731276497
189, 12328758711422329105019389982539560951228986597668702145097956175468519348920309
190, 34256124585721478074980980873512523523896822875906637442595527046990665266761523
191, 95189094589104790904556217884090558824685828617516319665565748564984723369457220
192, 264524521940855272106937702820301986845470010150944446148610489622177560655580196
193, 735146927788110318878638054407335543366855876665936464594690408421993895145574507
194, 2043202995476015462049187462882169976289343296164934404442378707876446055277665852
195, 5679076882963913929265887525377096781591407289261632655627568444557125995319535956
196, 15786016263625679649343179544010857226174369384245579060916786714528288038933116607
197, 43882930188633901470015828734437451959746697520345645823789728504039719238235284266
198, 121996306076853365751053531202168307620916572983606780123661900035869303555630148063
199, 339176261988518728096836182493660862745709169352281541101577697702699073887422989905

282842712474

12# wayne



太牛逼了

wayne

13# 282842712474
是软件牛。
用maple算的，
3楼的那个链接里有现成的代码：
http://oeis.org/A000602/a000602.txt
下面给出了n到 500  的解。
1-500.txt (55.47 KB, 下载次数: 6)

2011-3-13 20:12 上传

点击文件名下载附件

Lwins_G

参见：http://wenku.baidu.com/view/5516a6563c1ec5da50e27018.html

基本按照这个思路，只不过略有小变动。在PC上跑到$n=1000$是没有任何问题的。