cp's OEIS Frontend

A329426 Number of non-isomorphic directed graphs where every vertex has outdegree 1, and no self-loops.

%I A329426 #31 Jul 31 2022 15:57:59
%S A329426 1,2,6,20,97,550,3794,29826,266527,2649156,29040865,347548542,
%T A329426 4509961264,63050417976,944767674590,15103712944100,256594870255076,
%U A329426 4616238126871328,87670085904641440,1752759735606185804,36796608121601906104,809312755145598475440,18609995953274373396982
%N A329426 Number of non-isomorphic directed graphs where every vertex has outdegree 1, and no self-loops.
%H A329426 Stephen Dunn, <a href="/A329426/b329426.txt">Table of n, a(n) for n = 2..100</a>
%F A329426 a(n) = 1 + A329427(n) + A056542(n-1).
%F A329426 a(n) = 1 + A056542(n-1) + Sum_{2..floor(n/2)} a(i)*a(n-i).
%e A329426 For n = 2, a(2) = 1 + A329427(2) + A056542(1) = 1 + 0 + 0 = 1, which is the graph A <--> B.
%e A329426 For n = 3, a(3) = 1 + A329427(3) + A056542(2) = 1 + 0 + 1 = 2, which are graphs A --> B <--> C and A --> B --> C --> A.
%e A329426 The middle term is nonzero when there are graphs with more than 1 component.
%o A329426 (Kotlin)
%o A329426 fun A329427(n: Long): Long = (2L..(n/2)).map { a(it) * a(n-it) }.sum()
%o A329426 fun A056542(n: Long): Long = if (n == 1L) 0 else n * A056542(n-1) + 1
%o A329426 fun a(n: Long): Long = 1 + A329427(n) + A056542(n-1)
%Y A329426 Cf. A329427, A056542.
%K A329426 nonn
%O A329426 2,2
%A A329426 _Stephen Dunn_, Nov 30 2019