cp's OEIS Frontend

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

%I A177253 #33 May 12 2024 11:29:21
%S A177253 1,1,2,6,23,118,714,5016,40201,362163,3623772,39876540,478639079,
%T A177253 6223394516,87138394540,1307195547720,20916564680761,355600269756485,
%U A177253 6401066270800350,121624180731849810,2432546364331038479,51084540451761077514,1123879093137556106358
%N A177253 Number of permutations of [n] having no adjacent 4-cycles, i.e., no cycles of the form (i, i+1, i+2, i+3).
%H A177253 Seiichi Manyama, <a href="/A177253/b177253.txt">Table of n, a(n) for n = 0..449</a>
%H A177253 Richard 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 A177253 a(n) = Sum_{j=0..floor(n/4)} (-1)^j*(n-3*j)!/j!.
%F A177253 a(n) - n*a(n-1) = 3*a(n-4) + 4*(-1)^{n/4} if 4|n otherwise a(n) - n*a(n-1) = 3*a(n-4).
%F A177253 a(n) = A177252(n,0).
%F A177253 limit_{n->oo} a(n)/n! = 1.
%F A177253 The o.g.f. g(z) satisfies z^2*(1+z^4)*g'(z) - (1+z^4)(1-z-3z^4)g(z) + 1 - 3z^4 = 0; g(0)=1.
%F A177253 D-finite with recurrence a(n) = n*a(n-1) + 2*a(n-4) + (n-4)*a(n-5) + 3*a(n-8). - _R. J. Mathar_, Jul 26 2022
%F A177253 G.f.: Sum_{k>=0} k! * x^k / (1+x^4)^(k+1). - _Seiichi Manyama_, Feb 20 2024
%e A177253 a(5)=118 because the only permutations of {1,2,3,4,5} having adjacent 4-cycles are (1234)(5) and (1)(2345).
%p A177253 a := proc (n) options operator, arrow: sum((-1)^j*factorial(n-3*j)/factorial(j), j = 0 .. floor((1/4)*n)) end proc: seq(a(n), n = 0 .. 22);
%t A177253 a[n_] := Sum[(-1)^j*(n - 3*j)!/j!, {j, 0, n/4}];
%t A177253 Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Nov 20 2017 *)
%o A177253 (Magma)
%o A177253 [(&+[(-1)^j*Factorial(n-3*j)/Factorial(j): j in [0..Floor(n/4)]]): n in [0..30]]; // _G. C. Greubel_, May 11 2024
%o A177253 (SageMath)
%o A177253 [sum((-1)^j*factorial(n-3*j)/factorial(j) for j in range(1+n//4)) for n in range(31)] # _G. C. Greubel_, May 11 2024
%Y A177253 Cf. A000166, A008290, A177248, A177249, A177250, A177251, A177252.
%K A177253 nonn
%O A177253 0,3
%A A177253 _Emeric Deutsch_, May 07 2010
%E A177253 Crossreferences corrected by _Emeric Deutsch_, May 09 2010