Consider an undirected random graph of $n$ vertices. The probability that there is an edge between a pair of vertices is $\frac{1}{2}$. What is the expected number of simple (no vertex more than once), unordered cycles of length $k$ with $k\leq n$ ?
The approach that I took was as follows.
Let $X$ be the random variable denoting the number of undirected cycles of length $k$. Clearly $X$ can takes values from $\left\{0,1,2,\ldots,{\dbinom{n}{k}}\right\}$. We need to find $\mathbf E(X)$.
Since $X$ is a discrete random variable, by definition we have:$$\mathbf E(X)=\sum_{x\in X}x\cdot \Pr(X=x)=\sum_{i=0}^{\binom{n} k}i\cdot \Pr(X=i)$$ where, $\Pr(X=i)$ is the probability of number of simple, undirected cycles of length $k$ being $i$.
And here is where I'm stuck. Can anyone help me finding a convenient way of computing $\Pr(X=i)$.
Let $\{C_t\}_{t=1}^T$ enumerate all cycles of length $k$ in the $n$ vertices, let $G$ be the random graph under consideration, and let $Y_t = 1$ if $C_t \subset G$ and $Y_t = 0$ if $C_t \not \subset G$ (where by $C_t \subset G$ I mean that $G$ has all the edges that appear in $C_t$). If $X$ is the total number of cycles in $G$, then: $$ X = \sum_{t=1}^T Y_t.$$ Now, you can act on this with the expected value, and use additivity (note: $\mathbb{E}(Y+Z) = \mathbb{E}(Y) + \mathbb{E}(Z)$ for any random variables $Y,Z$, not necessarily independent in any way): $$ \mathbb{E}(X) = \mathbb{E}\left( \sum_{t=1}^T Y_t\right) = \sum_{t=1}^T \mathbb{E}\left(Y_t\right) = \sum_{t=1}^T \mathbb{P}(C_t \subset G) .$$ For any $t$, the cycle $C_t$ has $k$ edges, and the probability that all these $k$ edges are chosen is just $\frac{1}{2^k}$. Hence, we get: $$ \mathbb{E}(X) = \frac{T}{2^k} .$$ It remains to compute $T$, i.e. the number of different cycles. Let us fix a vertex $v_0$ (this can be chosen in $n$ ways), and see how many different cycles we can find starting with $v_0$. The second vertex on the cycle $v_1$ can be chosen in $n-1$ ways, $v_2$ can be chosen in $n-2$ ways, and so on, until the vertex $v_{k-1}$ which can be chosen in $n-k+1$ ways. This results in the total of $n(n-1)(n-2)(n-3)\dots (n-k+1) = n^{\underline{k}}$ ways.
However, we count some of the cycles several times. Firstly, we distinguished the starting point $v_0$, which for a given cycle can be chosen in $k$ ways. Secondly, we distinguished an orientation, which for a given cycle can be chosen in two ways. Hence, each cycle is counted $2k$ times, and $T = n^{\underline{k}}/2k$.
Finally, we find: $$ \mathbb{E}(X) = \frac{n^{\underline{k}}}{2^{k+1}k}. $$