数学研发网设为首页收藏本站

数学研发论坛

 找回密码
 欢迎注册
查看: 923|回复: 12

[求助] 道路连接

[复制链接]
发表于 2017-9-28 08:38:41 | 显示全部楼层 |阅读模式

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

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

x
6座城市,要求任何两座城市之间都要有道路连接(允许通过其他城市中转),
问有多少种不同的连接方法?   提示:
2座城市有1种连接方法,
3座城市有4种连接方法,
4座城市有38种连接方法,
5座城市有728种连接方法,
6座城市的连接方法是个5位数,具体数字我还真算不出来!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-9-28 15:12:25 | 显示全部楼层
26704

点评

太好了!谢谢aimisiyou!7座城市,8座城市,9座城市,可以计算吗?  发表于 2017-9-28 17:26
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2017-9-28 21:05:50 | 显示全部楼层
网上搜索楼主的数据,得到以下结果。

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
复制代码

点评

谢谢KeyTo9_Fans!看看这些神奇的数字!我知道自己算错了!  发表于 2017-9-29 04:20
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-10-1 17:47:42 | 显示全部楼层
如果把这 `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-2 05:17
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-10-6 08:18:25 | 显示全部楼层
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靠拢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-10-6 16:51:13 | 显示全部楼层
本帖最后由 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` 递增,第二类情形估计中的重复计数越来越接近第一类的计数,则猜想成立。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-10-6 19:39:50 | 显示全部楼层
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

点评

数值不能说明问题,如果能的话,哥德巴赫猜想就不叫猜想了。  发表于 2017-10-6 19:58
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-10-10 15:05:56 | 显示全部楼层
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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-10-10 18:29:56 | 显示全部楼层
本帖最后由 kastin 于 2017-10-10 18:30 编辑

第一类的非连通图(只存在非平凡聚合点)个数为 `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.\]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2017-11-24 08:06 , Processed in 0.221317 second(s), 22 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

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