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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001171 From least significant term in expansion of E( tr (X'*X)^n ), X rectangular and Gaussian. Also number of types of sequential n-swap moves for traveling salesman problem.
(Formerly M3570 N1447)
3
1, 1, 4, 20, 148, 1348, 15104, 198144, 2998656, 51290496, 979732224, 20661458688, 476936766720, 11959743432960, 323764901314560, 9410647116349440, 292316310979706880, 9663569062008422400, 338760229843058688000 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

Let X be a p X q rectangular matrix with random Gaussian entries. Expand E( tr (X'*X)^n ) as a polynomial in p and q for fixed n. Sequence gives coefficient of least significant term in polynomial.

There should be a reference to a paper by Guy et al. (?) that gives a formula.

An n-swap move consists of the removal of n edges and addition of n different edges which result in a new tour. A sequential n-swap is one in which the union of the n removed and n added edges forms a single cycle. The type can be characterized by how the n segments of the original tour formed by the removal are reassembled.

REFERENCES

David L. Applegate, Robert E. Bixby, Vasek Chvatal and William J. Cook, The Traveling Salesman Problem: A Computational Study, Princeton UP, 2006, Table 17.1, p. 535 (has 1358 instead of 1348 for n = 6)

P. J. Hanlon, R. P. Stanley and J. R. Stembridge, Some combinatorial aspects of the spectra of normally distributed random matrices. Hypergeometric functions on domains of positivity, Jack polynomials and applications (Tampa, FL, 1991), 151-174, Contemp. Math., 138, Amer. Math. Soc., Providence, RI, 1992.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 1..100

Freddy Cachazo, Humberto Gomez, Computation of Contour Integrals on M_{0,n}, arXiv preprint arXiv:1505.03571 [hep-th], 2015.

Freddy Cachazo, Karen Yeats, Samuel Yusim, Compatible Cycles and CHY Integrals, arXiv:1907.12661 [math-ph], 2019.

S. Grusea and A. Labarre, The distribution of cycles in breakpoint graphs of signed permutations, arXiv:1104.3353 [cs.DM], 2011-2012.

P. J. Hanlon, R. P. Stanley and J. R. Stembridge, Some combinatorial aspects of the spectra of normally distributed random matrices, In Hypergeometric functions on domains of positivity, Jack polynomials and applications(Tampa, FL, 1991), 151-174, Contemp. Math., 138, Amer. Math. Soc., Providence, RI, 1992. [From Herman Jamke (hermanjamke(AT)fastmail.fm), Aug 01 2010]

Keld Helsgaun, An Effective Implementation of K-opt Movesfor the Lin-Kernighan TSP Heuristic.

O. A. Kadubovskyi, Enumeration of 2-color chord diagrams of maximal genus under rotation and reflection,Conference: Sixteenth International Scientific Mykhailo Kravchuk Conference at Kyiv, vol 2, 2015.

FORMULA

Hanlon et al. give a formula (it would be nice to give it here).

A complicated formula from Hanlon is given on page 23 of Helsgaun. - Rob Pratt, Mar 30 2007

Hanlon et al. provide the correct formula for these coefficients at the end of Section 5 of their paper (see p. 168) but the one given by Helsgaun in his paper (see p. 23) is wrong: the term (k-a+b-1) in the inner sum should be replaced by (k-a-b+1)!. - Herman Jamke (hermanjamke(AT)fastmail.fm), Aug 01 2010

Conjecture (for n>=5): (n+1)*a(n) =  -(4*n-1)*a(n-1) + (5*n^3 - 16*n^2 + 13*n - 1)*a(n-2) + (10*n^3 - 68*n^2 + 150*n - 107)*a(n-3) - (n-4)*(n-2)^2*(2*n-7)^2*a(n-4). - Vaclav Kotesovec, Aug 07 2013

MAPLE

c:=(a, b, k)->(-1)^k*((-2)^(a-b+1)*k*(2*a-2*b+1)*(a-1)!)/((k+a-b+1)*(k+a-b)*(k-a+b)*(k-a+b-1)*(k-a-b)!*(2*a-1)!*(b-1)!); SPMT:=k->2^(3*k-2)*k!*(k-1)!^2/(2*k)!+add(add(c(a, b, k)*(2^(a-b-1)*(2*b)!*(a-1)!*(k-a-b+1)!/((2*b-1)*b!))^2, b=1..min(a, k-a)), a=1..k-1); seq(SPMT(k), k=1..30); # Herman Jamke (hermanjamke(AT)fastmail.fm), Aug 01 2010

MATHEMATICA

c[a_, b_, n_] := (-1)^ n*((-2)^(a-b+1)*n*(2a-2b+1)*(a-1)!) / ((n+a-b+1)*(n+a-b)*(n-a+b)*(n-a+b-1)*(n-a-b)!*(2a-1)!*(b-1)!); A001171[n_] := 2^(3n-2)*n!*(n-1)!^2/(2n)! + Sum[ c[a, b, n]*(2^(a-b-1)*(2b)!*(a-1)!*(n-a-b+1)! / ((2b-1)*b!))^2, {a, 1, n-1}, {b, 1, Min[a, n-a]}]; Table[ A001171[n], {n, 1, 19}] (* Jean-Fran├žois Alcover, Dec 06 2011, after Maple program by Herman Jamke *)

CROSSREFS

Cf. A061714.

Sequence in context: A301270 A117887 A082988 * A247331 A167018 A094070

Adjacent sequences:  A001168 A001169 A001170 * A001172 A001173 A001174

KEYWORD

nonn,nice,changed

AUTHOR

Colin Mallows

EXTENSIONS

Additional comments from David Applegate, Jun 21 2001

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Aug 01 2010

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 October 20 22:44 EDT 2019. Contains 328291 sequences. (Running on oeis4.)