A397712 - OEIS

%I #11 Jul 12 2026 19:44:45

%S 1,1,3,25,543,26566,2556342,435055552,120754619365,51350946391960,

%T 31851384417063656,27701908834589894664,32710404937218452511443,

%U 51052570219128509334656640,102965864527102952655273305600,263231815662641254658699835508896

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

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

%C 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.

%C 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).

%H Tyler Satchel Orden, <a href="/A397712/b397712.txt">Table of n, a(n) for n = 0..30</a>

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

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

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

%K nonn,new

%O 0,3

%A _Tyler Satchel Orden_, Jul 05 2026