頭の中であれこれ考えてみたが、この問題はかなり難しい。
グラフとは、点とそれを結ぶ辺からなる対象である。
点がm個あり、それをランダムにn個の辺で結んだ場合、そのグラフが連結である確率はどうなるだろう。ただし、辺は同じ点同士を複数回結ばないとする。連結であるとは、任意の点同士が辺をたどって結ばれている、ということである。
簡単な例
例えば、4点で辺が3つだとすると、
数字は各パターンの場合の数。右2つが連結だから、確率は(12+4)/20=4/5となる。
では、5点で辺が4つだとどうなるだろう。頭の体操になると思う。
辺の種類は、5C2 = 10、その中から4辺選ぶから、10C4 = 210、連結なのは上3つだから、求める確率は、125/210 = 25/42となる。
