# Number of compatible trees with an ancestry matrix

Suppose you are given an ancestry matrix $$M$$ which means that $$M[ij] = 1$$ iff node $$i$$ is an ancestor of node $$j$$. If $$M$$ represents no cycles (treated as an adjacency matrix) the corresponding graph is a tree (or a forest). My question is what is the number of trees where their ancestry matrix is $$M$$.

Is this question any simpler than counting number of directed graphs which are compatible to a general ancestry matrix?

• Hint: Can you come up with 2 different trees that generate the same ancestry matrix? – j_random_hacker Aug 3 at 18:22
• Thank you very much @j_random_hacker – Dandelion Aug 4 at 5:08