A059204 Number of non-unimodal permutations of n items (i.e., those which do not simply go up for the first part and then down for the rest, but at some point go down then up).

0, 0, 0, 2, 16, 104, 688, 4976, 40192, 362624, 3628288, 39915776, 478999552, 6227016704, 87178283008, 1307674351616, 20922789855232, 355687428030464, 6402373705596928, 121645100408569856, 2432902008176115712, 51090942171708391424, 1124000727777605582848

Offset

0,4

Comments

Number of permutations of [n] minus the number of compositions of n. - Zerinvary Lajos, Oct 16 2006

Links

Alois P. Heinz, Table of n, a(n) for n = 0..250

Formula

a(n) = n! - ceiling(2^(n-1)) = A000142(n) - A011782(n).

E.g.f.: (1+x)/(2*(1-x))-exp(2*x)/2.

Example

a(3) = 2 since the possibilities are {BAC, CAB}. a(4) = 16 since the possibilites are {ACBD, ADBC, BACD, BADC, BCAD, BDAC, CABD, CADB, CBAD, CBDA, CDAB, DABC, DACB, DBAC, DBCA, DCAB}.

Maple

a:= n-> n!-ceil(2^(n-1)):
seq(a(n), n=0..30);

Mathematica

nn=30; Range[0, nn]!CoefficientList[Series[1/(1-x)-Exp[2x]/2-1/2, {x, 0, nn}], x] (* Geoffrey Critzer, Mar 17 2014 *)

Prog

(PARI) x= 'x + O('x^50); concat([0, 0, 0], Vec(serlaplace((1+x)/(2*(1-x))-exp(2*x)/2))) \\ G. C. Greubel, Dec 28 2016

Crossrefs

Sequence in context: A208022 A207803 A370823 * A187248 A236958 A009619

Adjacent sequences: A059201 A059202 A059203 * A059205 A059206 A059207

Keyword

easy,nonn

Author

Henry Bottomley, Jan 17 2001

Status

approved