vamaddur's blog

Total Number of Connected Components in All Possible Graphs of N Nodes
By vamaddur, history, 5 years ago, In English

Original Problem

Can someone provide an editorial of this problem or link to one that already exists (I was not able to find one via Google search)?

You can also check out this OEIS sequence!

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Look at OEIS' FORMULA row:

E.g.f.: (F(x)-1)*exp(F(x)-1) = G(x)*log(G(x)) where G(x)=Sum_{n=0..oo} 2^(n(n-1)/2)*x^n/n! and F(x)=1+log(G(x)) is the e.g.f. of A001187.

$$$\displaystyle G(x)=\sum_{i=0}^{\infty}\frac{2^{i(i-1)/2}}{i!}x^i$$$
$$$\displaystyle\mathrm{Ans}_n=n![x^n]G(x)\log G(x)$$$
→ Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Since $$$1\le n\le 3000$$$, there is a simple $$$\mathcal{O}(n^2)$$$ solution:

  1. Calculate $$$\mathrm{f}[n]$$$: number of connected graphs of $$$n$$$ nodes.
    Formula: $$$\mathrm{f}[n]=2^{n(n-1)/2}-\sum_{i=1}^{n-1}\binom{n-1}{i-1}\mathrm{f}[i]2^{(n-i)(n-i-1)/2}$$$.

  2. Calculate $$$\mathrm{g}[n]$$$: number of connected components in all possible graphs of $$$n$$$ nodes.
    Formula: $$$\mathrm{g}[n]=\sum_{i=1}^{n}\binom{n-1}{i-1}\mathrm{f}[i](\mathrm{g}[n-i]+2^{(n-i)(n-i-1)/2})$$$.

→ Reply