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

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$是没有任何问题的。