A177260 Number of derangements of {1,2,...,n} having no adjacent 4-cycles (an adjacent 4-cycle is a cycle of the form (i,i+1,i+2,i+3)).

1, 0, 1, 2, 8, 44, 262, 1846, 14789, 133232, 1333112, 14669758, 176081478, 2289458896, 32056423888, 480890367598, 7694774125983, 130818028518432, 2354820682603399, 44743035640567412, 894883797133726171, 18792952193893804872, 413452012727711517437

Offset

0,4

Links

Table of n, a(n) for n=0..22.

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

Formula

a(n) = Sum_{s>=0,t>=0,s+4t<=n} (-1)^{s+t}*(n-3*t)!/s!/t!.

a(n) ~ exp(-1) * n!. - Vaclav Kotesovec, Dec 10 2021

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

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

Example

a(6)=262 because among the 265 (= A000166(6)) derangements of {1,2,3,4,5,6} only (1234)(56), (16)(2345), and (12)(3456) have adjacent 4-cycles.

Maple

a := proc (n) local ct, t, s: ct := 0: for s from 0 to n do for t from 0 to (1/4)*n do if s+4*t <= n then ct := ct+(-1)^(s+t)*factorial(n-3*t)/(factorial(s)*factorial(t)) else end if end do end do: ct end proc; seq(a(n), n = 0 .. 22);

Mathematica

a[n_] := Module[{ct = 0, t, s}, For[s = 0, s <= n, s++, For[t = 0, t <= n/3, t++, If[s + 4*t <= n, ct = ct + (-1)^(s + t)*Factorial[n - 3*t] / (Factorial[s]*Factorial[t])]]]; ct];
Table[a[n], {n, 0, 22}] (* Jean-François Alcover, Nov 24 2017, translated from Maple *)

Crossrefs

Cf. A000166, A177258, A177259.

Sequence in context: A362408 A291697 A047851 * A121747 A261266 A014508

Adjacent sequences: A177257 A177258 A177259 * A177261 A177262 A177263

Keyword

nonn

Author

Emeric Deutsch, May 08 2010

Status

approved