Size of neighborhood in local search for symmetric TSP I read about local search / neighborhood search methods for the symmetric TSP and I'm not quite sure about a few things. 
The given example said:


  Suppose we have an instance of the symmetric TSP with n nodes and the neighborhood $N^k$.
  Here $N^k$ is the $k$-change-neighborhood (delete $k$ edges and afterwards insert $k$ other edges).


We define $\gamma_{n, k}$ to be the number of possibilities to delete $k$ non-adjacent edges in a given tour.

If I understand this correctly, it should be as follows:
$\gamma_{n, 0} = 1$, $\gamma_{n,1} = n$, $\gamma_{n, 2} = n(n - 3)$, and so on.


  Is there a formula for $\gamma_{n,k}$?
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!$.