# Combinatorial problem: Directed Acyclic Graph

1. Feb 6, 2014

### EuleChange

How many unique landscapes exist in 5D DAG (directed acyclic graph)? There are 2^5 points (eg: 00000, 00001, ... 11111) and (2^5)! combinations.

The problem is a combinatorial problem. It should be fun and interesting, and I am interested in discussing the solution here as well.

It is classifying all distinct 5 dimensional landscapes. A landscape in 5-space is an assignment of edge direction to each edge between vertices such that a directed acyclic graph is formed (DAG).

Classification might include the number of peaks, basins, or a metric like that.

There are (2^5)! combinations so obviously iterating through each combination and testing if it is a new landscape or an orientation of an old one won't work.

For example in the 2D case, there are (2^2)! permutations = 24. This 24 is made up of 3 landscapes. There are 8 orientations of each one.

I am reluctant to draw a picture at first, because maybe the way you visualize it will help you find a solution.