login
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
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
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]
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: A366183 A117887 A082988 * A247331 A167018 A094070
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
Additional comments from David Applegate, Jun 21 2001
More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Aug 01 2010
STATUS
approved