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

%I #45 Apr 28 2024 11:38:22

%S 1,1,1,4,19,99,611,4376,35621,324965,3285269,36462924,440840359,

%T 5767387591,81184266631,1223531387056,19657686459529,335404201199049,

%U 6056933308042409,115417137054004820,2314399674388138811,48717810299204919851,1074106226256896375531

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

%H Michael De Vlieger, <a href="/A177249/b177249.txt">Table of n, a(n) for n = 0..449</a>

%H 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 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 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 a(n) = A177248(n,0).

%F Limit_{n->oo} a(n)/n! = 1.

%F a(n) = Sum_{j=0..floor(n/2)} (-1)^j*(n-j)!/j!.

%F a(n) - n*a(n-1) = a(n-2) if n is odd.

%F a(n) - n*a(n-1) = a(n-2) + 2*(-1)^(n/2) if n is even.

%F 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 The e.g.f. G(z) satisfies (1-z)G"(z)-2G'(z)-G(z)=-2cos(z); G(0)=1, G'(0)=1.

%F The o.g.f. is hypergeometric2F0([1,1], [], x/(1+x^2))/(1+x^2). - _Mark van Hoeij_, Nov 08 2011

%F 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 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 G.f.: Sum_{k>=0} k! * x^k / (1+x^2)^(k+1). - _Seiichi Manyama_, Feb 20 2024

%e a(3)=4 because we have (1)(2)(3), (13)(2), (123), and (132).

%p 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 a[n_] := Sum[(-1)^j*(n - j)!/j!, {j, 0, n/2}];

%t Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Nov 20 2017 *)

%o (Magma)

%o [(&+[(-1)^j*Factorial(n-j)/Factorial(j): j in [0..Floor(n/2)]]): n in [0..30]]; // _G. C. Greubel_, Apr 28 2024

%o (SageMath)

%o [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 Cf. A000166, A008290, A177248, A177250, A177251, A177252, A177253.

%K nonn

%O 0,4

%A _Emeric Deutsch_, May 07 2010