Congruences for labeled acyclic digraphs of bounded in-degree: a proof of the conjecture in OEIS A397711

Let a(n) be the number of acyclic digraphs (DAGs, Bayesian network structures) on n labeled vertices in which every vertex has in-degree at most 2 (OEIS A397711). In July 2026 T. S. Orden conjectured in the entry, after checking n ≤ 100, that a(n) ≡ 1 (mod n) for every odd n ≥ 3 and a(n) ≡ n/2 + 1 (mod n) for every even n ≥ 4. We prove this conjecture. More generally, if a_r(n) counts the acyclic digraphs on n labeled vertices with in-degree at most r, then n divides lcm(1, ..., r)·(a_r(n) − 1) for every n ≥ 1; in particular a_r(n) ≡ 1 (mod n) whenever n is coprime to lcm(1, ..., r) (for instance a_3(n) ≡ 1 (mod n) when gcd(n, 6) = 1, which explains the observation in OEIS A397712). Numerically the multiplier lcm(1, ..., r) cannot be decreased. The proof works with a weighted version of the count, in which every vertex chooses its parents among s copies of each other vertex. The inclusion–exclusion recurrence over sinks (Robinson's recurrence with bounded in-degree) then satisfies s·g | lcm(1, ..., r)·(P_g(s) − 1): every term carries a factor g through C(g,k)(g − k) = g·C(g−1,k), and a factor s because the number of nonempty parent sets drawn from m candidates is divisible by m up to the factor lcm(1, ..., r). For r = 2 this already gives the odd case. For even n, Burnside's lemma for the cyclic group of order n reduces the conjecture to the digraphs invariant under a permutation with all cycles of the same length d, which are counted by the weighted numbers Pn/d(d); the terms with d ≥ 3 are settled by the divisibility above, and the term d = 2 (digraphs invariant under a fixed-point-free involution) by the congruence P_g(2) ≡ g + 1 (mod 2g), proved by a parity count of binomial coefficients. The note was obtained with the author's methodology for open statements in the OEIS (subprocesses with time budgets, a log of obstacles with an algorithm added per obstacle, scripts that test the variants of a formula, literature search, compiled code for the blocking computations, independent verification and review by a second AI system) including the soak test (the numerical check is extended in range rather than repeated, it is run against negative controls that must fail, and the heavy part is rewritten from scratch in compiled code). The work was done with the assistance of an AI system under the author's direction; the methodology section of the note describes the process. The verification programs are included: pm.py and verif.py (Python, no external libraries: the weighted counts by heights and by sinks, the 17 terms of the entry, the lemmas and the general theorem on small ranges, and the minimal multipliers) and an independent Rust program (dagcheck.zip) with exact modular arithmetic, which checks the conjecture for 3 ≤ n ≤ 2500 (the entry checked n ≤ 100), the lemmas on wide ranges, and negative controls (with the same residues, in-degree at most 3, at most 4 and unbounded fail for 83, 156 and 236 of the values 3 ≤ n ≤ 300, and in-degree at most 1 fails exactly at the even n). Both PDFs (English and Spanish) are the same note.