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

1, 2, 10, 32, 173, 864, 5876, 42654, 369352, 3490396, 37205377, 431835570, 5488938513, 75253166882, 1111054042385, 17529435042906, 294620759901439, 5250432711385802, 98912760811106081, 1963457208200874954, 40962100714228585825, 895889161265034629994, 20497593840242211891900

Offset

4,2

Comments

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.

Links

Stephen Dunn, Table of n, a(n) for n = 4..100

Formula

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

Example

a(4) = A329426(2)*A329426(2) = 1*1 = 1, which represents the graph
  V <--> V
  V <--> V.
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.
a(6) = A329426(2)*A329426(4) + A329426(3)*A329426(3) = 1*6 + 2*2 = 10.

Prog

(Kotlin)
fun A056542(n: Long): Long = if (n == 1L) 0 else n * A056542(n-1) + 1
fun A329426(n: Long): Long = 1 + a(n) + A056542(n-1)
fun a(n: Long): Long = (2L..(n/2)).map { A329426(it) * A329426(n-it) }.sum()

Crossrefs

Cf. A329426, A056542.

Sequence in context: A328039 A264960 A151019 * A004028 A263839 A236921

Adjacent sequences: A329424 A329425 A329426 * A329428 A329429 A329430

Keyword

nonn

Author

Stephen Dunn, Nov 30 2019

Extensions

Term a(26) corrected by Sidney Cadot, Jan 06 2023.

Status

approved