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.
1, 1, 4, 20, 148, 1348, 15104, 198144, 2998656, 51290496, 979732224, 20661458688, 476936766720, 11959743432960, 323764901314560, 9410647116349440, 292316310979706880, 9663569062008422400, 338760229843058688000
Offset: 1
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.
Crossrefs
Cf. A061714.
Programs
-
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 *)
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
Extensions
Additional comments from David Applegate, Jun 21 2001
More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Aug 01 2010
Comments