cp's OEIS Frontend

A177249 Number of permutations of [n] having no adjacent transpositions, that is, no cycles of the form (i, i+1).

%I A177249 #45 Apr 28 2024 11:38:22
%S A177249 1,1,1,4,19,99,611,4376,35621,324965,3285269,36462924,440840359,
%T A177249 5767387591,81184266631,1223531387056,19657686459529,335404201199049,
%U A177249 6056933308042409,115417137054004820,2314399674388138811,48717810299204919851,1074106226256896375531
%N A177249 Number of permutations of [n] having no adjacent transpositions, that is, no cycles of the form (i, i+1).
%H A177249 Michael De Vlieger, <a href="/A177249/b177249.txt">Table of n, a(n) for n = 0..449</a>
%H A177249 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.
%H A177249 Anders Claesson, <a href="https://akc.is/papers/036-From-Hertzsprungs-problem-to-pattern-rewriting-systems.pdf">From Hertzsprung's problem to pattern-rewriting systems</a>, University of Iceland (2020).
%H A177249 Anders Claesson and Henning Ulfarsson, <a href="https://akc.is/papers/041-Turning-cycle-restrictions-into-mesh-patterns.pdf">Turning cycle restrictions into mesh patterns via Foata's fundamental transformation</a>, Univ. of Iceland (2023).
%F A177249 a(n) = A177248(n,0).
%F A177249 Limit_{n->oo} a(n)/n! = 1.
%F A177249 a(n) = Sum_{j=0..floor(n/2)} (-1)^j*(n-j)!/j!.
%F A177249 a(n) - n*a(n-1) = a(n-2) if n is odd.
%F A177249 a(n) - n*a(n-1) = a(n-2) + 2*(-1)^(n/2) if n is even.
%F A177249 The o.g.f. g(z) satisfies z^2*(1+z^2)*g'(z)-(1+z^2)(1-z-z^2)g(z)+1-z^2=0; g(0)=1.
%F A177249 The e.g.f. G(z) satisfies (1-z)G"(z)-2G'(z)-G(z)=-2cos(z); G(0)=1, G'(0)=1.
%F A177249 The o.g.f. is hypergeometric2F0([1,1], [], x/(1+x^2))/(1+x^2). - _Mark van Hoeij_, Nov 08 2011
%F A177249 G.f.: 1/Q(0), where Q(k)= 1 + x^2 - x*(k+1)/(1-x*(k+1)/Q(k+1)); (continued fraction). - _Sergei N. Gladkovskii_, Apr 20 2013
%F A177249 D-finite with recurrence a(n) = n*a(n-1) + (n-2)*a(n-3) + a(n-4). - _R. J. Mathar_, Jul 26 2022
%F A177249 G.f.: Sum_{k>=0} k! * x^k / (1+x^2)^(k+1). - _Seiichi Manyama_, Feb 20 2024
%e A177249 a(3)=4 because we have (1)(2)(3), (13)(2), (123), and (132).
%p A177249 a := proc (n) options operator, arrow: sum((-1)^j*factorial(n-j)/factorial(j), j = 0 .. floor((1/2)*n)) end proc: seq(a(n), n = 0 .. 22);
%t A177249 a[n_] := Sum[(-1)^j*(n - j)!/j!, {j, 0, n/2}];
%t A177249 Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Nov 20 2017 *)
%o A177249 (Magma)
%o A177249 [(&+[(-1)^j*Factorial(n-j)/Factorial(j): j in [0..Floor(n/2)]]): n in [0..30]]; // _G. C. Greubel_, Apr 28 2024
%o A177249 (SageMath)
%o A177249 [sum((-1)^j*factorial(n-j)/factorial(j) for j in range(1+n//2)) for n in range(31)] # _G. C. Greubel_, Apr 28 2024
%Y A177249 Cf. A000166, A008290, A177248, A177250, A177251, A177252, A177253.
%K A177249 nonn
%O A177249 0,4
%A A177249 _Emeric Deutsch_, May 07 2010