Counting dependency charts where each task depends on at most two or three others, and a pattern in the counts that someone else later proved

What is being counted#

The question came from project planning. Take a project backlog in which each task may wait on at most two other tasks before it can start, and nothing may wait in a circle. How many different ways can the dependencies be set up?

The tasks have names, say task 1, task 2 and so on, and the names matter: "task 1 waits on task 2" and "task 2 waits on task 1" count as two different charts. Mathematicians call such a chart a labeled DAG (directed acyclic graph), and the cap on how many tasks one task may wait on is a cap on its in-degree.

With two tasks there are 3 charts: no dependencies, task 1 waiting on task 2, or task 2 waiting on task 1. With three tasks there are 25. The cap does nothing yet, because with three tasks no task has more than two others to wait on. It first matters at four tasks: there are 543 charts with no cap, and in 100 of them some task waits on all three others, which leaves 443. Here are the counts for 1 to 10 tasks with a cap of two:

The cap cuts the numbers down quickly. With five tasks there are 29,281 charts with no cap and 13,956 with it.

Why the number is useful#

The same charts are the skeletons of Bayesian networks. A Bayesian network is a probability model drawn as a chart of arrows, where an arrow from one variable to another means the first directly influences the second; the arrows pointing into a variable come from its "parents". When a program learns such a model from data, it searches over possible charts, and limiting every variable to at most two parents is a standard restriction. This sequence is the exact number of charts that search has to choose from.

How it was computed and checked#

Claude, the AI model I work with, first searched the OEIS (the Online Encyclopedia of Integer Sequences, a public database of number sequences) and the web for the first few values, alone and next to terms like "Bayesian network" and "in-degree", and found no earlier count. It then computed the counts four separate ways. Two programs build every possible chart and test it, which is only practical up to 8 tasks. The other two are formulas. All four agree wherever they overlap. As a further check, the main formula reproduces two counts that were already known: charts with a cap of one, and charts with no cap at all.

The main formula comes from sorting the tasks into levels. Tasks that wait on nothing form the first level. A task goes on level 2 if the longest chain of waiting that ends at it has one step, on level 3 if it has two steps, and so on. Every task on a higher level waits on at least one task from the level just below it, and only on tasks from lower levels. Each task picks its own prerequisites without affecting the others, so the total becomes a sum over all the ways to split the tasks into levels. That argument is the proof, and it is written out in the database entry. The sum takes on the order of n³ arithmetic steps for n tasks, and it produced the whole table up to 100 tasks in 1.5 seconds.

The counts with a cap of two are in the OEIS as A397711, and the cap of three is a companion entry, A397712. When an OEIS editor reviewing them asked for a single table covering every cap, I added that as well, as A395247.

The remainder pattern#

Divide each count by the number of tasks and look at the remainder. Some of the remainders follow a rule with a short proof, and some follow a rule I found by computer and someone else later proved.

The proved part uses a trick: rename the tasks around a circle. With five tasks, task 1 becomes task 2, task 2 becomes task 3, and so on, with task 5 becoming task 1. Renaming turns each chart into another valid chart, and doing it five times brings every chart back to where it started. So the charts fall into groups that the renaming cycles through, and the size of each group divides 5. Since 5 is prime, every group has either 1 chart or 5.

A group of 1 is a chart that renaming leaves unchanged. The chart with no dependencies is one. No other chart can be: if an unchanged chart had an arrow from task 1 to task 3, it would also need arrows from 2 to 4, from 3 to 5, from 4 to 1, and from 5 to 2, and following those arrows from task 1 leads back to task 1, which is circular waiting. So there is exactly one group of 1, and every other chart sits in a group of 5. The total is a multiple of 5, plus 1: 13,956 divided by 5 leaves 1. The same argument works for any prime number of tasks and any cap.

When the number of tasks is not prime, a chart can come back to itself partway around, for example after half a turn, so groups of in-between sizes appear and the trick no longer gives a clean remainder. Even so, with a cap of two the remainders follow a simple rule. For every odd number of tasks from 3 on, the remainder is 1. For every even number from 4 on, it is one more than half the number of tasks. Four tasks: 443 divided by 4 leaves 3. Six tasks: 695,902 divided by 6 leaves 4. Eight tasks: 5,111,573,805 divided by 8 leaves 5. Nine tasks: 681,834,525,328 divided by 9 leaves 1. (With two tasks the remainder is 1, so the even rule really does start at 4.)

I checked that rule for every number of tasks up to 100, but I had no proof, and the renaming trick does not supply one, so I listed it in the database as a conjecture. Since then another contributor, Roberto Blanco Gómez, has posted a proof that it holds for every number of tasks and added it to the entry. I haven't gone through that proof here. The rule also depends on the cap: with a cap of three, the odd-size part breaks, and with nine tasks the remainder is 7, not 1.

For specialists#

The object is labeled DAGs on n nodes with every in-degree at most a fixed cap k (A397711 for k = 2, A397712 for k = 3, and the triangle A395247 by maximum in-degree). Methods, sharing no code: an edge-subset brute force with a DFS cycle test (n ≤ 5), a parent-set backtracking brute force with incremental transitive closure (n ≤ 8), the level-decomposition sum below, and an inclusion-exclusion recurrence (cross-checked against the level sum for n ≤ 13). The level sum reproduces A000272(n+1) for k = 1 and A003024 for unbounded k, both for n ≤ 8. Novelty searches: the OEIS for the initial terms in several windows (k = 2 and k = 3), and web and arXiv full-text searches for the exact values with Bayesian-network and in-degree terms; the Bayesian-network literature uses the object but no tabulation was found.

Level decomposition (from the A397711 entry): classify nodes by height, the length of the longest directed path ending at the node. Every non-bottom node takes all parents from earlier levels with at least one on the previous level, and parent choices are independent, so

a(n) = sum over compositions (m_1, ..., m_r) of n of
       n! / (m_1! ... m_r!) * prod_{j=2..r} F(m_{j-1}, m_1 + ... + m_{j-2})^(m_j)

where for k = 2, F(p, q) = p + pq + C(p, 2), the number of parent sets of size at most 2 drawn from p + q earlier nodes with at least one among the p on the previous level. For general k, F(p, q) = sum_{i=1..k} [C(p+q, i) - C(q, i)]. The sum costs O(n³) big-integer operations for fixed k.

For prime p, a(p) ≡ 1 (mod p) for every cap: the cyclic group of order p acts by relabeling, orbits have size 1 or p, and a DAG fixed by the p-cycle with an edge i → i+d contains the directed cycle i → i+d → i+2d → ⋯ → i, so only the empty DAG is fixed. For k = 2 the entry conjectures a(n) ≡ 1 (mod n) for odd n ≥ 3 and a(n) ≡ n/2 + 1 (mod n) for even n ≥ 4, checked for n ≤ 100 (the table depth of the b-file). Roberto Blanco Gómez has since posted a proof for all n (on Zenodo, linked from the entry): the recurrence over sinks gives n | 2(a(n) − 1), which settles odd n, and Burnside's lemma with the fixed-point-free involutions settles even n. For k = 3 the odd case fails: a(9) ≡ 7 (mod 9). Nothing is conjectured here for k ≥ 3.