login
Number of types of (n-1)-swap moves for traveling salesman problem. Number of circular permutations on elements 0,1,...,2n-1 where every two elements 2i,2i+1 and no two elements 2i-1,2i are adjacent.
4

%I #22 Mar 28 2019 10:57:51

%S 1,0,1,4,25,208,2121,25828,365457,5895104,106794993,2147006948,

%T 47436635753,1142570789072,29797622256377,836527783016196,

%U 25153234375160993,806519154686509056,27470342073410272609

%N Number of types of (n-1)-swap moves for traveling salesman problem. Number of circular permutations on elements 0,1,...,2n-1 where every two elements 2i,2i+1 and no two elements 2i-1,2i are adjacent.

%C An n-swap move consists of the removal of n edges and addition of n different edges which result in a new tour. The type can be characterized by how the n segments of the original tour formed by the removal are reassembled.

%H Harry J. Smith, <a href="/A061714/b061714.txt">Table of n, a(n) for n = 0..100</a>

%H Helsgaun, Keld, <a href="https://doi.org/10.1007/s12532-009-0004-6">General k-opt submoves for the Lin-Kernighan TSP heuristic</a>, Math. Program. Comput. 1, No. 2-3, 119-163 (2009).

%F a(n) = (-1)^n + Sum_{i=0..n-1} (-1)^(n-1-i)*binomial(n,i+1)*i!*2^i = (-1)^n + A120765(n).

%F E.g.f.: exp(-x)*(1-log(1-2*x)/2)

%F a(n) ~ (n-1)! * 2^(n-1) * exp(-1/2). - _Vaclav Kotesovec_, Oct 08 2013

%t m = 18; CoefficientList[ Series[ Exp[-x]*(1 - Log[1-2x]/2), {x, 0, m}], x]*Range[0, m]! (* _Jean-François Alcover_, Jul 25 2011, after g.f. *)

%o (PARI) { for (n=0, 100, a=(-1)^n + sum(i=0, n-1, (-1)^(n-1-i)*binomial(n, i+1)*i!*2^i); write("b061714.txt", n, " ", a) ) } \\ _Harry J. Smith_, Jul 26 2009

%Y Cf. A001171 (sequential n-swap moves).

%K nonn,nice

%O 0,4

%A _David Applegate_, Jun 21 2001

%E Revised by _Max Alekseyev_, Jul 03 2006