What does $(n)_i$ mean, as in $\sum_{i=3}^{\ell}\frac{(n)_i}{2i}p^i$?

47 Views Asked by At

The proof appears in the book "Probabilistic Methods" by Alon and Spencer which applies probabilistic methods to discrete maths problems. Here is an image of the beginning of the proof where it appears:

enter image description here

For those not familiar with the method employed in the proof. Essentially, a graph $G$ on $n$ vertices is defined randomly and pairwise edges between vertices each appear with probability $p$ as defined in the text. $X$ is a random variable that counts the number of cycles of size at most $l$ in the graph, and $X$ can be rewritten as: $$ X = \sum_{i=3}^l X_i $$ Here, $X_i$ is the random variable that counts the number of cycles of size $i$ in the random graph given by $G$. $\mathbb{E}(X)$ is computed using linearity of expectation on the $X_i$'s separately.