EDIT: for much better approach, see other answer.
Confirming your values (up to 8) - using a different approach, that should also allow for a more clever method of counting.
Following program needs < 30 min (on one core) to print
We enumerate canonical representatives for these DAGs. A representative is a list of pairs of numbers, e.g.,
[(4,3),(3,2),(1,0),(1,1),(0,0)]. This means that the top node (5) has left child 4, right child 3, node 4 has children (3,2), etc., down to node 1 with children (0,0).
The representative is canonical if
- all pairs are different
- each node (except first) is linked to from somewhere above
- for each level (distance to leaf), the pairs of this level are monotone.
For the example, the level mapping is
[(1,0),(1,1)] are on the same level, and this list is monotone.
Now instead of generate-and-test (which the program does), we should encode these conditions in propositional logic, and use BDDs for counting.
(EDIT here, original program below)
With somewhat improved internal representation, my program (now too long to post here, perhaps I play code golf later) says
a9 = 97608831
I wonder if we can use the following: $a[x_k,..,x_0] =$ the number of dags with $x_h$ nodes at level $h$. (E.g., $a[1,2,1,1]=6$). Here's list (for $\sum x_i=9$, you call this "8 nodes" since you don't count the leaf)
Is there some relation that would allow to compute these numbers without looking at any trees, graphs, dags? Some observations:
- $a[1,\dots,1]$ is $(2k-1)!!$
- and the others are even (so we should be able to speed up enumeration by 2)?
original source code below:
import qualified Data.Set as S
import qualified Data.Map.Strict as M
import Data.List ( sort )
import Control.Monad ( guard, when, forM_ )
main = forM_ [1 .. ] $ \ n -> do
print (n, length $ filter dag_ok $ candidates n )
type DAG = [(Int,Int)]
dag_ok :: DAG -> Bool
dag_ok dag =
nodes_different dag && nodes_linked dag && levels_ok dag
nodes_different dag =
length dag == S.size (S.fromList dag)
nodes_linked dag =
S.fromList [0 .. length dag-1]
== S.fromList (do (x,y) <- dag ; [x, y] )
levels_ok dag =
let n = length dag ; m = levels dag
s = M.fromListWith S.union $ do (p,h) <- M.toList m ; return (h, S.singleton p)
in weakly_monotone ( map snd $ M.toAscList m )
&& and ( do
( h, ps ) <- M.toList s
return $ monotone $ do p <- S.toDescList ps ; return $ dag !! (n-p)
monotone xs = and $ zipWith (<) xs $ tail xs
weakly_monotone xs = and $ zipWith (<=) xs $ tail xs
levels  = M.fromList [(0,0)]
levels ((x,y):d) =
let m = levels d
in M.insert (length d+1) (succ $ max ( m M.! x) (m M.! y)) m
candidates 0 = [ ]
candidates n = do
d <- candidates (n-1)
x <- [ 0 .. n-1] ; y <- [ 0 .. n-1]