A177249 Number of permutations of [n] having no adjacent transpositions, that is, no cycles of the form (i, i+1).
1, 1, 1, 4, 19, 99, 611, 4376, 35621, 324965, 3285269, 36462924, 440840359, 5767387591, 81184266631, 1223531387056, 19657686459529, 335404201199049, 6056933308042409, 115417137054004820, 2314399674388138811, 48717810299204919851, 1074106226256896375531
Offset: 0
Keywords
Examples
a(3)=4 because we have (1)(2)(3), (13)(2), (123), and (132).
Links
- Michael De Vlieger, Table of n, a(n) for n = 0..449
- R. A. Brualdi and Emeric Deutsch, Adjacent q-cycles in permutations, arXiv:1005.0781 [math.CO], 2010.
- Anders Claesson, From Hertzsprung's problem to pattern-rewriting systems, University of Iceland (2020).
- Anders Claesson and Henning Ulfarsson, Turning cycle restrictions into mesh patterns via Foata's fundamental transformation, Univ. of Iceland (2023).
Programs
-
Magma
[(&+[(-1)^j*Factorial(n-j)/Factorial(j): j in [0..Floor(n/2)]]): n in [0..30]]; // G. C. Greubel, Apr 28 2024
-
Maple
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);
-
Mathematica
a[n_] := Sum[(-1)^j*(n - j)!/j!, {j, 0, n/2}]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Nov 20 2017 *) -
SageMath
[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
Formula
a(n) = A177248(n,0).
Limit_{n->oo} a(n)/n! = 1.
a(n) = Sum_{j=0..floor(n/2)} (-1)^j*(n-j)!/j!.
a(n) - n*a(n-1) = a(n-2) if n is odd.
a(n) - n*a(n-1) = a(n-2) + 2*(-1)^(n/2) if n is even.
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.
The e.g.f. G(z) satisfies (1-z)G"(z)-2G'(z)-G(z)=-2cos(z); G(0)=1, G'(0)=1.
The o.g.f. is hypergeometric2F0([1,1], [], x/(1+x^2))/(1+x^2). - Mark van Hoeij, Nov 08 2011
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
D-finite with recurrence a(n) = n*a(n-1) + (n-2)*a(n-3) + a(n-4). - R. J. Mathar, Jul 26 2022
G.f.: Sum_{k>=0} k! * x^k / (1+x^2)^(k+1). - Seiichi Manyama, Feb 20 2024