OFFSET
0,4
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..445
R. A. Brualdi and Emeric Deutsch, Adjacent q-cycles in permutations, arXiv:1005.0781 [math.CO], 2010.
FORMULA
a(n) = Sum_{s=0..n} Sum_{t=0..floor((n-s)/4)} (-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). - 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 *)
PROG
(Magma)
F:=Factorial;
A177258:= func< n | (&+[(&+[(-1)^(j+k)*F(n-3*k)/(F(j)*F(k)): k in [0..Floor((n-j)/4)]]): j in [0..n]]) >;
[A177258(n): n in [0..40]]; // G. C. Greubel, May 13 2024
(SageMath)
f=factorial;
def A177260(n): return sum(sum((-1)^(j+k)*f(n-3*k)/(f(j)*f(k)) for k in range(1+(n-j)//4)) for j in range(n+1))
[A177260(n) for n in range(41)] # G. C. Greubel, May 13 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, May 08 2010
STATUS
approved