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

Author

Ira M. Gessel, Jul 21 2018

Keywords

• easy
• nonn

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).

Examples

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

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.

Crossrefs

Cf. A097592, A097597.

Programs

Magma

m:=25; R:=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

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 *)

PARI

my(x='x+O('x^25)); Vec(serlaplace(1/(1 -x +x^2/2 -x^3/6))) \\ 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

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