cp's OEIS Frontend

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.

%I A133189 #35 Feb 16 2025 08:33:06
%S A133189 1,0,1,3,9,40,210,1176,7273,49932,372060,2971540,25359411,230364498,
%T A133189 2215550428,22460391240,239236043985,2669869110856,31134833803728,
%U A133189 378485082644400,4786085290280275,62838103267148790,855122923978737876,12042364529117844328
%N 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.
%D A133189 A. P. Heinz (1990). Analyse der Grenzen und Möglichkeiten schneller Tableauoptimierung. PhD Thesis, Albert-Ludwigs-Universität Freiburg, Freiburg i. Br., Germany.
%H A133189 Alois P. Heinz, <a href="/A133189/b133189.txt">Table of n, a(n) for n = 0..530</a>
%H A133189 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DirectedGraph.html">Directed Graph</a>
%H A133189 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CycleGraph.html">Cycle Graph</a>
%F A133189 a(n) = Sum_{k=0..floor(n/2)} binomial(n,2*k) * A006882(2*k-1) * k^(n-2*k).
%F A133189 E.g.f.: exp(exp(x)*x^2/2). - _Geoffrey Critzer_, Nov 23 2012
%e A133189 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 A133189 a:= proc(n) option remember; add(binomial(n, k+k)*
%p A133189       doublefactorial(k+k-1) *k^(n-k-k), k=0..floor(n/2))
%p A133189     end:
%p A133189 seq(a(n), n=0..30);
%p A133189 # second Maple program:
%p A133189 a:= proc(n) option remember; `if`(n=0, 1, add(
%p A133189       binomial(n-1, j-1) *binomial(j, 2) *a(n-j), j=1..n))
%p A133189     end:
%p A133189 seq(a(n), n=0..30);  # _Alois P. Heinz_, Mar 16 2015
%t A133189 nn=20;Range[0,nn]!CoefficientList[Series[Exp[Exp[x]x^2/2],{x,0,nn}],x]  (* _Geoffrey Critzer_, Nov 23 2012 *)
%t A133189 Table[Sum[BellY[n, k, Binomial[Range[n], 2]], {k, 0, n}], {n, 0, 25}] (* _Vladimir Reshetnikov_, Nov 09 2016 *)
%Y A133189 Cf. A006882, A007318, A135458, A135429.
%Y A133189 2nd column of A145460, A143398.
%K A133189 nonn
%O A133189 0,4
%A A133189 _Alois P. Heinz_, Dec 17 2007