Number of full orderings in a full binary tree.

Question

I'm trying to resolve an example from book.

T = (V, E) is a full binary tree, and |V| = n. Show that there exist n!/2^((n-1)/2) full orderings on V which extend transverse ordering.

As I know there are three main types of full orderings - post-, -pre, symmetrical. Having binary tree with root A and two leaves B, C. As I understand only order of leaves can change.

So for preorder we get A < B < C; A < C < B.

For postorder: C < B < A; B < C < A;

Symmetrical: B < A < C; C < A < B.

Finally we get 6 different full orderings, but according to the formula should get (1 * 2 * 3) / 2 ^ ((3-1)/2) = 3. Can anyone help me, maybe I misunderstand conditions of the task?

Answer 1

HINT: I’m not familiar with your terminology, but I suspect that transverse ordering refers to the partial ordering of nodes that simply orders each level from left to right but imposes no order relation between nodes on different levels. In that case your original tree has a transverse order with an isolated point $A$ and a chain $B<C$, and there are just $3$ ways to insert $A$ into the chain: $A<B<C$, $B<A<C$, and $B<C<A$. This interpretation also fits the desired result, that there are $$\frac{n!}{2^{(n-1)/2}}$$ linear extensions of the transverse partial order on the nodes of the tree.

There are $n!$ possible permutations (linear orderings) of the nodes, but of course some of them don’t extend the transverse order. Say that two permutations of the nodes are equivalent one can be transformed into the other by one or more interchanges of sibling nodes. For instance, in your little tree with three vertices the permutations $ABC$ and $ACB$ are equivalent, because each can be obtained from the other by interchanging the siblings $B$ and $C$. In the tree shown below, the permutations $ABCDE$, $ACBDE$, $ABCED$, and $ABCED$ are all equivalent: the second is obtained from the first by interchanging $B$ and $C$, the third by interchanging $D$ and $E$, and the fourth by making both interchanges.

                               A  
                              / \  
                             B   C  
                            / \  
                           D   E

• Show that this notion of equivalence really is an equivalence relation on the set of permutations of the nodes of the tree.
• Show that each equivalence class contains $2^{(n-1)/2}$ permutations.
• Show that in each equivalence class there is exactly one permutation that extends the transverse ordering.