cp's OEIS Frontend

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.

%I A001171 M3570 N1447 #44 Oct 15 2019 12:23:10
%S A001171 1,1,4,20,148,1348,15104,198144,2998656,51290496,979732224,
%T A001171 20661458688,476936766720,11959743432960,323764901314560,
%U A001171 9410647116349440,292316310979706880,9663569062008422400,338760229843058688000
%N 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.
%C A001171 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.
%C A001171 There should be a reference to a paper by Guy et al. (?) that gives a formula.
%C A001171 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.
%D A001171 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)
%D A001171 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.
%D A001171 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001171 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001171 Vincenzo Librandi, <a href="/A001171/b001171.txt">Table of n, a(n) for n = 1..100</a>
%H A001171 Freddy Cachazo, Humberto Gomez, <a href="http://arxiv.org/abs/1505.03571">Computation of Contour Integrals on M_{0,n}</a>, arXiv preprint arXiv:1505.03571 [hep-th], 2015.
%H A001171 Freddy Cachazo, Karen Yeats, Samuel Yusim, <a href="https://arxiv.org/abs/1907.12661">Compatible Cycles and CHY Integrals</a>, arXiv:1907.12661 [math-ph], 2019.
%H A001171 S. Grusea and A. Labarre, <a href="https://arxiv.org/abs/1104.3353">The distribution of cycles in breakpoint graphs of signed permutations</a>, arXiv:1104.3353 [cs.DM], 2011-2012.
%H A001171 P. J. Hanlon, R. P. Stanley and J. R. Stembridge, <a href="http://www-math.mit.edu/~rstan/pubs/pubfiles/92.pdf">Some combinatorial aspects of the spectra of normally distributed random matrices</a>, 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]
%H A001171 Keld Helsgaun, <a href="http://www.akira.ruc.dk/~keld/research/LKH/KoptReport.pdf">An Effective Implementation of K-opt Movesfor the Lin-Kernighan TSP Heuristic</a>.
%H A001171 O. A. Kadubovskyi, <a href="http://www.researchgate.net/publication/275956844_Enumeration_of_2-color_chord_diagrams_of_maximal_genus_under_rotation_and_reflection">Enumeration of 2-color chord diagrams of maximal genus under rotation and reflection</a>,Conference: Sixteenth International Scientific Mykhailo Kravchuk Conference at Kyiv, vol 2, 2015.
%F A001171 Hanlon et al. give a formula (it would be nice to give it here).
%F A001171 A complicated formula from Hanlon is given on page 23 of Helsgaun. - _Rob Pratt_, Mar 30 2007
%F A001171 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
%F A001171 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
%p A001171 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
%t A001171 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 *)
%Y A001171 Cf. A061714.
%K A001171 nonn,nice
%O A001171 1,3
%A A001171 _Colin Mallows_
%E A001171 Additional comments from _David Applegate_, Jun 21 2001
%E A001171 More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Aug 01 2010