

A001171


From least significant term in expansion of E( tr (X'*X)^n ), X rectangular and Gaussian. Also number of types of sequential nswap 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 nswap move consists of the removal of n edges and addition of n different edges which result in a new tour. A sequential nswap 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), 151174, 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 [hepth], 2015.
Freddy Cachazo, Karen Yeats, Samuel Yusim, Compatible Cycles and CHY Integrals, arXiv:1907.12661 [mathph], 2019.
S. Grusea and A. Labarre, The distribution of cycles in breakpoint graphs of signed permutations, arXiv:1104.3353 [cs.DM], 20112012.
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), 151174, 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 Kopt Movesfor the LinKernighan TSP Heuristic.
O. A. Kadubovskyi, Enumeration of 2color 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 (ka+b1) in the inner sum should be replaced by (kab+1)!.  Herman Jamke (hermanjamke(AT)fastmail.fm), Aug 01 2010
Conjecture (for n>=5): (n+1)*a(n) = (4*n1)*a(n1) + (5*n^3  16*n^2 + 13*n  1)*a(n2) + (10*n^3  68*n^2 + 150*n  107)*a(n3)  (n4)*(n2)^2*(2*n7)^2*a(n4).  Vaclav Kotesovec, Aug 07 2013


MAPLE

c:=(a, b, k)>(1)^k*((2)^(ab+1)*k*(2*a2*b+1)*(a1)!)/((k+ab+1)*(k+ab)*(ka+b)*(ka+b1)*(kab)!*(2*a1)!*(b1)!); SPMT:=k>2^(3*k2)*k!*(k1)!^2/(2*k)!+add(add(c(a, b, k)*(2^(ab1)*(2*b)!*(a1)!*(kab+1)!/((2*b1)*b!))^2, b=1..min(a, ka)), a=1..k1); seq(SPMT(k), k=1..30); # Herman Jamke (hermanjamke(AT)fastmail.fm), Aug 01 2010


MATHEMATICA

c[a_, b_, n_] := (1)^ n*((2)^(ab+1)*n*(2a2b+1)*(a1)!) / ((n+ab+1)*(n+ab)*(na+b)*(na+b1)*(nab)!*(2a1)!*(b1)!); A001171[n_] := 2^(3n2)*n!*(n1)!^2/(2n)! + Sum[ c[a, b, n]*(2^(ab1)*(2b)!*(a1)!*(nab+1)! / ((2b1)*b!))^2, {a, 1, n1}, {b, 1, Min[a, na]}]; Table[ A001171[n], {n, 1, 19}] (* JeanFranç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



