Counting dependency charts where each task waits on at most two or three others

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). Each dependency is drawn as an arrow from the task waited on to the task that waits, so the number of arrows pointing into a task, its in-degree, is the number of tasks it waits on, and the cap is a cap on the 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, and more so as the number of tasks grows. With five tasks it already removes more than half: there are 29,281 charts with no cap and 13,956 with it.

Where the count is used#

The same charts are the structures of Bayesian networks. A Bayesian network is a probability model drawn as a chart of arrows. The arrows say how the model is built: each variable is modeled given its "parents", the variables with arrows pointing into it. The arrows are often read causally, as direct influence. When a program learns such a model from data, it searches over possible charts, and limiting every variable to a small number of parents is common, with caps such as two or three. This sequence counts the charts allowed under that restriction. The search itself does not need this count. Two narrower tasks do: drawing capped charts uniformly at random, which is one way to generate test cases for learning methods, and setting structure priors, the weights a learning method puts on charts before it sees data, which Eggeling and co-authors (2019) build from counts of this kind.

How it was computed and checked#

In July, a Claude agent working under my direction 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. A later literature check, in October 2026, by a fresh agent searching the web, arXiv and Semantic Scholar, found one: a 2017 paper on generating random preference networks (CP-nets), by Allen, Goldsmith, Justice, Mattei and Raines in the Journal of Artificial Intelligence Research, lists these counts for up to 7 tasks. A397711 and A397712 are the first OEIS entries for these counts, with values through 100 tasks for a cap of two and through 30 tasks for a cap of three, in the entries' b-files (their longer tables of values), far past that table. Every value in that table matches the values here. Eggeling, Viinikka, Vuoksenmaa and Koivisto (2019) gave a recurrence for these counts under any cap, extending Robinson's 1973 recurrence for charts with no cap, without publishing the values; Talvitie, Vuoksenmaa and Koivisto (2019) used such counts inside a sampler, also without a table. The argument below for prime numbers of tasks is the standard rotation argument, applied to these charts.

The agent computed the counts four separate ways. Two programs build every possible chart and test it, one up to 5 tasks and a faster one up to 8. The other two are formulas: a level formula, explained next, and a recurrence that builds each chart by setting aside the tasks that wait on nothing. (The recurrence of Eggeling and co-authors sets aside the tasks that nothing waits on instead.) All four agree wherever they overlap. All four were written by Claude agents, so that agreement is a check inside the project. The checks against numbers from outside it are the 2017 table above and two counts that were already known, which the main formula reproduces: 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. Once the levels are fixed, a task's options are: at least one task from the level just below, any others from lower levels, and no more than the cap in all. How many options that gives depends only on how many tasks sit on the level just below and how many sit on the levels under that, and one task's choice does not change another's, so the options multiply. Adding these products over all the ways to split the tasks into levels gives the total. That argument proves the formula, which is written out in the database entry and in the section for specialists below. Written out, the sum has a term for every way to split the tasks into levels, far too many to list for large n. A dynamic program that keeps track only of how many tasks are placed so far and how many sit on the latest level adds them up in a number of arithmetic steps that grows like the cube of the number of tasks, and it produced the whole table up to 100 tasks in 1.5 seconds. The level formula and the recurrence that sets aside tasks waiting on nothing were compared for up to 13 tasks; beyond that, in July, the table rested on the level formula alone. Added October 2026: the recurrence of Eggeling and co-authors, which the later proof uses, reproduced all 101 values, from 0 tasks to 100.

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. When the number of tasks is prime, the remainder follows a rule with a short proof. For other numbers of tasks, with a cap of two, the remainders follow a rule that Claude agents working under my direction found by computer and that, as of July 2026, nobody had proved (see What happened next).

The short proof for a prime number of tasks 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. Take the fewest renamings that bring a given chart back to itself. Since five renamings always bring it back, that fewest number divides 5, and the chart's group has exactly that many charts in it. 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 seem to follow a simple rule, which I listed as a conjecture. 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 in July, and the renaming trick does not supply one, so I listed it in the database as a conjecture. 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 (the pages on the later proof, like its preprint, write r for this cap; 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. Arrows point from parent to child (u → v means v waits on u); a source has no parents and a sink is nobody's parent. The cross-check recurrence (the fourth method above) removes sources, as Robinson's 1973 recurrence for A003024 does, so it is not the sink recurrence given below. Under a cap on parents removing sources does not factor, since the remaining nodes may still take parents among the removed ones, so the program also tracks how many more parents each remaining node may take. The cap does factor over sinks, since each removed sink picks at most k parents freely among the other nodes: a(n) = sum_{j=1..n} (-1)^(j+1) C(n, j) f(n-j)^j a(n-j) with f(m) = sum_{i=0..k} C(m, i), which is Corollary 4 of Eggeling, Viinikka, Vuoksenmaa and Koivisto (AISTATS 2019). 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 in July. A later check found the values for n ≤ 7 in Allen, Goldsmith, Justice, Mattei and Raines, JAIR 59 (2017), Theorem 18 and Table 1 (on uniform generation of CP-nets), computed by a recurrence over Steinsky's DAG codes; their entries equal ours. Eggeling et al. (above) give the recurrence without a table of values, and Talvitie, Vuoksenmaa and Koivisto (UAI 2019) use the counts inside a sampler, also without a table. A397711 and A397712 are the first OEIS entries for these counts, with values through n = 100 for k = 2 and n = 30 for k = 3.

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, with L the number of levels (written r in the entry's formula),

a(n) = sum over compositions (m_1, ..., m_L) of n of
       n! / (m_1! ... m_L!) * prod_{j=2..L} 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)]. Evaluated by a dynamic program over (nodes placed, size of the last level), 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 depth of the b-file, the entry's downloadable table of terms). For k = 3 the odd case fails: a(9) ≡ 7 (mod 9). Nothing is conjectured here for k ≥ 3.