道路连接
6座城市，要求任何两座城市之间都要有道路连接(允许通过其他城市中转)，问有多少种不同的连接方法？ 提示：
2座城市有1种连接方法，
3座城市有4种连接方法，
4座城市有38种连接方法，
5座城市有728种连接方法，
6座城市的连接方法是个5位数，具体数字我还真算不出来！ 26704 网上搜索楼主的数据，得到以下结果。
http://oeis.org/A001187/b001187.txt
0 1
1 1
2 1
3 4
4 38
5 728
6 26704
7 1866256
8 251548592
9 66296291072
10 34496488594816
11 35641657548953344
12 73354596206766622208
13 301272202649664088951808
14 2471648811030443735290891264
15 40527680937730480234609755344896
16 1328578958335783201008338986845427712
17 87089689052447182841791388989051400978432
18 11416413520434522308788674285713247919244640256
19 2992938411601818037370034280152893935458466172698624
20 1569215570739406346256547210377768575765884983264804405248
21 1645471602537064877722485517800176164374001516327306287561310208
22 3450836972295011606260171491426093685143754611532806996347023345844224
23 14473931784581530777452916362195345689326195578125463551466449404195748970496
24 121416458387840348322477378286414146687038407628418077332783529218671227143860518912
25 2037032940914341967692256158580080063148397956869956844427355893688994716051486372603625472
26 68351532186533737864736355381396298734910952426503780423683990730318777915378756861378792989392896
27 4586995386487343986845036190980325929492297212632066142611360844233962960637520118252235915249481987129344
28 615656218382741242234508631976838051282411931197630362747033724174222395343543109861028695816566950855890811486208
29 165263974343528091996230919398813154847833461047104477666952257939564080953537482898938408257044203946031706125367800496128
30 88725425253946309579607515290733826999038832348034303708272765654674479763074364231597119435621862686597717341418971119460584259584
31 95268202520385449790227094691687836722278710954949736428196756305746453532341035148366531266372862653739009088659598082113309304400438624256
32 204586909944926298207861553173799965921067126517774603507480126827588404754232387878919170016875623577048105576068684204467114231315623298308706926592
33 878694093745349914731889727208157807680003171098920968952145189548012830636076748530741378813207711246134152874638123892704663922045456803250047261786444398592
34 7547924819767483287594694542205326068855891655862820018679189530528628155893698967796630219069788201405972928386025644172169109953194652176102437455457970998547197198336
35 129672361263353660216004848405397154497075914498088480263529787446798464815868889966259599220355751574955667311875199310825316757090836792227021420332597263591744872066219249762304
36 4455508410978470003213152055317479855991723332650114280703483486331017198541367912550307040027205813596014620050254013798901452927850711294962075802234712748298505435020109941966616435621888
37 306180206751230090930313674296749763317292930219833760674864513181351793147422958983304199997791891477494238067606067864147691875149221011750587805454462256284237767964756224079011437145490032917741568
38 42081087200752140195116730773102052524009718837902621183664949269856744858385083976643391056195246283737633254986683196506525739229100562028667655727478159896469450443625002559600024194689577683162985133342982144
39 11567161173227696466220457283329529101751379197153495724502457893891478829937149071434453800538222228465001645119757350054456753856800058471020811256328606811309950183460999195585736337722940242137574318489684508433109221376
40 6359114105601017351375465630036218352726964545083913061809864302427743340641476112983635151514041188995967358659226381513838435962182371853731281705837980150384424607870600516842502175922529566100381861494213531965265765000213275082752
41 6991919901710702396948942815573257427744311018004588489866790612959056357721564695830748688904669995738081555372234543689358610668809196548322563461899302515136978058611651369187392760821440875968116963440793130046454847480988052748303630065467392
42 15375394465098365435098131065240195173750887603455691084898736566282027607324662718653380384318359771738669872579070523864682029424324656980343742654131923883848453279046887366030428581980234722002609397042921130626427482776226373410811403774539364168814821376
43 67621699984704009571087635348261788647460730411971168452281282746962798999895717916292043207408657855232972628889146834646084600650980317820241001687549180689983916950502853108787655643356237905731863505593837387547463783553663104052737827256888296815897621036524900450304
44 594806763388137870319868932592503661181879874998563369872608575294390559331829154567126246824792929668641338543467328561106071308881273503814138669414317911219402066314092130747535752627679688399993515689603622744525243838714230998285264232171322066511990049433899384262102238508351488
45 10463951242026625501784363274596214619943325701401522513836100192928357652762255136769619473700702276949844553770347735730521468871772581157963359677917896206658361141741863952608795675733168160935829452838892433190712974942475048711118429563334205007874224852816312589287727030417085994911901155328
46 368167554019320956145827247050509963076959450983143444578072117098399777382502455552633802915095691807005512740224345254318634273382517137823997743877511866703540358482988273801636313118482363728678083259725882776454656507629131210255280738244476783496709369751571318821222548711309212127848471930415455355797504
47 25907488423318455274080473672019976083009208996271003791416218114322853582878049179546761491016196610119349803222490393175612695149120594742502991139032865749979736985340247224801444473477196529096332604358326020598992443433363048888842556850935198901353471923472154386768107635993449205071378228596636214817388982756553261056
48 3646154850293767810262810894999553363628589110640769385457986485984919161321600546344826908488589572223649058216506920510786720770519258252897810249930214560211056122090333850686659187132094273815095247787669459869137017783625755540375408272361426098383313551230976557640520636974573279383371834513917048967432546435999569365350430111956992
49 1026301351570055077911628972867042177680735585635225345203536190737910863123857244548313982876228994987864700400759811456244128889754306386459557887432298148719591734971030611474690885904247396313959818854940592795291449937598794070517570167551607950979266237997797283563645242105244737520881371410960067902176629829514256225641238164014573644333472284672
50 577756298062641319815321284633539861082132919998722885657507672188606317696301924134068233518707877841769252356274834883678320922291785288952259324960085933885572481476441044041666245632947630667669900623389069655523344952222114179660086674251300523449279256078271770682664276058349275922600493471476178420154378012048571333436567365397136152469165480980158369042006016 如果把这 `n` 个城市看成 `n` 个顶点，那么题目可转化为求 `n` 个顶点构成的无向连通图个数 `c_n`.
考虑其对偶情况，记 `n` 个顶点构成的非连通图的个数 `d_n`
已知 `n` 个顶点可构成的简单图个数为 `s_n=2^{C_n^2}=2^{\frac{n(n-1)}{2}}` 种，且有\考虑非连通图，它可以分割成 `k\;(1\leqslant k \leqslant n-1)` 个顶点构成的连通分量，以及剩下 `n-k` 个顶点构成简单图 `s_{n-k}`. 显然，该连通分量随后不能作为 `n-k` 个顶点构成的简单图的连通分量再次出现，否则会重复计数问题。因此只要 `k` 个顶点的连通分量必须都包含某个共同的顶点，这样就不会出现重复计数问题。于是这样的连通分量选择方案有 `C_{n-1}^{k-1}` 种，而每种选择中构成的连通图个数为 `c_k`， 因此有递推关系\代入上面的关系得到\根据定义 `c_1=1,c_2=1`，从而可得 `c_6=26704.` kastin 发表于 2017-10-1 17:47
如果把这 `n` 个城市看成 `n` 个顶点，那么题目可转化为求 `n` 个顶点构成的无向连通图个数 `c_n`.
考虑其 ...
谢谢aimisiyou！谢谢 KeyTo9_Fans！谢谢kastin！
当n足够大时，Cn=2^(n(n-1)/2)-n×2^((n-1)(n-2)/2)
斗胆求助：(Sn-Cn)÷2^((n-1)(n-2)/2)是否在向n靠拢？ 本帖最后由 kastin 于 2017-10-6 17:21 编辑
王守恩 发表于 2017-10-6 08:18
谢谢aimisiyou！谢谢 KeyTo9_Fans！谢谢kastin！
当n足够大时，Cn=2^(n(n-1)/2)-n×2^((n-1)(n-2)/2)
...
楼主的猜想是，当 `n\to \infty`，有 `\D c_n\sim 2^{\frac{n(n-1)}{2}}-n2^{\frac{(n-1)(n-2)}{2}}`，即 `\D(s_n-c_n)/2^{\frac{(n-1)(n-2)}{2}}=d_n/2^{\frac{(n-1)(n-2)}{2}}\sim n`
从定义上来讲，“连通”指的是相互连结的点通过不断缩并，最终只剩一个孤立的“点“(此处暂称之为聚合点），故“非连通”指的是极大连通分量之间是不连通的——也就是说，若将连通分量收缩为一个聚合点，那么这些聚合点的个数至少为2个。
为叙述方便，称孤立顶点为平凡聚合点，非孤立顶点的连通分量收缩后的点为非平凡聚合点。
因此非连通图可视为至少有两个聚合点的图，分为两类情形：第一种是只存在非平凡聚合点；第二种是至少存在一个平凡聚合点。
考虑第二种情形：平凡聚合点有 `n` 种选择，剩下 `n-1` 个点构成简单图（即形成一个或多个聚合点），故种数可以用 `n2^{C_{n-1}^2}` 来估计。当然这会存在重复计数，故估计值偏大。
所以，若能证明随着 `n` 递增，第二类情形估计中的重复计数越来越接近第一类的计数，则猜想成立。
kastin 发表于 2017-10-6 16:51
楼主的猜想是，当 `n\to \infty`，有 `\D c_n\sim 2^{\frac{n(n-1)}{2}}-n2^{\frac{(n-1)(n-2)}{2}}`， ...
例：
(2^( 7 ×8 /2 ) - C( 8 ))÷2^( 7 ×6 /2)=8.052284241
(2^( 8 ×9 /2 ) - C( 9 ))÷2^( 8 ×7 /2)=9.027070045
(2^( 9 ×10/2) - C(10))÷2^( 9 ×8 /2)=10.01002229
(2^(10×11/2) - C(11))÷2^(10×9 /2)=11.00316553
(2^(11×12/2) - C(12))÷2^(11×10/2)=12.00095822
(2^(12×13/2) - C(13))÷2^(12×11/2)=13.00029222
(2^(13×14/2) - C(14))÷2^(13×12/2)=14.00008995
8.0522842407226562500000000000000000000000000000000
9.0270700454711914062500000000000000000000000000000
10.010022291913628578186035156250000000000000000000
11.003165525682561565190553665161132812500000000000
12.000958229163146029350173193961381912231445312500
13.000292221763118230559719279426644789054989814758
14.000089903500021390665865707661486005974893487291
15.000027624237456815526968268049272934357846187581
16.000008426410498591863892697229390994352806551532
17.000002546380489822930135128478315746326307243421
18.000000762063060656877205479509226290854441433355
19.000000225944769640879391336758703432659053191222
20.000000066408487168716424114982731720567118671215
21.000000019362030283649772031376525045675082304198
22.000000005603706314883481708873104052095846720529
23.000000001610899509179799931763401812437795918303
24.000000000460231973638512602317262632959155546632
25.000000000130743978300759439055418685760658333874
26.000000000036948830119278463204593046672849068155
27.000000000010391776705278218125212308980371801402
28.000000000002909685510356016509299209245910287411
29.000000000000811352872460011248771509415445718111
30.000000000000225375546026478579635141881170137644
31.000000000000062380695237054151166056982096427097
32.000000000000017208462458960481100398440691460750
33.000000000000004732326435783024509380987882020296
34.000000000000001297573272417383558518730035202939
35.000000000000000354805176806910088941415178353312
36.000000000000000096765046124788299264961071964185
37.000000000000000026325784313265576338557218060634
38.000000000000000007145569986709604233180724014047
39.000000000000000001935258532322193847928474413692
40.000000000000000000523042845774382003951756217029
41.000000000000000000141083925394067755792560125976
42.000000000000000000037984133744602731251004511347
43.000000000000000000010208235941745155297366516995
44.000000000000000000002738795008469457736147767223
45.000000000000000000000733605805800000686550870270
46.000000000000000000000196196901545675943003228562
47.000000000000000000000052393490752924312952882242
48.000000000000000000000013971597534010699175931850
49.000000000000000000000003720697169369325207932003
50.000000000000000000000000989547119511219994467720 本帖最后由 kastin 于 2017-10-10 18:30 编辑
第一类的非连通图（只存在非平凡聚合点）个数为 `t_n`，则\
页:
[1]