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

Author

Alois P. Heinz, Sep 04 2008

Keywords

• nonn

Examples

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

Links

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

Crossrefs

Row sums of A143899.

Cf. A006125, A001858, A007318.

Programs

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 *)

Formula

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

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