|
|
A177259
|
|
Number of derangements of {1,2,...,n} having no adjacent 3-cycles (an adjacent 3-cycle is a cycle of the form (i,i+1,i+2)).
|
|
4
|
|
|
1, 0, 1, 1, 9, 41, 258, 1809, 14575, 131660, 1320264, 14551987, 174887262, 2276174790, 31895551245, 478783042890, 7665081036273, 130370168718467, 2347620603019159, 44620121619435141, 892663172726141844, 18750621868455013979, 412602921349249182309
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{s=0..n} Sum_{t=0..floor((n-s)/3)} (-1)^(s+t)*(n-2*t)!/(s!*t!).
Conjecture: D-finite with recurrence a(n) = (n-1)*a(n-1) + (n-1)*a(n-2) + a(n-3) + (n-1)*a(n-4) + 2*a(n-6). - R. J. Mathar, Jul 26 2022
G.f.: Sum_{k>=0} k! * x^k / (1+x+x^3)^(k+1). - Seiichi Manyama, Feb 22 2024
|
|
EXAMPLE
|
a(5)=41 because among the 44 (= A000166(5)) derangements of {1,2,3,4,5} only (12)(345), (123)(45), and (15)(234) have adjacent 3-cycles.
|
|
MAPLE
|
a := proc (n) local ct, t, s: ct := 0: for s from 0 to n do for t from 0 to (1/3)*n do if s+3*t <= n then ct := ct+(-1)^(s+t)*factorial(n-2*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 + 3*t <= n, ct = ct + (-1)^(s + t)*Factorial[n - 2*t] / (Factorial[s]*Factorial[t])]]]; ct];
|
|
PROG
|
(Magma)
F:=Factorial;
A177258:= func< n | (&+[(&+[(-1)^(j+k)*F(n-2*k)/(F(j)*F(k)): k in [0..Floor((n-j)/3)]]): j in [0..n]]) >;
(SageMath)
f=factorial;
def A177259(n): return sum(sum((-1)^(j+k)*f(n-2*k)/(f(j)*f(k)) for k in range(1+(n-j)//3)) for j in range(n+1))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|