当边出现的概率达到多少时，图就连通了？

KeyTo9_Fans

$N$个顶点的完全图有$(N*(N-1))/2$条边。 现在假设这$(N*(N-1))/2$条边都是不确定的。

它们有$p$的概率出现，$(1-p)$的概率消失，并且相互独立。 我们用$c(p)$来表示整个图连通的概率，用$P$来表示满足$c(p)=0.5$的$p$值。 对于不同的$N$，$P$的值是不一样的。 我们用$P(N)$来表示顶点数为$N$时对应的$P$值。 给定$N$，求$P(N)$的值。

KeyTo9_Fans

下面是$N<=3$的结果： $P(1)$不存在。 $P(2)=0.5$ $P(3)=0.5$ 希望可以精确计算到$P(10)$，并找到$P(N)$的近似公式。

056254628

N=4，一共有6条边。 不连通的情况： 0条边被选中有1种情况，概率＝(1-p)^6 1条边被选中有6种情况，概率＝6*p*(1-p)^5 2条边被选中有15种情况，概率＝15*p^2*(1-p)^4 3条边被选中有4种情况，概率＝4*p^3*(1-p)^3 4、5、6条边被选中，概率＝0 (1-p)^6+6*p*(1-p)^5+15*p^2*(1-p)^4+4*p^3*(1-p)^3＝0.5 解一个一元六次方程，解得p＝0.45110975209938 所以P(4)=0.45110975209938

056254628

解 $125*p^4-528*p^5+970*p^6-980*p^7+570*p^8-180*p^9+24*p^10=0.5$ 得 P(5)=0.404341191366976 解 $1296*p^5-9300*p^6+31080*p^7-63195*p^8+86110*p^9-81840*p^10+54780*p^11-25440*p^12+7830*p^13-1440*p^14+120*p^15=0.5$ 得 P(6)=0.364968878617189 解 $16807*p^6-183810*p^7+965160*p^8-3209430*p^9+7527471*p^10-13150032*p^11+17633945*p^12-18448710*p^13+15159120*p^14-9770810*p^15+4894680*p^16-1869840*p^17+526890*p^18-103320*p^19+12600*p^20-720*p^21=0.5$ 得 P(7)=0.332459475337216 计算N＝8时，就溢出了，需要利用大数计算。

056254628

解 125*p^4-528*p^5+970*p^6-980*p^7+570*p^8-180*p^9+24*p^10=0.5 得 P(5)=0.404341191366976 解 1296*p^5-9300*p^6+31080*p^7-63195*p^8+86110*p^9-81840*p^10+54780*p^11-25440*p^12+7830*p^13-1440*p^14+120*p^15=0.5 得 P(6)=0.364968878617189 解 16807*p^6-183810*p^7+965160*p^8-3209430*p^9+7527471*p^10-13150032*p^11+17633945*p^12-18448710*p^13+15159120*p^14-9770810*p^15+4894680*p^16-1869840*p^17+526890*p^18-103320*p^19+12600*p^20-720*p^21=0.5 得 P(7)=0.332459475337216

056254628

对于每一种情况，可以根据连通情况，将其分成k个部分，每个部分内部都是连通的，与其他部分都不连通。 比如 (2，2，4) 代表N＝8，分成三个部分，每个部分都是连通的。 (2，2，4)情况的概率记做 T(2，2，4) －－－－－－－－－－－－－－－－－－－－－－－－－－－ 当N所有情况的概率都知道的情况下，可以递推出N+1的所有情况的概率。 这样根据初始条件 T(2)=P 记做(0,1) 表示0＋1*P (多项式系数表示法) T(1,1)=1-P 记做(1,-1) 表示1-1*P (多项式系数表示法) 可依次递推。 以下是结果。 T(2)=(0,1) T(1,1)=(1,-1) T(3)=(0,0,3,-2) T(1,2)=(0,3,-6,3) T(1,1,1)=(1,-3,3,-1) T(4)=(0,0,0,16,-33,24,-6) T(1,3)=(0,0,12,-44,60,-36,8) T(2,2)=(0,0,3,-12,18,-12,3) T(1,1,2)=(0,6,-30,60,-60,30,-6) T(1,1,1,1)=(1,-6,15,-20,15,-6,1) T(5)=(0,0,0,0,125,-528,970,-980,570,-180,24) T(1,4)=(0,0,0,80,-485,1260,-1820,1580,-825,240,-30) T(2,3)=(0,0,0,30,-200,570,-900,850,-480,150,-20) T(1,1,3)=(0,0,30,-230,770,-1470,1750,-1330,630,-170,20) T(1,2,2)=(0,0,15,-120,420,-840,1050,-840,420,-120,15) T(1,1,1,2)=(0,10,-90,360,-840,1260,-1260,840,-360,90,-10) T(1,1,1,1,1)=(1,-10,45,-120,210,-252,210,-120,45,-10,1) T(6)=(0,0,0,0,0,1296,-9300,31080,-63195,86110,-81840,54780,-25440,7830,-1440,120) T(1,5)=(0,0,0,0,750,-6918,29160,-74160,126450,-151770,130812,-80940,35220,-10260,1800,-144) T(2,4)=(0,0,0,0,240,-2415,11040,-30270,55320,-70770,64680,-42240,19320,-5895,1080,-90) T(1,1,4)=(0,0,0,240,-2655,13455,-41310,85590,-126090,135450,-106920,61560,-25215,6975,-1170,90) T(3,3)=(0,0,0,0,90,-930,4360,-12240,22860,-29820,27720,-18360,8490,-2610,480,-40) T(1,2,3)=(0,0,0,180,-2100,11220,-36300,79200,-122760,138600,-114840,69300,-29700,8580,-1500,120) T(1,1,1,3)=(0,0,60,-760,4440,-15840,38500,-67320,87120,-84480,61380,-33000,12760,-3360,540,-40) T(2,2,2)=(0,0,0,15,-180,990,-3300,7425,-11880,13860,-11880,7425,-3300,990,-180,15) T(1,1,2,2)=(0,0,45,-585,3510,-12870,32175,-57915,77220,-77220,57915,-32175,12870,-3510,585,-45) T(1,1,1,1,2)=(0,15,-210,1365,-5460,15015,-30030,45045,-51480,45045,-30030,15015,-5460,1365,-210,15) T(1,1,1,1,1,1)=(1,-15,105,-455,1365,-3003,5005,-6435,6435,-5005,3003,-1365,455,-105,15,-1) T(7)=(0,0,0,0,0,0,16807,-183810,965160,-3209430,7527471,-13150032,17633945,-18448710,15159120,-9770810,4894680,-1869840,526890,-103320,12600,-720) T(1,6)=(0,0,0,0,0,9072,-119532,744240,-2905665,7958440,-16207107,25372662,-31133375,30246090,-23331525,14237020,-6797280,2488290,-674940,127890,-15120,840) T(2,5)=(0,0,0,0,0,2625,-37338,249375,-1038240,3016230,-6483960,10669680,-13710060,13902525,-11162130,7071855,-3498096,1324260,-370860,72450,-8820,504) T(1,1,5)=(0,0,0,0,2625,-39963,286713,-1287615,4054470,-9500190,17153640,-24379740,27612585,-25064655,18233985,-10569951,4822356,-1695120,443310,-81270,9324,-504) T(3,4)=(0,0,0,0,0,1680,-24745,170730,-732480,2187220,-4820235,8110410,-10628310,10963260,-8931615,5728030,-2861460,1091580,-307405,60270,-7350,420) T(1,2,4)=(0,0,0,0,1680,-26985,203910,-962745,3181080,-7806435,14733810,-21846825,25765740,-24309285,18348330,-11016915,5197920,-1886745,508830,-96075,11340,-630) T(1,1,1,4)=(0,0,0,560,-9555,76965,-388885,1381275,-3662505,7513415,-12193545,15870855,-16691675,14219205,-9788415,5404945,-2361555,798525,-201635,35805,-3990,210) T(1,3,3)=(0,0,0,0,630,-10290,79030,-379050,1271550,-3165890,6057870,-9099090,10860850,-10360350,7897890,-4783870,2274090,-830550,225050,-42630,5040,-280) T(2,2,3)=(0,0,0,0,315,-5250,41160,-201600,690900,-1758120,3439800,-5285280,6456450,-6306300,4924920,-3057600,1490580,-558600,155400,-30240,3675,-210) T(1,1,2,3)=(0,0,0,630,-11130,92820,-485520,1785000,-4898040,10395840,-17450160,23483460,-25525500,22462440,-15965040,9096360,-4098360,1428000,-371280,67830,-7770,420) T(1,1,1,1,3)=(0,0,105,-1960,17325,-96390,378420,-1113840,2548980,-4641000,6822270,-8168160,7997990,-6404580,4176900,-2199120,921060,-299880,73185,-12600,1365,-70) T(1,2,2,2)=(0,0,0,105,-1890,16065,-85680,321300,-899640,1949220,-3341520,4594590,-5105100,4594590,-3341520,1949220,-899640,321300,-85680,16065,-1890,105) T(1,1,1,2,2)=(0,0,105,-1995,17955,-101745,406980,-1220940,2848860,-5290740,7936110,-9699690,9699690,-7936110,5290740,-2848860,1220940,-406980,101745,-17955,1995,-105) T(1,1,1,1,1,2)=(0,21,-420,3990,-23940,101745,-325584,813960,-1627920,2645370,-3527160,3879876,-3527160,2645370,-1627920,813960,-325584,101745,-23940,3990,-420,21) T(1,1,1,1,1,1,1)=(1,-21,210,-1330,5985,-20349,54264,-116280,203490,-293930,352716,-352716,293930,-203490,116280,-54264,20349,-5985,1330,-210,21,-1)

056254628

T(8)=(0,0,0,0,0,0,0,262144,-4068456,30802240,-150657080,532354536,-1441519296,3098951072,-5410382880,7786027816,-9324568001,9345271992,-7856193296,5536123600,-3258291120,1590501640,-636845160,205732800,-52319190,10086720,-1386000,120960,-5040) T(9)=(0,0,0,0,0,0,0,0,4782969,-100143792,1032288516,-6952118544,34273176588,-131447465856,407158789500,-1044267039720,2256642859464,-4160649753288,6604921452864,-9087542239104,10886907107538,-11390487268104,10424251015920,-8346992077872,5841996257286,-3565563257088,1890561025584,-866124834680,340283488860,-113494862880,31699531080,-7276802400,1337084280,-189090720,19323360,-1270080,40320) T(10)=(0,0,0,0,0,0,0,0,0,100000000,-2719892160,36628300800,-324496267200,2121183237600,-10884316965480,45558310696800,-159642667620135,477077447178540,-1232671556293800,2782630494934920,-5532426738592740,9748958193896580,-15300758477189520,21469710851551800,-27011077082801580,30532209914200806,-31050312703343640,28429756177413360,-23437879996999860,17388982649046960,-11596879696617600,6939551178972720,-3716558335019880,1775448575926410,-753273866698920,282287441908080,-92792729053500,26521978127400,-6517548349200,1357020856800,-234748765440,32833495800,-3567715200,282592800,-14515200,362880) 解上述多项式等于0.5的解，就可得出P(8)、P(9)、P(10)

wayne

056254628的方法很不错。 只是回复太简短， 我来补充一下： 计算 不连通的概率比较方便： 设T[n]表示n个点不连通的总概率，而n个点不连通又分各种情况，这个时候就是整数划分的情形了。 则n个点联通的概率 p[n]= 1-T[n] n=3 {{2, 1}, {1, 1, 1}} T[3] = 3!/2!*p[2]*p[1]*(1-p)^2+ 3!/3!*p[1]*p[1]*(1-p)^3=1 - 3 p^2 + 2 p^3 p[3] =3 p^2 - 2 p^3 n=4,分解成： {{3, 1}, {2, 2}, {2, 1, 1}, {1, 1, 1, 1}} T[4]=4!/3!*p[3]*p[1]*(1-p)^3+4!/(2!*2!)/2!*p[2]*p[2]*(1-p)^4+4!/2!/2*p[2]*p[1]*p[1]*(1-p)^(2*1+2*1+1*1)+(1-p)^6=1 - 16 p^3 + 33 p^4 - 24 p^5 + 6 p^6 p[4]=16 p^3 - 33 p^4 + 24 p^5 - 6 p^6

wayne

n=5 {{4, 1}, {3, 2}, {3, 1, 1}, {2, 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1}} T[5]=5!/4!*p[4]*(1-p)^4 +5!/(2!*3!)*p[3]*p[2]*(1-p)^6 +5!/3!/2!*p[3]*(1-p)^(3+3+1) +5!/(2!*2!)/2!*p[2]*p[2]*(1-p)^(4+2+2) +5!/2!/3!*p[2]*(1-p)^9 +(1-p)^10 =1 - 125 p^4 + 528 p^5 - 970 p^6 + 980 p^7 - 570 p^8 + 180 p^9 - 24 p^10 p[5] =125 p^4 - 528 p^5 + 970 p^6 - 980 p^7 + 570 p^8 - 180 p^9 + 24 p^10

wayne

Mathematica程序：

1. p[1] = 1; Table[{k, p[k] = 1 - Expand@Total@Table[Multinomial @@ ii/(Factorial[Tally[ii][[All, 2]]] /. List -> Times)*(p /@ ii /. List -> Times)*(1 - p)^Total[Table[ii /. List -> Times, {ii, Subsets[ii, {2}]}]], {ii, Drop[IntegerPartitions[k], 1]}]}, {k, 2, 10}]

复制代码

运行结果：

1. {2, p}
2. {3, 3*p^2 - 2*p^3}
3. {4, 16*p^3 - 33*p^4 + 24*p^5 - 6*p^6}
4. {5, 125*p^4 - 528*p^5 + 970*p^6 - 980*p^7 + 570*p^8 - 180*p^9 + 24*p^10}
5. {6, 1296*p^5 - 9300*p^6 + 31080*p^7 - 63195*p^8 + 86110*p^9 - 81840*p^10 + 54780*p^11 - 25440*p^12 + 7830*p^13 - 1440*p^14 + 120*p^15}
6. {7, 16807*p^6 - 183810*p^7 + 965160*p^8 - 3209430*p^9 + 7527471*p^10 - 13150032*p^11 + 17633945*p^12 - 18448710*p^13 + 15159120*p^14 - 9770810*p^15 + 4894680*p^16 - 1869840*p^17 + 526890*p^18 - 103320*p^19 + 12600*p^20 - 720*p^21}
7. {8, 262144*p^7 - 4068456*p^8 + 30802240*p^9 - 150657080*p^10 + 532354536*p^11 - 1441519296*p^12 + 3098951072*p^13 - 5410382880*p^14 + 7786027816*p^15 - 9324568001*p^16 + 9345271992*p^17 - 7856193296*p^18 + 5536123600*p^19 - 3258291120*p^20 + 1590501640*p^21 - 636845160*p^22 + 205732800*p^23 - 52319190*p^24 + 10086720*p^25 - 1386000*p^26 + 120960*p^27 - 5040*p^28}
8. {9, 4782969*p^8 - 100143792*p^9 + 1032288516*p^10 - 6952118544*p^11 + 34273176588*p^12 - 131447465856*p^13 + 407158789500*p^14 - 1044267039720*p^15 + 2256642859464*p^16 - 4160649753288*p^17 + 6604921452864*p^18 - 9087542239104*p^19 + 10886907107538*p^20 - 11390487268104*p^21 + 10424251015920*p^22 - 8346992077872*p^23 + 5841996257286*p^24 - 3565563257088*p^25 + 1890561025584*p^26 - 866124834680*p^27 + 340283488860*p^28 - 113494862880*p^29 + 31699531080*p^30 - 7276802400*p^31 + 1337084280*p^32 - 189090720*p^33 + 19323360*p^34 - 1270080*p^35 + 40320*p^36}
9. {10, 100000000*p^9 - 2719892160*p^10 + 36628300800*p^11 - 324496267200*p^12 + 2121183237600*p^13 - 10884316965480*p^14 + 45558310696800*p^15 - 159642667620135*p^16 + 477077447178540*p^17 - 1232671556293800*p^18 + 2782630494934920*p^19 - 5532426738592740*p^20 + 9748958193896580*p^21 - 15300758477189520*p^22 + 21469710851551800*p^23 - 27011077082801580*p^24 + 30532209914200806*p^25 - 31050312703343640*p^26 + 28429756177413360*p^27 - 23437879996999860*p^28 + 17388982649046960*p^29 - 11596879696617600*p^30 + 6939551178972720*p^31 - 3716558335019880*p^32 + 1775448575926410*p^33 - 753273866698920*p^34 + 282287441908080*p^35 - 92792729053500*p^36 + 26521978127400*p^37 - 6517548349200*p^38 + 1357020856800*p^39 - 234748765440*p^40 + 32833495800*p^41 - 3567715200*p^42 + 282592800*p^43 - 14515200*p^44 + 362880*p^45}

复制代码

解 p[10]=1/2得：

2. {2, {0.5`50.}}
3. {3, {0.5`50.}}
4. {4, {0.4511097520993799575366390074233493137646762588542820830490750446087`50.}}
5. {5, {0.404341191366975379965835410110736280449453252466984925258986260318`50.}}
6. {6, {0.3649688786171876725034362096534987972609740254499756612539226271295`50.}}
7. {7, {0.3324594753372192102975771567586793568602822779401161104330615369397`50.}}
8. {8, {0.3055121848229642026730941601497377857604190793704577533761482091023`50.}}
9. {9, {0.2829458421374258036772390229255307953220590263330335431797226307468`50.}}
10. {10, {0.263825884558808910570220208506396220752252431937174262783598993068`50.}}
11. {11, {0.2474378567251968289793258273546740969270817268001598448160002804706`50.}}
12. {12, {0.2332384192827676598538263232461689978544978811379090966973321896358`50.}}
13. {13, {0.2208122923494861890204985480611686416097297724436966849466331980479`50.}}
14. {14, {0.2098392765636121134116351858994888350986933523567685909127148870667`50.}}
15. {15, {0.200069994383263321489586598099554745150284895078171659268242970004`50.}}
16. {16, {0.1913082162098676589373470880620205574159801790237680333867640210668`50.}}
17. {17, {0.1833979541670204296762009937284016288679363151173088643285905872046`50.}}
18. {18, {0.1762139716197288303734531856377764447028575730501888526163198577584`50.}}
19. {19, {0.1696547452109516374460216295105869262608176650273036389160360060165`50.}}
20. {20, {0.1636372007043874352974993563235014038025177443667242845449524246558`50.}}

复制代码