I want to show that $\mu_{n}(p)$, the expected number of Hamiltonian cycles in the random graph $G(n,p)$, is given by
$$\mu_{n}(p)=\frac{1}{2}(n-1)!p^{n}$$
We can easily show that the number of the Hamiltonian cycles in a complete graph $K_{n}$ is given by $\frac{1}{2}(n-1)!$. Now, we let $X$ be a random variable counting the number of Hamiltonian cycles. Then the expectations of $X$ in a random graph $G(n,p)$ is $$E[X]=
\displaystyle\sum_{i=1}^{k} x_ip_i$$ where $x_i$ denotes a Hamiltonian cycle in a complete graph $K_n$ and $p_i=p^n$ for all $i$, since each Hamiltonian cycle that occurs in $K_n$ occurs in $G(n,p)$ with probability $p^n$. Thus, using the linearity of the expectation, we get
$$E[X]= p^n\displaystyle\sum_{i=1}^{k} x_i=p^n\frac{1}{2}(n-1)!$$
as required. Does that make sense?
Best Answer
You are doing the calculation correctly, but I take some issue with your formalism. Specifically, you say that "$x_i$ denotes a Hamiltonian cycle in a complete graph $K_n$" but it's unclear what sort of object $x_i$ is, and why you replace every $x_i$ by $1$ in the final step.
So let me give you the conventional careful way of writing up the same calculation you do. (As you become used to this kind of argument, you will skip directly to multiplying $\frac12(n-1)!$ by $p^n$, but it's important to be able to fill in the intervening steps when you need to.)
Arbitrarily order the $k = \frac12(n-1)!$ Hamiltonian cycles in $K_n$ so that we can talk about the first cycle, second cycle, $i^{\text{th}}$ cycle, and so on. Define the random variable $$ X_i = \begin{cases}1 & \text{the $i^{\text{th}}$ cycle is present in $G(n,p)$,} \\ 0 & \text{otherwise.} \end{cases} $$ Then we have $$ X = X_1 + X_2 + \dots + X_k $$ and therefore by linearity of expectation $$ \mathbb E[X] = \mathbb E[X_1] + \mathbb E[X_2] + \dots + \mathbb E[X_k]. $$ Since each cycle is present with probability $p^n$, we have $\mathbb E[X_i] = p^n \cdot 1 + (1-p^n) \cdot 0 = p^n$ for each $i$, and therefore $$ \mathbb E[X] = \sum_{i=1}^k \mathbb E[X_i] = \sum_{i=1}^k p^n = k p^n = \frac12 (n-1)! p^n. $$