cp's OEIS Frontend

A329427 Number of directed graphs of n vertices with more than 1 component and outdegree 1.

%I A329427 #47 Jan 05 2023 19:21:34
%S A329427 1,2,10,32,173,864,5876,42654,369352,3490396,37205377,431835570,
%T A329427 5488938513,75253166882,1111054042385,17529435042906,294620759901439,
%U A329427 5250432711385802,98912760811106081,1963457208200874954,40962100714228585825,895889161265034629994,20497593840242211891900
%N A329427 Number of directed graphs of n vertices with more than 1 component and outdegree 1.
%C A329427 a(n) gives the number of unique ways a directed graph of n vertices with outdegree 1 can be broken into smaller components of size >= 2. It can be generalized to higher degree by replacing A329426 in the formula with a suitable counting function.
%H A329427 Stephen Dunn, <a href="/A329427/b329427.txt">Table of n, a(n) for n = 4..100</a>
%F A329427 a(n) = Sum_{i=2..floor(n/2)} A329426(i) * A329426(n-i).
%e A329427 a(4) = A329426(2)*A329426(2) = 1*1 = 1, which represents the graph
%e A329427   V <--> V
%e A329427   V <--> V.
%e A329427 a(5) = A329426(2)*A329426(3) = 1*2 = 2, which represents the two possible graphs of size 3 (V --> V <--> V, etc.) paired with V <--> V.
%e A329427 a(6) = A329426(2)*A329426(4) + A329426(3)*A329426(3) = 1*6 + 2*2 = 10.
%o A329427 (Kotlin)
%o A329427 fun A056542(n: Long): Long = if (n == 1L) 0 else n * A056542(n-1) + 1
%o A329427 fun A329426(n: Long): Long = 1 + a(n) + A056542(n-1)
%o A329427 fun a(n: Long): Long = (2L..(n/2)).map { A329426(it) * A329426(n-it) }.sum()
%Y A329427 Cf. A329426, A056542.
%K A329427 nonn
%O A329427 4,2
%A A329427 _Stephen Dunn_, Nov 30 2019
%E A329427 Term a(26) corrected by _Sidney Cadot_, Jan 06 2023.