Probabilistic method proof clarification Image 1:

Image 2:

How did they get the probability in the first picture and the expectation in the second?
 A: For the probability that $v$ precedes its $d(v)$ neighbors, condition on its position $k$:
\begin{align}
\frac{1}{n!}\sum_{k=1}^{d(v)+1} \binom{d(v)}{k-1}(k-1)!(n-k)!
&=\frac{1}{n}\sum_{k=0}^{d(v)} \frac{\binom{d(v)}{k}}{\binom{n-1}{k}}\\
&=\frac{1}{n}\sum_{k=0}^{d(v)} \frac{\binom{n-1-k}{d(v)-k}}{\binom{n-1}{d(v)}}\\
&=\frac{1}{n\binom{n-1}{d(v)}}\sum_{j=0}^{d(v)} \binom{n-1-d(v)+j}{j}\\
&=\frac{\binom{n}{d(v)}}{n\binom{n-1}{d(v)}}\\
&=\frac{1}{n-d(v)}
\end{align}
A: *

*Here's an overly slick way to see the first one, which cuts down on binomial coefficient calculations. (I didn't come up with it -- I've seen this in algorithms classes a few times. My sense is that an answer along the lines of what Rob gives is actually the 'right' approach, since carefully manipulating binomial coefficients is a general technique that answers these kinds of questions.)

Only the ordering of the nodes $v$ and its $n - d(v) - 1$ non-neighbors matter ($v$ is not a neighbor of itself). So, we are asking, if we order $n - d(v) - 1 + 1 = n - d(v) = m$ elements, with a special one called $v$, whats the probability that $v$ ends up first? Well, there $(m -1)!$ permutations where $v$ is first, out of $m!$ total. So the probability is $\frac{1}{m} = \frac{1}{n - d(v)}$.
2.
The second one uses linearity of expectation and the orbit stabilizer theorem.
First we ask: how many copies of $H$ are in $K_n$?
Let's clarify that by a copy we mean an equivalence class of injective graph-homomorphisms $\phi : H \to K_n$, where $\phi \sim \phi'$ iff there is a $a \in Aut(H)$ so that $\phi = \phi' \circ a$. (I'm guessing that this is the intended meaning, but the answer works out so I think the guess is correct.)
The group $S_n$ acts transitively on the set of these by composition on the left, so to figure out how many there are we have to compute the size of a stabilizer. I claim that the order of the stabilizer is exactly $|Aut(H)| (n - v)!$ (proof below), which gives us $\frac{n!}{ (n -v)! |Aut(H)|}$ subgraphs isomorphic to $H$ by the orbit-stabilizer theorem. Each one appears with probability $p^{e(H)}$, so linearity of expectation gives the expected value, using $\# H = \sum_{\text{ copy , } \phi \text{ ,of H in K_n }} 1_{\phi 
 \text{ in G }}$ and $\mathbb{P} (\phi 
 \text{ in G }) = p^{e(H)}$.
Proof of claim: If $g \circ \phi = \phi \circ a$ for some $g \in S_n$ (thought of as a bijection from the vertices of $K_n$ to themselves) and $a \in Aut(H)$, then $im (\phi) = im ( g \circ \phi)$. In particular $g$ preserves the image of $\phi$, which we will call $I$, as well as its complement.
This means that $g$ breaks down into two functions: $g|_{I^c} : I^c \to I^c$, $g|_I : I \to I$. The actions are completely independent, so once we figure out how many choices there are for each piece, we multiply those numbers to get the number of choices for $g$.
$g|_{I^c}$ can be any permutation, so there are $(n - v)!$ choices for it.
The condition for $g|_I$ is that there is some $a \in Aut(H)$ with $g|_{I} \phi = \phi \circ a$. We want to calculate the size of the set $S' = \{ q \in Bijections(I) : \exists a \in Aut(H), q \phi = \phi a \}$.
When restricted to $I$, $\phi : H \to K_n[I]$ becomes a bijection (on vertices). In particular, $g|_{I} = \phi \circ a \circ \phi^{-1}$ (as maps of sets, $\phi^{-1}$ is not a graph homomorphism). To put this differently, $q \in S'$ is completely determined by $a$, and every $a \in Aut(H)$ gives on such $q \in S'$. So $|S'| = Aut(H)$.
