\problemdata                                                             
        {Random Graphs} % latex-friendly label for the prob.
        {Expectation} % The topic(s) of the problem content.  
        {} % Source (if known)                                          
        {S01 Final, 17} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           


A Hamiltonian tour is a cycle that includes all the vertices of the
graph exactly once.  Note that the tour has no specific start or end
point---it is simply the circular sequence of visited nodes.

\begin{problemparts}
\problempart Suppose that you have a \emph{complete} graph on $n$ vertices\footnote{see Figure \ref{complete} on page \pageref{complete} for an example of a complete graph on 5 vertices}. How many Hamiltonian tours does it have? \hint Beware of overcounting...

\problempart Now suppose that you write down $n$ vertices on a piece
of paper and then, for every pair $(u,v)$ of vertices on the page, you
create an edge between $u$ and $v$ independently with fixed
probability $p$.  What is the expected number of Hamiltonian tours?

\solution{
A Hamiltonian tour is a simple cycle that visits all the
vertices once, so the problem reduces to finding the expected number
of simple cycles with exactly $n$ nodes in the cycle. Each $n$-cycle
has $n$ edges as well, so given a possible cycle $c$, each edge is
distinct, so there is a $p^n$ 
chance of that particular cycle existing (since the edges are
distinct, the events are independent). This is also the expectation 
of the number of cycles on that particular path. (Formally, if we
define a random variable $\chi_c$ that takes on the value 1 when the
cycle exists and 0 when it does not, then $E[ \chi_c ] = p^n$.) If we
can find the number of possible cycles, we can then use linearity of
expectation to find the expectation easily. At first glance, there are 
$n!$ permutations of the nodes (the nodes are distinct), but we need
to take into account that cycles are the same through rotation and
through flipping (i.e. $ABCD = BCDA = ADCB$). So we are overcounting
by a factor of $2n$ ($n$ possible rotations, each with a possible
flip). Thus there are $\frac{n!}{2n} = \frac{(n-1)!}{2}$ possible
cycles (for instance, a square has 3 Hamiltonian cycles, but a
triangle only has one). By linearity of expectation, the expected
number of cycles is then:

$$ \frac{(n-1)!}{2} p^n $$
}

\end{problemparts}
\end{problem}                                  