A177249 Number of permutations of [n] having no adjacent transpositions, that is, no cycles of the form (i, i+1).

1, 1, 1, 4, 19, 99, 611, 4376, 35621, 324965, 3285269, 36462924, 440840359, 5767387591, 81184266631, 1223531387056, 19657686459529, 335404201199049, 6056933308042409, 115417137054004820, 2314399674388138811, 48717810299204919851, 1074106226256896375531

Offset

0,4

Links

Michael De Vlieger, Table of n, a(n) for n = 0..449

R. A. Brualdi and Emeric Deutsch, Adjacent q-cycles in permutations, arXiv:1005.0781 [math.CO], 2010.

Anders Claesson, From Hertzsprung's problem to pattern-rewriting systems, University of Iceland (2020).

Anders Claesson and Henning Ulfarsson, Turning cycle restrictions into mesh patterns via Foata's fundamental transformation, Univ. of Iceland (2023).

Formula

a(n) = A177248(n,0).

Limit_{n->oo} a(n)/n! = 1.

a(n) = Sum_{j=0..floor(n/2)} (-1)^j*(n-j)!/j!.

a(n) - n*a(n-1) = a(n-2) if n is odd; a(n) - n*a(n-1)=a(n-2)+2*(-1)^{n/2} if n is even.

The o.g.f. g(z) satisfies z^2*(1+z^2)*g'(z)-(1+z^2)(1-z-z^2)g(z)+1-z^2=0; g(0)=1.

The e.g.f. G(z) satisfies (1-z)G"(z)-2G'(z)-G(z)=-2cos(z); G(0)=1, G'(0)=1.

The o.g.f. is hypergeom([1,1],[],x/(1+x^2))/(1+x^2) in Maple notation. - Mark van Hoeij, Nov 08 2011

G.f.: 1/Q(0), where Q(k)= 1 + x^2 - x*(k+1)/(1-x*(k+1)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, Apr 20 2013

D-finite with recurrence a(n) -n*a(n-1) +(-n+2)*a(n-3) -a(n-4)=0. - R. J. Mathar, Jul 26 2022

G.f.: Sum_{k>=0} k! * x^k / (1+x^2)^(k+1). - Seiichi Manyama, Feb 20 2024

Example

a(3)=4 because we have (1)(2)(3), (13)(2), (123), and (132).

Maple

a := proc (n) options operator, arrow: sum((-1)^j*factorial(n-j)/factorial(j), j = 0 .. floor((1/2)*n)) end proc: seq(a(n), n = 0 .. 22);

Mathematica

a[n_] := Sum[(-1)^j*(n - j)!/j!, {j, 0, n/2}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Nov 20 2017 *)

Crossrefs

Cf. A000166, A008290, A177248, A177250, A177251, A177252, A177253.

Sequence in context: A327115 A370024 A306511 * A083882 A007564 A218185

Adjacent sequences: A177246 A177247 A177248 * A177250 A177251 A177252

Keyword

nonn

Author

Emeric Deutsch, May 07 2010

Status

approved