A133189 - OEIS

%I #34 Oct 09 2020 10:42:47

%S 1,0,1,3,9,40,210,1176,7273,49932,372060,2971540,25359411,230364498,

%T 2215550428,22460391240,239236043985,2669869110856,31134833803728,

%U 378485082644400,4786085290280275,62838103267148790,855122923978737876,12042364529117844328

%N 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.

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

%H Alois P. Heinz, <a href="/A133189/b133189.txt">Table of n, a(n) for n = 0..530</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DirectedGraph.html">Directed Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CycleGraph.html">Cycle Graph</a>

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

%F E.g.f.: exp(exp(x)*x^2/2). - _Geoffrey Critzer_, Nov 23 2012

%e 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.

%p a:= proc(n) option remember; add(binomial(n, k+k)*

%p       doublefactorial(k+k-1) *k^(n-k-k), k=0..floor(n/2))

%p     end:

%p seq(a(n), n=0..30);

%p # second Maple program:

%p a:= proc(n) option remember; `if`(n=0, 1, add(

%p       binomial(n-1, j-1) *binomial(j, 2) *a(n-j), j=1..n))

%p     end:

%p seq(a(n), n=0..30);  # _Alois P. Heinz_, Mar 16 2015

%t nn=20;Range[0,nn]!CoefficientList[Series[Exp[Exp[x]x^2/2],{x,0,nn}],x]  (* _Geoffrey Critzer_, Nov 23 2012 *)

%t Table[Sum[BellY[n, k, Binomial[Range[n], 2]], {k, 0, n}], {n, 0, 25}] (* _Vladimir Reshetnikov_, Nov 09 2016 *)

%Y Cf. A006882, A007318, A135458, A135429.

%Y 2nd column of A145460, A143398.

%K nonn

%O 0,4

%A _Alois P. Heinz_, Dec 17 2007