login
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.
7
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
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
2nd column of A145460, A143398.
Sequence in context: A229244 A218504 A292909 * A020092 A346753 A233533
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Dec 17 2007
STATUS
approved