How can I compute the number of possible orderings of the numbers $1,\dots,N$, where some constraints are given on the relative order of some numbers?
I know how to do the calculation in simple cases. For example:
- If the constraints are that $7 \succ 5 \succ 8 \succ 11$ (where "$\succ$" means "comes after"), then the number of orderings is $N! / 4!$, because there are $N!$ total orderings and only one out of $4!$ satisfies the constraint.
- If the constraints are that $7\succ 5$, $7\succ 8$ and $7\succ 11$, then the number of orderings is $N!/4$, because here, $3!$ out of the possible $4!$ orderings of 5,7,8,11 satisfy the constraint.
How can I do the calculation when there is a whole tree of constraints? E.g, it is given that:
$7\succ 8$, $8\succ 5$, $8\succ 6$, $6\succ 1$, ...
Is there a simple way to take a tree of such constraints and calculate the number of orderings satisfying all constraints?
Alternatively, is there a software that can be used to do such calculations (e.g. constraint-satisfaction program, SMT program, etc..)?
There is a beautiful formula that counts the number of ways of labeling the vertices of a rooted, binary tree $T$ that has $n$ vertices with the numbers $1, \ldots, n$ so that the labels are increasing from the root to the leaves. For each $v$ in the binary tree $T$, let $h_v$ be the number of vertices "descended" from $v$, including $v$ itself. The number of allowed labelings (called linear extensions of the poset $T$) is then $$\frac{n!}{\prod_{v \in V} h_v}.$$
My understanding is that this only works for binary trees, but there are various extensions of this formula to other kinds of trees. You can see some of the results by googling "hook length formula trees", etc.