Блог пользователя vamaddur

Total Number of Connected Components in All Possible Graphs of N Nodes
Автор vamaddur, история, 5 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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)$$$
→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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})$$$.

→ Ответить