cp's OEIS Frontend

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)).

%I A177259 #27 May 18 2024 15:11:28
%S A177259 1,0,1,1,9,41,258,1809,14575,131660,1320264,14551987,174887262,
%T A177259 2276174790,31895551245,478783042890,7665081036273,130370168718467,
%U A177259 2347620603019159,44620121619435141,892663172726141844,18750621868455013979,412602921349249182309
%N 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)).
%H A177259 G. C. Greubel, <a href="/A177259/b177259.txt">Table of n, a(n) for n = 0..445</a>
%H A177259 R. A. Brualdi and Emeric Deutsch, <a href="http://arxiv.org/abs/1005.0781">Adjacent q-cycles in permutations</a>, arXiv:1005.0781 [math.CO], 2010.
%F A177259 a(n) = Sum_{s=0..n} Sum_{t=0..floor((n-s)/3)} (-1)^(s+t)*(n-2*t)!/(s!*t!).
%F A177259 a(n) ~ exp(-1) * n!. - _Vaclav Kotesovec_, Dec 10 2021
%F A177259 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
%F A177259 G.f.: Sum_{k>=0} k! * x^k / (1+x+x^3)^(k+1). - _Seiichi Manyama_, Feb 22 2024
%e A177259 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.
%p A177259 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);
%t A177259 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];
%t A177259 Table[a[n], {n, 0, 22}] (* _Jean-François Alcover_, Nov 24 2017, translated from Maple *)
%o A177259 (Magma)
%o A177259 F:=Factorial;
%o A177259 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]]) >;
%o A177259 [A177258(n): n in [0..40]]; // _G. C. Greubel_, May 13 2024
%o A177259 (SageMath)
%o A177259 f=factorial;
%o A177259 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))
%o A177259 [A177259(n) for n in range(41)] # _G. C. Greubel_, May 13 2024
%Y A177259 Cf. A000166, A177258, A177260.
%K A177259 nonn
%O A177259 0,5
%A A177259 _Emeric Deutsch_, May 08 2010