A133189 Number of simple directed graphs on n labeled nodes consisting only of some cycle graphs C_2 and nodes not part of a cycle having directed edges to both nodes in exactly one cycle.

1, 0, 1, 3, 9, 40, 210, 1176, 7273, 49932, 372060, 2971540, 25359411, 230364498, 2215550428, 22460391240, 239236043985, 2669869110856, 31134833803728, 378485082644400, 4786085290280275, 62838103267148790, 855122923978737876, 12042364529117844328

Offset: 0

Author

Alois P. Heinz, Dec 17 2007

Keywords

• nonn

Examples

			a(3) = 3, because there are 3 graphs of the given kind for 3 labeled nodes: 3->1<->2<-3,  2->1<->3<-2,  1->2<->3<-1.
		

References

• A. P. Heinz (1990). Analyse der Grenzen und Möglichkeiten schneller Tableauoptimierung. PhD Thesis, Albert-Ludwigs-Universität Freiburg, Freiburg i. Br., Germany.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..530
• Eric Weisstein's World of Mathematics, Directed Graph
• Eric Weisstein's World of Mathematics, Cycle Graph

Crossrefs

Cf. A006882, A007318, A135458, A135429.

2nd column of A145460, A143398.

Programs

Maple

a:= proc(n) option remember; add(binomial(n, k+k)*
      doublefactorial(k+k-1) *k^(n-k-k), k=0..floor(n/2))
    end:
seq(a(n), n=0..30);
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(
      binomial(n-1, j-1) *binomial(j, 2) *a(n-j), j=1..n))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Mar 16 2015

Mathematica

nn=20;Range[0,nn]!CoefficientList[Series[Exp[Exp[x]x^2/2],{x,0,nn}],x]  (* Geoffrey Critzer, Nov 23 2012 *)
Table[Sum[BellY[n, k, Binomial[Range[n], 2]], {k, 0, n}], {n, 0, 25}] (* Vladimir Reshetnikov, Nov 09 2016 *)

Formula

a(n) = Sum_{k=0..floor(n/2)} binomial(n,2*k) * A006882(2*k-1) * k^(n-2*k).

E.g.f.: exp(exp(x)*x^2/2). - Geoffrey Critzer, Nov 23 2012