We have a binary tree T with N leaves (each leaf corresponds to a city ID) and N-1 internal nodes. Every internal node has exactly two children.
We have a tour when we visit all of the cities and close the tour by returning to the point at which we started.
(i) However, not just any tour is allowed - the tour must correspond to a depth-first traversal of the tree.
With this restriction (i), how can I get a closed form (as a function of n) of the number of distinct tours of a given T with N internal nodes?
There are 4 examples of tours here, but aren't <2,1,3,0>, <1,2,0,3>, <3,0,1,2>, <0,3,2,1> also tours? If so, isn't there exactly N^3 distinct tours?
HINT: If you remove a pair of sibling leaves, you cut the number of tours in half.