A143900 Number of simple graphs on n labeled nodes containing at least one cycle subgraph, also row sums of A143899.

0, 0, 0, 1, 26, 733, 29836, 2060191, 267873508, 68709450231, 35184166480296, 36028792251523289, 73786976171465003256, 302231454900131663566437, 2475880078570650265515241808, 40564819207303337099536803011071, 1329227995784915872766249150185503728

Offset

0,5

Links

Robert G. Wilson v, Table of n, a(n) for n = 0..82 (first 51 terms from Alois P. Heinz)

Formula

a(n) = A006125(n) - A001858(n).

a(n) = Sum_{k=3..C(n,2)} A143899(n,k).

Example

a(3) = 1, because 1 simple graph on 3 nodes with 3 edges contains a cycle subgraph:
..1-2..
..|/...
..3....

Maple

graphs:= n-> 2^binomial(n, 2): forests:= n-> add(add(binomial(m, j) *binomial(n-1, n-m-j) *n^(n-m-j) *(m+j)!/ (-2)^j/ m!, j=0..m), m=0..n): a:= n-> graphs(n) -forests(n): seq(a(n), n=0..18);

Mathematica

graphs[n_] := 2^Binomial[n, 2]; forests[n_] := Sum[Binomial[m, j]* Binomial[n-1, n-m-j]*n^(n-m-j)*(m+j)!/(-2)^j/m!, {m, 0, n}, {j, 0, m}]; a[0] = 0; a[n_] := graphs[n] - forests[n]; Table[a[n], {n, 0, 18}] (* Jean-François Alcover, Feb 25 2017, after Alois P. Heinz *)

Crossrefs

Row sums of A143899.

Cf. A006125, A001858, A007318.

Sequence in context: A181227 A094738 A182612 * A282790 A180792 A091742

Adjacent sequences: A143897 A143898 A143899 * A143901 A143902 A143903

Keyword

nonn

Author

Alois P. Heinz, Sep 04 2008

Status

approved