|
|
A329427
|
|
Number of directed graphs of n vertices with more than 1 component and outdegree 1.
|
|
3
|
|
|
1, 2, 10, 32, 173, 864, 5876, 42654, 369352, 3490396, 37205377, 431835570, 5488938513, 75253166882, 1111054042385, 17529435042906, 294620759901439, 5250432711385802, 98912760811106081, 1963457208200874954, 40962100714228585825, 895889161265034629994, 20497593840242211891900
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
|
|
EXAMPLE
|
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.
|
|
PROG
|
(Kotlin)
fun a(n: Long): Long = (2L..(n/2)).map { A329426(it) * A329426(n-it) }.sum()
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|