Expected number of hamiltonian paths in a tournament

Question

The following theorem is from Alon&Spencer's The probabilistic method, in the beginning of chapter 2:

Theorem 2.1.1: There is a tournament $T$ with $n$ vertices and at least $\frac{n!}{2^{n-1}}$ Hamiltonian paths.

Briefly the theorem is proved by looking at $X_\sigma$ the indicator random variable for a permutation $\sigma$ giving a Hamiltonian path, that is, satisfying $(\sigma(i),\sigma(i+1))\in T$ for $1\leq i \lt n$. Then

$\sum \mathbb{E}\left[X_\sigma\right] = \frac{n!}{2^{n-1}}$.

I don't understand where did this value ($\frac{n!}{2^{n-1}}$) came from! could someone explain it please?

Answer 1

The argument is to construct a tournament by randomly orienting the edges of $K_n.$ Say the edge goes from the greater number to the smaller with probability $1/2,$ assuming that the vertices are the integers $1,\dots,n.$ Then the probability that a given permutation of the vertices is a Hamilton path is just $2^{1-n},$ leading to the expectation you have given.

Answer 2

Here is how I figured it out,

For each permutation of the vertices, the probability that this permutation represents a hamiltonian path is the probability that each edge points in the correct direction as the previous one, and since the orientation of each edge is chosen indepently then this probability is simply the product of probabilities of the orientation of $(n-1)$ edges. So the probability of the event that a permutation contains a hamiltonian path is $\frac{1}{2^{n-1}}$.

Now since we have $n!$ possible permutations thus the summation of $\mathbb{E}\left[X_\sigma\right]$ will be $\frac{n!}{2^{n-1}}$.