道路连接

王守恩

6座城市，要求任何两座城市之间都要有道路连接(允许通过其他城市中转)，
问有多少种不同的连接方法？   提示：
2座城市有1种连接方法，
3座城市有4种连接方法，
4座城市有38种连接方法，
5座城市有728种连接方法，
6座城市的连接方法是个5位数，具体数字我还真算不出来！

aimisiyou

26704

KeyTo9_Fans

网上搜索楼主的数据，得到以下结果。

http://oeis.org/A001187/b001187.txt

1. 0 1
   
2. 1 1
   
3. 2 1
   
4. 3 4
   
5. 4 38
   
6. 5 728
   
7. 6 26704
   
8. 7 1866256
   
9. 8 251548592
   
10. 9 66296291072
    
11. 10 34496488594816
    
12. 11 35641657548953344
    
13. 12 73354596206766622208
    
14. 13 301272202649664088951808
    
15. 14 2471648811030443735290891264
    
16. 15 40527680937730480234609755344896
    
17. 16 1328578958335783201008338986845427712
    
18. 17 87089689052447182841791388989051400978432
    
19. 18 11416413520434522308788674285713247919244640256
    
20. 19 2992938411601818037370034280152893935458466172698624
    
21. 20 1569215570739406346256547210377768575765884983264804405248
    
22. 21 1645471602537064877722485517800176164374001516327306287561310208
    
23. 22 3450836972295011606260171491426093685143754611532806996347023345844224
    
24. 23 14473931784581530777452916362195345689326195578125463551466449404195748970496
    
25. 24 121416458387840348322477378286414146687038407628418077332783529218671227143860518912
    
26. 25 2037032940914341967692256158580080063148397956869956844427355893688994716051486372603625472
    
27. 26 68351532186533737864736355381396298734910952426503780423683990730318777915378756861378792989392896
    
28. 27 4586995386487343986845036190980325929492297212632066142611360844233962960637520118252235915249481987129344
    
29. 28 615656218382741242234508631976838051282411931197630362747033724174222395343543109861028695816566950855890811486208
    
30. 29 165263974343528091996230919398813154847833461047104477666952257939564080953537482898938408257044203946031706125367800496128
    
31. 30 88725425253946309579607515290733826999038832348034303708272765654674479763074364231597119435621862686597717341418971119460584259584
    
32. 31 95268202520385449790227094691687836722278710954949736428196756305746453532341035148366531266372862653739009088659598082113309304400438624256
    
33. 32 204586909944926298207861553173799965921067126517774603507480126827588404754232387878919170016875623577048105576068684204467114231315623298308706926592
    
34. 33 878694093745349914731889727208157807680003171098920968952145189548012830636076748530741378813207711246134152874638123892704663922045456803250047261786444398592
    
35. 34 7547924819767483287594694542205326068855891655862820018679189530528628155893698967796630219069788201405972928386025644172169109953194652176102437455457970998547197198336
    
36. 35 129672361263353660216004848405397154497075914498088480263529787446798464815868889966259599220355751574955667311875199310825316757090836792227021420332597263591744872066219249762304
    
37. 36 4455508410978470003213152055317479855991723332650114280703483486331017198541367912550307040027205813596014620050254013798901452927850711294962075802234712748298505435020109941966616435621888
    
38. 37 306180206751230090930313674296749763317292930219833760674864513181351793147422958983304199997791891477494238067606067864147691875149221011750587805454462256284237767964756224079011437145490032917741568
    
39. 38 42081087200752140195116730773102052524009718837902621183664949269856744858385083976643391056195246283737633254986683196506525739229100562028667655727478159896469450443625002559600024194689577683162985133342982144
    
40. 39 11567161173227696466220457283329529101751379197153495724502457893891478829937149071434453800538222228465001645119757350054456753856800058471020811256328606811309950183460999195585736337722940242137574318489684508433109221376
    
41. 40 6359114105601017351375465630036218352726964545083913061809864302427743340641476112983635151514041188995967358659226381513838435962182371853731281705837980150384424607870600516842502175922529566100381861494213531965265765000213275082752
    
42. 41 6991919901710702396948942815573257427744311018004588489866790612959056357721564695830748688904669995738081555372234543689358610668809196548322563461899302515136978058611651369187392760821440875968116963440793130046454847480988052748303630065467392
    
43. 42 15375394465098365435098131065240195173750887603455691084898736566282027607324662718653380384318359771738669872579070523864682029424324656980343742654131923883848453279046887366030428581980234722002609397042921130626427482776226373410811403774539364168814821376
    
44. 43 67621699984704009571087635348261788647460730411971168452281282746962798999895717916292043207408657855232972628889146834646084600650980317820241001687549180689983916950502853108787655643356237905731863505593837387547463783553663104052737827256888296815897621036524900450304
    
45. 44 594806763388137870319868932592503661181879874998563369872608575294390559331829154567126246824792929668641338543467328561106071308881273503814138669414317911219402066314092130747535752627679688399993515689603622744525243838714230998285264232171322066511990049433899384262102238508351488
    
46. 45 10463951242026625501784363274596214619943325701401522513836100192928357652762255136769619473700702276949844553770347735730521468871772581157963359677917896206658361141741863952608795675733168160935829452838892433190712974942475048711118429563334205007874224852816312589287727030417085994911901155328
    
47. 46 368167554019320956145827247050509963076959450983143444578072117098399777382502455552633802915095691807005512740224345254318634273382517137823997743877511866703540358482988273801636313118482363728678083259725882776454656507629131210255280738244476783496709369751571318821222548711309212127848471930415455355797504
    
48. 47 25907488423318455274080473672019976083009208996271003791416218114322853582878049179546761491016196610119349803222490393175612695149120594742502991139032865749979736985340247224801444473477196529096332604358326020598992443433363048888842556850935198901353471923472154386768107635993449205071378228596636214817388982756553261056
    
49. 48 3646154850293767810262810894999553363628589110640769385457986485984919161321600546344826908488589572223649058216506920510786720770519258252897810249930214560211056122090333850686659187132094273815095247787669459869137017783625755540375408272361426098383313551230976557640520636974573279383371834513917048967432546435999569365350430111956992
    
50. 49 1026301351570055077911628972867042177680735585635225345203536190737910863123857244548313982876228994987864700400759811456244128889754306386459557887432298148719591734971030611474690885904247396313959818854940592795291449937598794070517570167551607950979266237997797283563645242105244737520881371410960067902176629829514256225641238164014573644333472284672
    
51. 50 577756298062641319815321284633539861082132919998722885657507672188606317696301924134068233518707877841769252356274834883678320922291785288952259324960085933885572481476441044041666245632947630667669900623389069655523344952222114179660086674251300523449279256078271770682664276058349275922600493471476178420154378012048571333436567365397136152469165480980158369042006016

复制代码

kastin

如果把这 `n` 个城市看成 `n` 个顶点，那么题目可转化为求 `n` 个顶点构成的无向连通图个数 `c_n`.
考虑其对偶情况，记 `n` 个顶点构成的非连通图的个数 `d_n`
已知 `n` 个顶点可构成的简单图个数为 `s_n=2^{C_n^2}=2^{\frac{n(n-1)}{2}}` 种，且有\[s_n=c_n+d_n\]考虑非连通图，它可以分割成 `k\;(1\leqslant k \leqslant n-1)` 个顶点构成的连通分量，以及剩下 `n-k` 个顶点构成简单图 `s_{n-k}`. 显然，该连通分量随后不能作为 `n-k` 个顶点构成的简单图的连通分量再次出现，否则会重复计数问题。因此只要 `k` 个顶点的连通分量必须都包含某个共同的顶点，这样就不会出现重复计数问题。于是这样的连通分量选择方案有 `C_{n-1}^{k-1}` 种，而每种选择中构成的连通图个数为 `c_k`， 因此有递推关系\[d_n=\sum_{k=1}^{n-1}C_{n-1}^{k-1}c_ks_{n-k}\]代入上面的关系得到\[c_n=2^{\frac{n(n-1)}{2}}-\sum_{k=1}^{n-1}C_{n-1}^{k-1}2^{\frac{(n-k)(n-k-1)}{2}}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 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

第一类的非连通图（只存在非平凡聚合点）个数为 `t_n`，则\[t_n=d_n-\sum_{k=1}^{n-2}C_n^k(c_{n-k}+t_{n-k}),with~t_1=t_2=t_3=0.\]