Connectedness 4

Probability Level 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 = 1 2 p=\frac{1}{2} . Let N N be the expected number of connected components in graph G G . Then

N = a b N = \frac{a}{b}

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


The answer is 69553.

Christopher Criscitiello by Christopher Criscitiello , 25, USA

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}

The expected number of connected components is then 1866256 ⋅ 1 + 207536 ⋅ 2 + 20818 ⋅ 3 + 2275 ⋅ 4 + 245 ⋅ 5 + 21 ⋅ 6 + 1 ⋅ 7 2 21 = 36785 32768 . \frac{1866256 \cdot 1 + 207536 \cdot 2 + 20818 \cdot 3 + 2275 \cdot 4 + 245 \cdot 5 + 21 \cdot 6 + 1 \cdot 7}{2^{21}} = \frac{36785}{32768}.

0 Helpful 1 Interesting 0 Brilliant 0 Confused

I don't think I'm visualizing this correctly... how can there only be one connected component? Doesn't it have to be connected to something else? Does "connected component" refer to something other than two vertices being connected by an edge? Because that is the assumption I made; which I would think indicates that the minimum number of connected components would be two.

Tristan Goodman - 6 months, 3 weeks ago

Log in to reply

Connected component refers to a subgraph which is connected. So there being only one connected component would mean the graph is connected.

Joe Mansley - 5 months, 1 week ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...