login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A237195 Number of simple labeled graphs on n nodes that contain some size k connected component, all of whose nodes are labeled with integers {1,2,...,k} for some k in {1,2,...,n}. 1
1, 2, 7, 52, 846, 28628, 1928768, 255610528, 66822534992, 34632302913632, 35711543058158592, 73426371674544520192, 301419451958411673103360, 2472252535617096234970201088, 40532629372281642451697543062528, 1328660058258732602631909956943781888 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

In other words, a(n) is the number of simple labeled graphs on {1,2,...,n} such that 1 is an isolated node, or 1 and 2 form a size 2 component, or 1,2 and 3 form a size 3 component, or ... 1,2,3,...,k form a size k component, where 1<=k<=n.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..80

FORMULA

a(n) = Sum_{k=1..n} A223894(n,k)/binomial(n,k).

EXAMPLE

a(3) = 7. We count all 8 simple labeled graphs on {1,2,3} except: 1-3 2.

MAPLE

b:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-

      add(k*binomial(n, k)* 2^((n-k)*(n-k-1)/2)*b(k), k=1..n-1)/n)

    end:

a:= n-> add(b(k)*2^((n-k)*(n-k-1)/2), k=1..n):

seq(a(n), n=1..20);  # Alois P. Heinz, Feb 04 2014

MATHEMATICA

nn=15; g=Sum[2^Binomial[n, 2]x^n/n!, {n, 0, nn}]; a=Drop[Range[0, nn]!CoefficientList[Series[Log[g], {x, 0, nn}], x], 1]; Map[Total, Table[Table[Drop[Transpose[Table[ Range[0, nn]!CoefficientList[Series[a[[n]]x^n/n! g, {x, 0, nn}], x], {n, 1, nn}]], 1][[i, j]]/Binomial[i, j], {j, 1, i}], {i, 1, nn}]]

CROSSREFS

Sequence in context: A216086 A210856 A046662 * A275597 A118191 A005588

Adjacent sequences:  A237192 A237193 A237194 * A237196 A237197 A237198

KEYWORD

nonn

AUTHOR

Geoffrey Critzer, Feb 04 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 25 23:04 EST 2020. Contains 331270 sequences. (Running on oeis4.)