2
$\begingroup$

I am trying to find a mathematical relationship between the size of a tree (or - in other terms - the cardinality of set or permutations) for a set of elements which are subject to precedence constraints.

To illustrate the problem, I'll provide a few examples. Suppose our set is {a, b, c, d} and our precedence constraints are: {a->b, a->c, a->d} (meaning a must occur before b, a must occur before c, and a must occur before d). In this case, there are 3! permutations because a must be the first element in all valid permutations and only the last 3 elements are not bound to a position.

As another trivial example, consider {a->b->c->d} (a must occur before b, which must occur before c, which must occur before d). In this case there are 4! / 4! = 1 permutations.

A less trivial example is if we have the precendence constraints {a->b->c, a->d}. In situations like these I have come up with the following logic: the existence of a->b->c means that we instead of having 3! permutations for these elements, we only have one. Similarly, instead of having 2! permutations for a->d we only have 1. Therefore, we can divide the potential permutations (4!) by our factor of (3! + 2! = 8) to get the value of 3, which the number of permutations possible under these precedence constraints.

Using the combination of my first and last finding, I've been able to construe the relationship between the size of the permutation set given different precedence constraints and source sets reasonably well, however I am running into difficulty for a certain type of problem.

Suppose our set is {a, b, c, d, e, f} and our precedence constraints are {a->b->c, a->d->e}, then we have 36 permutations. Further, if our set is {a, b, c, d, e, f, g, h} and our precedence constraints are {a->b->c->d, a->e->f->g}, then we have 160 permutations. I don't see the relationship between these findings.

Is there a clean way to determine the cardinality of the resultant set of permutations, given a source set and precedence constraints?

Thanks

EDIT:

For precedence constraints that match the above form (that is, there are two precedence chains that have half the cardinality of the original set, and the same starting element), I have derived a formula which I think helps us find the number of possible permutations. Looking at the second example, we see that for the subsequent elements in the precedence chain (say b->c->d from the second example), instead of having 3! permutations possible, we now only have 1 valid ordering (similar logic applies to the other constraint). Thus, we have eliminated possible permutations by 3!*3!. Additionally, I dreamt up another factor of 7, and I lost my train of thought as to why. I was thinking something along the lines of the number of reserved slots due to our constraints, or the number of distinct nodes in the precedence constraints. Anyways, the formula becomes 7 * 3! * 3! which can be generalized to (n-1) * (size of first sub-constraint)! * (size of second sub-contraint)!. This is the reduction factor for our set, so instead of 8! possible permutations, we are left with 8! / (7 * 3! * 3!) = 160. This formula seems to hold for the easier precedence constraints as well, and might be a general solution.

$\endgroup$
3
  • 6
    $\begingroup$ This is the theory of linear extensions of a poset, and probably the person who developed this theory will be along to answer your question... $\endgroup$ – Alexander Woo Oct 3 '20 at 4:44
  • $\begingroup$ Awesome, can't wait to get some insight. Thanks for the direction in the meantime. $\endgroup$ – user35883 Oct 3 '20 at 5:08
  • 1
    $\begingroup$ Worth mentioning also the famous result of Brightwell and Winkler which says that computing the number of linear extensions for arbitrary finite posets is $\#P$-complete (so, informally, there cannot be a "good" formula in general). $\endgroup$ – Sam Hopkins Oct 3 '20 at 16:43
7
$\begingroup$

If the precedence constraints are a disjoint union of rooted trees, as in your examples, then there is an explicit formula due to Knuth, The Art of Computer Programming, vol. 3, 1973, p. 70. Let $n$ be the size of the set $S$. For each $x\in S$, let $\nu(x)$ denote one more than the number of elements that come after $x$. Then the number of permutations is $$ \frac{n!}{\prod_{x\in S} \nu(x)}. $$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.