login
A317111
Number of permutations of [n] in which the length of every increasing run is 0 or 1 (mod 4).
14
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
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
Sequence in context: A355153 A268108 A143147 * A337348 A218778 A320521
KEYWORD
easy,nonn
AUTHOR
Ira M. Gessel, Jul 21 2018
STATUS
approved