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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.