A177251 Number of permutations of [n] having no adjacent 3-cycles, i.e., no cycles of the form (i, i+1, i+2).

1, 1, 2, 5, 22, 114, 697, 4923, 39612, 357899, 3588836, 39556420, 475392841, 6187284605, 86701097310, 1301467245329, 20835850494474, 354382860600678, 6381494425302865, 121290065781743383, 2426510081356069016, 50969474697328055063, 1121571023472780698152

Offset

0,3

Links

Seiichi Manyama, 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.

Formula

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

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

a(n) - n*a(n-1) = 2*a(n-3) + 3*(-1)^(n/3) if 3 | n, otherwise a(n) - n*a(n-1) = 2*a(n-3).

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

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

G.f.: hypergeometric2F0([1,1], [], x/(1+x^3))/(1+x^3). - Mark van Hoeij, Nov 08 2011

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

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

Example

a(4)=22 because the only permutations of {1,2,3,4} having adjacent 3-cycles are (123)(4) and (1)(234).

Maple

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

Mathematica

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

Prog

(Magma)
A177251:= func< n | (&+[(-1)^j*Factorial(n-2*j)/Factorial(j): j in [0..Floor(n/3)]]) >;
[A177251(n): n in [0..30]]; // G. C. Greubel, Apr 28 2024
(SageMath)
def A177251(n): return sum((-1)^j*factorial(n-2*j)/factorial(j) for j in range(1+n//3))
[A177251(n) for n in range(31)] # G. C. Greubel, Apr 28 2024

Crossrefs

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

Cf. A370324, A370569.

Sequence in context: A126797 A101206 A294467 * A041807 A228711 A215096

Adjacent sequences: A177248 A177249 A177250 * A177252 A177253 A177254

Keyword

nonn

Author

Emeric Deutsch, May 07 2010

Extensions

Crossreferences corrected by Emeric Deutsch, May 09 2010

Status

approved