login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A061714 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
1, 0, 1, 4, 25, 208, 2121, 25828, 365457, 5895104, 106794993, 2147006948, 47436635753, 1142570789072, 29797622256377, 836527783016196, 25153234375160993, 806519154686509056, 27470342073410272609 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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.

LINKS

Harry J. Smith, Table of n, a(n) for n = 0..100

Helsgaun, Keld, General k-opt submoves for the Lin-Kernighan TSP heuristic, Math. Program. Comput. 1, No. 2-3, 119-163 (2009).

FORMULA

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

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

a(n) ~ (n-1)! * 2^(n-1) * exp(-1/2). - Vaclav Kotesovec, Oct 08 2013

MATHEMATICA

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. *)

PROG

(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

CROSSREFS

Cf. A001171 (sequential n-swap moves).

Sequence in context: A213192 A036242 A120955 * A005411 A105628 A203219

Adjacent sequences:  A061711 A061712 A061713 * A061715 A061716 A061717

KEYWORD

nonn,nice

AUTHOR

David Applegate, Jun 21 2001

EXTENSIONS

Revised by Max Alekseyev, Jul 03 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 22 14:33 EDT 2019. Contains 322356 sequences. (Running on oeis4.)