Size of neighborhood in local search for symmetric TSP
Let $\delta_{n,k}$ be the number of ways to select $k$ nonadjacent edges on a path of length $n$. We can compute $\delta_{n,k}$ using a simple recurrence:


$\delta_{n,0} = 1$.
$\delta_{0,k} = 0$ for $k &gt; 0$.
$\delta_{n,k} = \delta_{n-1,k} + \delta_{n-2,k-1}$, where the first term corresponds to the case in which the first edge is chosen, and the other to the case in which the first edge is not chosen.


We can solve this recurrence and obtain $\delta_{n,k} = \binom{n-k+1}{k}$. Indeed, this satisfies the two base cases, and the inductive case is just Pascal's identity $\binom{n-k+1}{k} = \binom{n-k}{k} + \binom{n-k}{k-1}$.

To compute $\gamma_{n,k}$, choose a first edge arbitrarily. If it is chosen, we are left with a choice of $k-1$ edges in a path of length $n-3$, and otherwise we are left with a choice of $k$ edges in a path of length $n-1$. In other words,
$$
\gamma_{n,k} = \delta_{n-1,k} + \delta_{n-3,k-1} = \binom{n-k}{k} + \binom{n-k-1}{k-1}.
$$
This gives
$$
\begin{align*}
\gamma_{n,0} &amp;= 1, \\
\gamma_{n,1} &amp;= \binom{n-1}{1} + \binom{n-2}{0} = (n-1) + 1 = n, \\
\gamma_{n,2} &amp;= \binom{n-2}{2} + \binom{n-3}{1} = \frac{(n-2)(n-3)}{2} + (n-3) = \frac{n(n-3)}{2},
\end{align*}
$$
and so on. Note that there is a difference in normalization: you count the edges with order, and I count them without order. This explains the factor of 2 in $\gamma_{n,2}$. In general, to take the order into account you need to multiply $\gamma_{n,k}$ by $k!$.