A061714 -id:A061714 - cp's OEIS frontend

A000354 Expansion of e.g.f. exp(-x)/(1-2*x).

1, 1, 5, 29, 233, 2329, 27949, 391285, 6260561, 112690097, 2253801941, 49583642701, 1190007424825, 30940193045449, 866325405272573, 25989762158177189, 831672389061670049, 28276861228096781665, 1017967004211484139941, 38682746160036397317757

Offset: 0

N. J. A. Sloane

a(n) is the permanent of the n X n matrix with 1's on the diagonal and 2's elsewhere. - Yuval Dekel, Nov 01 2003. Compare A157142.
Starting with offset 1 = lim_{k->infinity} M^k, where M = a tridiagonal matrix with (1,0,0,0,...) in the main diagonal, (1,3,5,7,...) in the subdiagonal and (2,4,6,8,...) in the subsubdiagonal. - Gary W. Adamson, Jan 13 2009
a(n) is also the number of (n-1)-dimensional facet derangements for the n-dimensional hypercube. - Elizabeth McMahon, Gary Gordon (mcmahone(AT)lafayette.edu), Jun 29 2009
a(n) is the number of ways to write down each n-permutation and underline some (possibly none or all) of the elements that are not fixed points. a(n) = Sum_{k=0..n} A008290(n,k)*2^(n-k). - Geoffrey Critzer, Dec 15 2012
Type B derangement numbers: the number of fixed point free permutations in the n-th hyperoctahedral group of signed permutations of {1,2,...,n}. See Chow 2006. See A000166 for type A derangement numbers. - Peter Bala, Jan 30 2015

			G.f. = 1 + x + 5*x^2 + 29*x^3 + 233*x^4 + 2329*x^5 + 27949*x^6 + 391285*x^7 + ... - _Michael Somos_, Apr 14 2018

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 83.
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).

T. D. Noe, Table of n, a(n) for n = 0..100
Roland Bacher, Counting Packings of Generic Subsets in Finite Groups, Electr. J. Combinatorics, 19 (2012), #P7. - From _N. J. A. Sloane_, Feb 06 2013
Paul Barry, General Eulerian Polynomials as Moments Using Exponential Riordan Arrays, Journal of Integer Sequences, 16 (2013), #13.9.6.
Chak-On Chow, On derangement polynomials of type B, Séminaire Lotharingien de Combinatoire 55 (2006), Article B55b.
Gary Gordon and Elizabeth McMahon, Moving faces to other places: Facet derangements, arXiv:0906.4253 [math.CO], 2009.
Gary Gordon and Elizabeth McMahon, Moving faces to other places: facet derangements, Amer. Math. Monthly, 117 (2010), 865-88.
Édouard Lucas, Théorie des Nombres, Gauthier-Villars, Paris, 1891, Vol. 1, p. 223.
Édouard Lucas, Théorie des nombres (annotated scans of a few selected pages)
István Mezo, Victor H. Moll, José L. Ramírez, and Diego Villamizar, On the r-Derangements of type B, arXiv:2103.04151 [math.CO], 2021.
István Mező, Victor H. Moll, José Ramírez, and Diego Villamizar, On the r-derangements of type B, Online Journal of Analytic Combinatorics, Issue 16 (2021), #05.
Jean-Christophe Pain, A sum rule for r-derangements obtained from the Cauchy product of exponential generating functions, arXiv:2408.15927 [math.CO], 2024.
Simon Plouffe, Exact formulas for integer sequences
L. W. Shapiro & N. J. A. Sloane, Correspondence, 1976
Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.

Cf. A061714, A008290, A000166, A113012, A263895.

Column k=2 of A320032.

a := n -> (-1)^n*(1-2*n*hypergeom([1,1-n],[],2)):
seq(simplify(a(n)), n=0..18); # Peter Luschny, May 09 2017
a := n -> 2^n*add((n!/k!)*(-1/2)^k, k=0..n):
seq(a(n), n=0..23); # Peter Luschny, Jan 06 2020
seq(simplify(2^n*KummerU(-n, -n, -1/2)), n = 0..19); # Peter Luschny, May 10 2022

FunctionExpand @ Table[ Gamma[ n+1, -1/2 ]*2^n/Exp[ 1/2 ], {n, 0, 24}]
With[{nn=20},CoefficientList[Series[Exp[-x]/(1-2x),{x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, Jul 22 2013 *)
a[n_] := 2^n n! Sum[(-1)^i/(2^i i!), {i, 0, n}]; Table[a[n], {n, 0, 20}] (* Gerry Martens, May 06 2016 *)
a[ n_] := If[ n < 1, Boole[n == 0], (2 n - 1) a[n - 1] + (2 n - 2) a[n - 2]]; (* Michael Somos, Sep 28 2017 *)
a[ n_] := Sum[ (-1)^(n + k) Binomial[n, k] k! 2^k, {k, 0, n}]; (* Michael Somos, Apr 14 2018 *)
a[ n_] := If[ n < 0, 0, (2^n Gamma[n + 1, -1/2]) / Sqrt[E] // FunctionExpand]; (* Michael Somos, Apr 14 2018 *)
a[n_] := n! 2^n Hypergeometric1F1[-n, -n, -1/2];
Table[a[n], {n, 0, 19}]   (* Peter Luschny, Jul 28 2024 *)

my(x='x+O('x^66)); Vec(serlaplace(exp(-x)/(1-2*x))) \\ Joerg Arndt, Apr 15 2013

vector(100, n, n--; sum(k=0, n, (-1)^(n+k)*binomial(n, k)*k!*2^k)) \\ Altug Alkan, Oct 30 2015

{a(n) = if( n<1, n==0, (2*n - 1) * a(n-1) + (2*n - 2) * a(n-2))}; /* Michael Somos, Sep 28 2017 */

Inverse binomial transform of double factorials A000165. - Paul Barry, May 26 2003
a(n) = Sum_{k=0..n} (-1)^(n+k)*C(n, k)*k!*2^k. - Paul Barry, May 26 2003
a(n) = Sum_{k=0..n} A008290(n, k)*2^(n-k). - Philippe Deléham, Dec 13 2003
a(n) = 2*n*a(n-1) + (-1)^n, n > 0, a(0)=1. - Paul Barry, Aug 26 2004
D-finite with recurrence a(n) = (2*n-1)*a(n-1) + (2*n-2)*a(n-2). - Elizabeth McMahon, Gary Gordon (mcmahone(AT)lafayette.edu), Jun 29 2009
From Groux Roland, Jan 17 2011: (Start)
a(n) = (1/(2*sqrt(exp(1))))*Integral_{x>=-1} exp(-x/2)*x^n dx;
Sum_{k>=0} 1/(k!*2^(k+1)*(n+k+1)) = (-1)^n*(a(n)*sqrt(exp(1))-2^n*n!). (End)
a(n) = round(2^n*n!/exp(1/2)), x >= 0. - Simon Plouffe, Mar 1993
G.f.: 1/Q(0), where Q(k) = 1 - x*(4*k+1) - 4*x^2*(k+1)^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Sep 30 2013
From Peter Bala, Jan 30 2015: (Start)
a(n) = Integral_{x = 0..inf} (2*x - 1)^n*exp(-x) dx.
b(n) := 2^n*n! satisfies the recurrence b(n) = (2*n - 1)*b(n-1) + (2*n - 2)*b(n-2), the same recurrence as satisfied by a(n). This leads to the continued fraction representation a(n) = 2^n*n!*( 1/(1 + 1/(1 + 2/(3 + 4/(5 +...+ (2*n - 2)/(2*n - 1) ))))) for n >= 2, which in the limit gives the continued fraction representation sqrt(e) = 1 + 1/(1 + 2/(3 + 4/(5 + ... ))). (End)
For n > 0, a(n) = 1 + 4*Sum_{k=0..n-1} A263895(n). - Vladimir Reshetnikov, Oct 30 2015
a(n) = (-1)^n*(1-2*n*hypergeom([1,1-n],[],2)). - Peter Luschny, May 09 2017
a(n+1) >= A113012(n). - Michael Somos, Sep 28 2017
a(0) = 1; a(n) = Sum_{k=1..n} binomial(n,k) * (2*k - 1) * a(n-k). - Ilya Gutkovskiy, Jan 17 2020
a(n) = 2^n*KummerU(-n, -n, -1/2). - Peter Luschny, May 10 2022
a(n) = 2^n*n!*hypergeom([-n], [-n], -1/2). - Peter Luschny, Jul 28 2024

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.

Original entry on oeis.org

1, 1, 4, 20, 148, 1348, 15104, 198144, 2998656, 51290496, 979732224, 20661458688, 476936766720, 11959743432960, 323764901314560, 9410647116349440, 292316310979706880, 9663569062008422400, 338760229843058688000

Offset: 1

Colin Mallows

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.

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).

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.

Cf. A061714.

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

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 *)

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

Additional comments from David Applegate, Jun 21 2001

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

cp's OEIS Frontend

A000354 Expansion of e.g.f. exp(-x)/(1-2*x).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A120766 Number of ways to seat n people around a circular table such that person i is next to person i-1 or i+1 or both.

Views

Author

Keywords

Programs

PARI

Formula