I am solving some TSP problems and i got this one and i am not pretty sure about my answer.
By seeing TSP as a formal combinatorial problem, i have that the Feasible solutions $F$ is the set defined as $F=\{S\subseteq V^2:S \text{ a hamiltonial circuit}\}$, with some cost function associated to the sum of the weights. Now, by defining the neighborhood of a feasible solution $f$ as $N_k(f)$ to be the feasible solutions $g$ such that $g$ is obtained from $f$ by deleting $k$ edges from $f$ and adding another $k$ edges. I am asked to count the number of elements of $N_2(f)$ and $N_3(f)$.
For $N_2(f)$ there are $2$ options, or either i remove the edges and put the same edges obtaining $f$ or i remove the edges and i cross the edges and it is just one way to do it, so:$$|N_2(t)|=\binom{n}{2}+1$$
Now, in the case where $k=3$, i have 4 options:
I take out the $3$ edges and i put the same edges. $1$
I take out the $3$ edges and i put back just one of them. $\binom{n}{3}\binom{3}{1}$
I take out the $3$ edges and i put back two of them, but then the third one just have 1 chance and i fall into case 1. $0$
I take out the $3$ edges and i do not put back any of them. $\binom{n}{3}d_3$(where $d_3$ is the derrangament number in $S_3$)
So $|N_3(t)|=\binom{n}{3}(\binom{3}{1}+d_3)+1$
My question is: am i overcounting some configurations? I have that feeling.
If i am not, a generalization would be $$|N_k(t)|=1+\binom{n}{k}\sum _{i=0}^{k-2}\binom{k}{i}d_{k-i}??$$
Thanks in advance.
For the case $k=2$ either you removed two adjacent edges (this can be done in $n$ ways) or not (this can be done in $\binom{n}{2}-n$ ways). If you removed two adjacent edges you still get $f$ after completing the cycle. Else you can get a new feasible cycle by inserting two crossing edges (as you noticed). Thus we have $|N_2(f)|=\binom{n}{2}-n+1$. The following table summarizes the counts:
$$ \begin{array}{c|c|cr} \text{Remove} & \text{n. of possible removals} & \text{n. of new cycles from each removal} \\ \hline \text{2 adjacent} & n & 0 \\ \text{0 adjacent} & \binom{n}{2}-n & 1 \end{array} $$
For the case $k=3$ the table is:
$$ \begin{array}{c|c|cr} \text{Remove} & \text{n. of possible removals} & \text{n. of new cycles from each removal} \\ \hline \text{3 adjacent} & n & 1 \\ \text{2 adjacent} & n(n-4) & 1\\ \text{0 adjacent} & \binom{n}{3}-n-n(n-4) & 1 \end{array} $$
In fact, consider removing three adjacent edges, say $v_1,v_2,v_3$. You can obtain only one "new" feasible cycle (i.e. $\neq$f) by reinserting $v_2$ and then connecting vertex 1 with 3 and vertex 2 with vertex 4. Similarly, consider removing two adjacent edges and then a third non-adjacent one. This can be done by first choosing two adjacent edges (in $n$ ways) and then choosing one more edge among the $n-4$ non-adjacent ones. Now connect the extremes of the larger hole and the left-alone vertex to the extremes of the smaller hole to obtain a new feasible cycle. Finally, from the table we have $|N_3(f)|=\binom{n}{3}+1$.
On the bibliographic side, this is exercise 5 in Ch.1 of Combinatorial Optimization: algorithms and complexity by C.H. Papadimitriou and K. Steiglitz, Dover Publications. I think it is a reference on this topic but as far as I can see there are no solutions to the exercises.