A001171 -id:A001171 - cp's OEIS frontend

A189507 Triangle read by rows: T(n,k) (n >= 0, 1 <= k <= n+1) are the signed Hultman numbers.

1, 1, 1, 4, 3, 1, 20, 21, 6, 1, 148, 160, 65, 10, 1, 1348, 1620, 701, 155, 15, 1, 15104, 19068, 9324, 2247, 315, 21, 1, 198144, 264420, 138016, 38029, 5908, 574, 28, 1, 2998656, 4166880, 2325740, 692088, 124029, 13524, 966, 36, 1, 51290496, 74011488, 43448940, 13945700, 2723469, 344961, 27930, 1530, 45, 1, 979732224, 1459381440, 897020784, 305142068, 64711856, 8996295, 850905, 53262, 2310, 55, 1

Offset: 0

N. J. A. Sloane, Apr 23 2011

"Signed" refers to the fact that these numbers are associated with signed permutations. The numbers themselves are positive.

			Triangle begins:
      1
      1     1
      4     3    1
     20    21    6    1
    148   160   65   10   1
   1348  1620  701  155  15  1
  15104 19068 9324 2247 315 21 1
  ...

N. Alexeev, A. Pologova, M. A. Alekseyev, Generalized Hultman Numbers and Cycle Structures of Breakpoint Graphs, Journal of Computational Biology 24:2 (2017), 93-105. doi:10.1089/cmb.2016.0190 arXiv:1503.05285
Simona Grusea and Anthony Labarre, The distribution of cycles in breakpoint graphs of signed permutations, arXiv:1104.3353v1

The first three columns give A001171, A189508, A189509. Cf. A164652.

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.

Original entry on oeis.org

1, 0, 1, 4, 25, 208, 2121, 25828, 365457, 5895104, 106794993, 2147006948, 47436635753, 1142570789072, 29797622256377, 836527783016196, 25153234375160993, 806519154686509056, 27470342073410272609

Offset: 0

David Applegate, Jun 21 2001

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.

Harry J. Smith, Table of n, a(n) for n = 0..100
Keld Helsgaun, General k-opt submoves for the Lin-Kernighan TSP heuristic, Math. Program. Comput. 1, No. 2-3, 119-163 (2009).
Wikipedia, Travelling salesman problem.

Cf. A001171 (sequential n-swap moves).

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

{ 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

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

Revised by Max Alekseyev, Jul 03 2006

cp's OEIS Frontend

A189507 Triangle read by rows: T(n,k) (n >= 0, 1 <= k <= n+1) are the signed Hultman numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions