Basic graph counting sequences

[Max Alekseyev]

On Thu, Aug 21, 2008 at 9:16 AM, David Wilson <dwilson at gambitcomm.com> wrote:

> These sequences could also be used as a basis for computing sequences
>
>   G_k = n-node graphs having k connected components
>
> for a few small k.

Unlabeled variant of this sequence is A106240.
The labeled variant seems to be missing in OEIS but it can be computed
as follows:

If g(n,k) is the number of labeled n-node graphs having k connected
components then

SUM[n,k=0..oo] g(n,k) * x^n * y^k / n! = exp( y*( F(x) - 1 ) )
= ( SUM[n=0..oo] 2^binomial(n, 2)*x^n/n! )^y

where F(x) is e.g.f. of A001187.

The triangle of g(n,k) for n=1..9, k=1..n is:

n=1: 1
n=2: 1, 1
n=3: 4, 3, 1
n=4: 38, 19, 6, 1
n=5: 728, 230, 55, 10, 1
n=6: 26704, 5098, 825, 125, 15, 1
n=7: 1866256, 207536, 20818, 2275, 245, 21, 1
n=8: 251548592, 15891372, 925036, 64673, 5320, 434, 28, 1
n=9: 66296291072, 2343580752, 76321756, 3102204, 169113, 11088, 714, 36, 1

Trivially, the first column (i.e., for k=1) is A001187 and the row
sums are A006125.

Regards,
Max