OFFSET
0,3
COMMENTS
a(n) is the number of Bayesian network structures on n variables in which each variable has at most 2 parents; parent-set bounds of this kind are a standard restriction in Bayesian network structure learning.
Equivalently, the number of dependency graphs on n labeled items in which each item depends directly on at most 2 others.
The analogous count with in-degree at most 1 is A000272(n+1) = (n+1)^(n-1), the number of labeled forests of rooted trees; the unbounded case is A003024. Agrees with A003024 for n <= 3; first divergence a(4) = 443 versus A003024(4) = 543.
a(p) == 1 (mod p) for every prime p: the cyclic group C_p acts on the set of such DAGs by relabeling, and the only fixed DAG is the empty one.
Conjecture (verified for n <= 100): a(n) == 1 (mod n) for all odd n >= 3, and a(n) == n/2 + 1 (mod n) for all even n >= 4.
LINKS
Tyler Satchel Orden, Table of n, a(n) for n = 0..100
FORMULA
a(n) = Sum over compositions (m_1,...,m_r) of n of n!/(m_1!*...*m_r!) * Product_{j=2..r} F(m_{j-1}, m_1+...+m_{j-2})^(m_j), where F(p,q) = p + p*q + binomial(p,2). (Classify nodes by height, the length of the longest directed path ending at each node; every non-bottom node takes all parents from earlier levels with at least one on the previous level, and parent choices are independent.)
a(n) <= (1 + (n-1) + binomial(n-1,2))^n.
EXAMPLE
For n = 2 the a(2) = 3 digraphs are the empty graph, 1->2, and 2->1. For n = 4, of the 543 labeled DAGs (A003024) exactly 100 contain a node of in-degree 3, so a(4) = 543 - 100 = 443.
PROG
(Python)
from math import comb
def a(n, k=2):
if n == 0: return 1
h = [[0]*(n+1) for _ in range(n+1)]
for m in range(1, n+1): h[m][m] = comb(n, m)
for u in range(1, n):
for p in range(1, u+1):
if not h[u][p]: continue
q = u - p
f = sum(comb(p+q, i) - comb(q, i) for i in range(1, k+1))
for m in range(1, n-u+1):
h[u+m][m] += h[u][p] * comb(n-u, m) * f**m
return sum(h[n][p] for p in range(1, n+1))
CROSSREFS
KEYWORD
nonn,new
AUTHOR
Tyler Satchel Orden, Jul 05 2026
STATUS
approved