A317111 Number of permutations of [n] in which the length of every increasing run is 0 or 1 (mod 4).

1, 1, 1, 1, 2, 10, 50, 210, 840, 4200, 29400, 231000, 1755600, 13213200, 109309200, 1051050000, 11099088000, 120071952000, 1320791472000, 15317750448000, 192286654560000, 2577944809440000, 35885904294240000, 513695427204960000, 7641940962015360000

Offset

0,5

Comments

Similarly, 1/(1 - x + x^2/2! - ... - x^(2m-1)/(2m-1)!) is the e.g.f. for permutations in which every increasing run has length 0 or 1 (mod 2m).

Links

G. C. Greubel, Table of n, a(n) for n = 0..485

David Galvin, John Engbers, and Clifford Smyth, Reciprocals of thinned exponential series, arXiv:2303.14057 [math.CO], 2023.

Ira M. Gessel, Reciprocals of exponential polynomials and permutation enumeration, arXiv:1807.09290 [math.CO], 2018.

Formula

E.g.f.: 1/(1 - x + x^2/2! - x^3/3!).

a(0) = a(1) = a(2) = 1; a(n) = n * a(n-1) - n * (n-1) * a(n-2) / 2 + n * (n-1) * (n-2) * a(n-3) / 6 for n > 2. - Ilya Gutkovskiy, Jan 22 2024

Example

For n=4 the a(4)=2 permutations are 4321 and 1234.

Maple

gser:=series(1/(1-x+x^2/2!-x^3/3!), x, 21): seq(n!*coeff(gser, x, n), n=0..20);

Mathematica

With[{nmax = 25}, CoefficientList[Series[1/(1 -x +x^2/2! -x^3/3!), {x, 0, nmax}], x]*Range[0, nmax]!] (* G. C. Greubel, Nov 30 2018 *)

Prog

(PARI) my(x='x+O('x^25)); Vec(serlaplace(1/(1 -x +x^2/2 -x^3/6))) \\ G. C. Greubel, Nov 30 2018
(Magma) m:=25; R<x>:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!( 1/(1-x+x^2/2-x^3/6) )); [Factorial(n-1)*b[n]: n in [1..m]]; // G. C. Greubel, Nov 30 2018
(Sage)
f= 1/(1 -x +x^2/2 -x^3/6)
g=f.taylor(x, 0, 13)
L=g.coefficients()
coeffs={c[1]:c[0]*factorial(c[1]) for c in L}
coeffs  # G. C. Greubel, Nov 30 2018

Crossrefs

Cf. A097592, A097597.

Sequence in context: A355153 A268108 A143147 * A337348 A218778 A320521

Adjacent sequences: A317108 A317109 A317110 * A317112 A317113 A317114

Keyword

easy,nonn

Author

Ira M. Gessel, Jul 21 2018

Status

approved