Connectedness 3

Consider a graph G G on seven vertices. For each pair of vertices, you draw an edge between that pair of vertices with probability p p . Let N ( p ) N(p) be the expected number of connected components in graph G G . Then

0 1 N ( p ) d p = a b \int_{0}^1 N(p) dp = \frac{a}{b}

where a , b a,b are relatively prime positive integers. Submit a + b a+b .


The answer is 89083.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Jon Haussmann
Mar 23, 2018

Using a computer program, I found the number of graphs on seven vertices that have e e edges and k k connected components: e \ k 1 2 3 4 5 6 7 0 0 0 0 0 0 0 1 1 0 0 0 0 0 21 0 2 0 0 0 0 210 0 0 3 0 0 0 1295 35 0 0 4 0 0 5250 735 0 0 0 5 0 13377 6762 210 0 0 0 6 16807 32417 5005 35 0 0 0 7 68295 45360 2625 0 0 0 0 8 156555 45990 945 0 0 0 0 9 258125 35595 210 0 0 0 0 10 331506 21189 21 0 0 0 0 11 343140 9576 0 0 0 0 0 12 290745 3185 0 0 0 0 0 13 202755 735 0 0 0 0 0 14 116175 105 0 0 0 0 0 15 54257 7 0 0 0 0 0 16 20349 0 0 0 0 0 0 17 5985 0 0 0 0 0 0 18 1330 0 0 0 0 0 0 19 210 0 0 0 0 0 0 20 21 0 0 0 0 0 0 21 1 0 0 0 0 0 0 1866256 207536 20818 2275 245 21 1 \begin{array}{c||c|c|c|c|c|c|c} e \backslash k & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 & 21 & 0 \\ \hline 2 & 0 & 0 & 0 & 0 & 210 & 0 & 0 \\ \hline 3 & 0 & 0 & 0 & 1295 & 35 & 0 & 0 \\ \hline 4 & 0 & 0 & 5250 & 735 & 0 & 0 & 0 \\ \hline 5 & 0 & 13377 & 6762 & 210 & 0 & 0 & 0 \\ \hline 6 & 16807 & 32417 & 5005 & 35 & 0 & 0 & 0 \\ \hline 7 & 68295 & 45360 & 2625 & 0 & 0 & 0 & 0 \\ \hline 8 & 156555 & 45990 & 945 & 0 & 0 & 0 & 0 \\ \hline 9 & 258125 & 35595 & 210 & 0 & 0 & 0 & 0 \\ \hline 10 & 331506 & 21189 & 21 & 0 & 0 & 0 & 0 \\ \hline 11 & 343140 & 9576 & 0 & 0 & 0 & 0 & 0 \\ \hline 12 & 290745 & 3185 & 0 & 0 & 0 & 0 & 0 \\ \hline 13 & 202755 & 735 & 0 & 0 & 0 & 0 & 0 \\ \hline 14 & 116175 & 105 & 0 & 0 & 0 & 0 & 0 \\ \hline 15 & 54257 & 7 & 0 & 0 & 0 & 0 & 0 \\ \hline 16 & 20349 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 17 & 5985 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 18 & 1330 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 19 & 210 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 20 & 21 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 21 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \sum & 1866256 & 207536 & 20818 & 2275 & 245 & 21 & 1 \end{array}

Let P k ( p ) P_k(p) be the probability that there are k k connected components. Then P 1 ( p ) = 16807 p 6 ( 1 p ) 15 + 68295 p 7 ( 1 p ) 14 + 156555 p 8 ( 1 p ) 13 + 258125 p 9 ( 1 p ) 12 + 331506 p 10 ( 1 p ) 11 + 343140 p 11 ( 1 p ) 10 + 290745 p 12 ( 1 p ) 9 + 202755 p 13 ( 1 p ) 8 + 116175 p 14 ( 1 p ) 7 + 54257 p 15 ( 1 p ) 6 + 20349 p 16 ( 1 p ) 5 + 5985 p 17 ( 1 p ) 4 + 1330 p 18 ( 1 p ) 3 + 210 p 19 ( 1 p ) 2 + 21 p 20 ( 1 p ) + p 21 , P 2 ( p ) = 13377 p 5 ( 1 p ) 16 + 32417 p 6 ( 1 p ) 15 + 45360 p 7 ( 1 p ) 14 + 45990 p 8 ( 1 p ) 13 + 35595 p 9 ( 1 p ) 12 + 21189 p 10 ( 1 p ) 11 + 9576 p 11 ( 1 p ) 10 + 3185 p 12 ( 1 p ) 9 + 735 p 13 ( 1 p ) 8 + 105 p 14 ( 1 p ) 7 + 7 p 15 ( 1 p ) 6 , P 3 ( p ) = 5250 p 4 ( 1 p ) 17 + 6762 p 5 ( 1 p ) 16 + 5005 p 6 ( 1 p ) 15 + 2625 p 7 ( 1 p ) 14 + 945 p 8 ( 1 p ) 13 + 210 p 9 ( 1 p ) 12 + 21 p 10 ( 1 p ) 11 , P 4 ( p ) = 1295 p 3 ( 1 p ) 18 + 735 p 4 ( 1 p ) 17 + 210 p 5 ( 1 p ) 16 + 35 p 6 ( 1 p ) 15 , P 5 ( p ) = 210 p 2 ( 1 p ) 19 + 35 p 3 ( 1 p ) 18 , P 6 ( p ) = 21 p ( 1 p ) 20 , P 7 ( p ) = ( 1 p ) 21 . \begin{aligned} P_1(p) &= 16807p^6 (1 - p)^{15} + 68295p^7 (1 - p)^{14} + 156555p^8 (1 - p)^{13} + 258125p^9 (1 - p)^{12} \\ &\quad + 331506p^{10} (1 - p)^{11} + 343140p^{11} (1 - p)^{10} + 290745p^{12} (1 - p)^9 + 202755p^{13} (1 - p)^8 \\ &\quad + 116175p^{14} (1 - p)^7 + 54257p^{15} (1 - p)^6 + 20349p^{16} (1 - p)^5 + 5985p^{17} (1 - p)^4 \\ &\quad + 1330p^{18} (1 - p)^3 + 210p^{19} (1 - p)^2 + 21p^{20} (1 - p) + p^{21}, \\ P_2(p) &= 13377p^5 (1 - p)^{16} + 32417p^6 (1 - p)^{15} + 45360p^7 (1 - p)^{14} + 45990p^8 (1 - p)^{13} \\ &\quad + 35595p^9 (1 - p)^{12} + 21189p^{10} (1 - p)^{11} + 9576p^{11} (1 - p)^{10} + 3185p^{12} (1 - p)^9 \\ &\quad + 735p^{13} (1 - p)^8 + 105p^{14} (1 - p)^7 + 7p^{15} (1 - p)^6, \\ P_3(p) &= 5250p^4 (1 - p)^{17} + 6762p^5 (1 - p)^{16} + 5005p^6 (1 - p)^{15} + 2625p^7 (1 - p)^{14} \\ &\quad + 945p^8 (1 - p)^{13} + 210p^9 (1 - p)^{12} + 21p^{10} (1 - p)^{11}, \\ P_4(p) &= 1295p^3 (1 - p)^{18} + 735p^4 (1 - p)^{17} + 210p^5 (1 - p)^{16} + 35p^6 (1 - p)^{15}, \\ P_5(p) &= 210p^2 (1 - p)^{19} + 35p^3 (1 - p)^{18}, \\ P_6(p) &= 21p (1 - p)^{20}, \\ P_7(p) &= (1 - p)^{21}. \end{aligned}

We can compute that 0 1 P 1 ( p ) d p = 242565 369512 , 0 1 P 2 ( p ) d p = 211093 2217072 , 0 1 P 3 ( p ) d p = 859 14212 , 0 1 P 4 ( p ) d p = 505 10032 , 0 1 P 5 ( p ) d p = 39 836 , 0 1 P 6 ( p ) d p = 1 22 , 0 1 P 7 ( p ) d p = 1 22 . \begin{aligned} \int_0^1 P_1(p) \ dp &= \frac{242565}{369512}, \\ \int_0^1 P_2(p) \ dp &= \frac{211093}{2217072}, \\ \int_0^1 P_3(p) \ dp &= \frac{859}{14212}, \\ \int_0^1 P_4(p) \ dp &= \frac{505}{10032}, \\ \int_0^1 P_5(p) \ dp &= \frac{39}{836}, \\ \int_0^1 P_6(p) \ dp &= \frac{1}{22}, \\ \int_0^1 P_7(p) \ dp &= \frac{1}{22}. \end{aligned}

Finally, N ( p ) = P 1 ( p ) + 2 P 2 ( p ) + 3 P 3 ( p ) + + 7 P 7 ( p ) , N(p) = P_1(p) + 2P_2(p) + 3P_3(p) + \dots + 7P_7(p), so 0 1 N ( p ) d p = 0 1 [ P 1 ( p ) + 2 P 2 ( p ) + 3 P 3 ( p ) + + 7 P 7 ( p ) ] d p = 0 1 P 1 ( p ) d p + 2 0 1 P 2 ( p ) d p + 3 0 1 P 3 ( p ) d p + + 7 0 1 P 7 ( p ) d p = 242565 369512 1 + 211093 2217072 2 + 859 14212 3 + 505 10032 4 + 39 836 5 + 1 22 6 + 1 22 7 = 59911 29172 . \begin{aligned} \int_0^1 N(p) \ dp &= \int_0^1 [P_1(p) + 2P_2(p) + 3P_3(p) + \dots + 7P_7(p)] \ dp \\ &= \int_0^1 P_1(p) \ dp + 2 \int_0^1 P_2(p) \ dp + 3 \int_0^1 P_3(p) \ dp + \dots + 7 \int_0^1 P_7(p) \ dp \\ &= \frac{242565}{369512} \cdot 1 + \frac{211093}{2217072} \cdot 2 + \frac{859}{14212} \cdot 3 \\ &\quad + \frac{505}{10032} \cdot 4 + \frac{39}{836} \cdot 5 + \frac{1}{22} \cdot 6 + \frac{1}{22} \cdot 7 \\ &= \frac{59911}{29172}. \end{aligned}

@Christopher Criscitiello , is there any way to do these problems other than brute force?

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...