A397712 Number of acyclic digraphs (or DAGs) on n labeled nodes in which every node has in-degree at most 3.

1, 1, 3, 25, 543, 26566, 2556342, 435055552, 120754619365, 51350946391960, 31851384417063656, 27701908834589894664, 32710404937218452511443, 51052570219128509334656640, 102965864527102952655273305600, 263231815662641254658699835508896

Offset

0,3

Comments

Number of Bayesian network structures on n variables with at most 3 parents per variable.

k=3 member of the family A000272 (k=1, shifted), A397711 (k=2), A003024 (k unbounded). Agrees with A003024 for n <= 4; first divergence a(5) = 26566 versus 29281.

a(p) == 1 (mod p) for prime p, by the same cyclic-relabeling argument as A397711; unlike the k=2 case this does not extend to all odd n (a(9) == 7 mod 9).

Links

Tyler Satchel Orden, Table of n, a(n) for n = 0..30

Formula

Same level-decomposition sum as A397711 with F(p,q) = Sum_{i=1..3} (binomial(p+q,i) - binomial(q,i)).

Prog

(Python) # The program in A397711 with k=3.

Crossrefs

Cf. A003024 (no in-degree bound), A000272 (in-degree at most 1, shifted), A397711 (in-degree at most 2).

Sequence in context: A136173 A243440 A306783 * A003024 A224679 A213599

Adjacent sequences: A397708 A397709 A397711 * A397715 A397716 A397717

Keyword

nonn,new

Author

Tyler Satchel Orden, Jul 05 2026

Status

approved