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,4

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

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

Example

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.

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

Crossrefs

Cf. A006882, A007318, A135458, A135429.

2nd column of A145460, A143398.

Sequence in context: A229244 A218504 A292909 * A020092 A346753 A233533

Adjacent sequences: A133186 A133187 A133188 * A133190 A133191 A133192

Keyword

nonn

Author

Alois P. Heinz, Dec 17 2007

Status

approved