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

%I #47 Jan 05 2023 19:21:34

%S 1,2,10,32,173,864,5876,42654,369352,3490396,37205377,431835570,

%T 5488938513,75253166882,1111054042385,17529435042906,294620759901439,

%U 5250432711385802,98912760811106081,1963457208200874954,40962100714228585825,895889161265034629994,20497593840242211891900

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

%C 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 Stephen Dunn, <a href="/A329427/b329427.txt">Table of n, a(n) for n = 4..100</a>

%F a(n) = Sum_{i=2..floor(n/2)} A329426(i) * A329426(n-i).

%e a(4) = A329426(2)*A329426(2) = 1*1 = 1, which represents the graph

%e V <--> V

%e V <--> V.

%e 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 a(6) = A329426(2)*A329426(4) + A329426(3)*A329426(3) = 1*6 + 2*2 = 10.

%o (Kotlin)

%o fun A056542(n: Long): Long = if (n == 1L) 0 else n * A056542(n-1) + 1

%o fun A329426(n: Long): Long = 1 + a(n) + A056542(n-1)

%o fun a(n: Long): Long = (2L..(n/2)).map { A329426(it) * A329426(n-it) }.sum()

%Y Cf. A329426, A056542.

%K nonn

%O 4,2

%A _Stephen Dunn_, Nov 30 2019

%E Term a(26) corrected by _Sidney Cadot_, Jan 06 2023.