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

Author

Henry Bottomley, Jan 17 2001

Keywords

• easy
• nonn

Comments

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

Examples

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

Links

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

Programs

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

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

Formula

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

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