A173385 The number of permutations that avoid the pattern 122'1', that is, out of four consecutive elements in a permutation we never have the situation that the first two elements form an ascent while the last two elements form a descent.

1, 1, 2, 6, 18, 66, 252, 1176, 5768, 34216, 209552, 1521696, 11196768, 96160416, 825730752, 8183634816, 80315504768, 902135948416, 9960471556352, 125042593153536, 1533993841632768, 21284696790729216, 287227371473636352, 4364939476603385856

Offset

0,3

Links

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

Sergey Kitaev, Partially Ordered Generalized Patterns, preprint.

Sergey Kitaev, Partially Ordered Generalized Patterns, Discrete Math. 298(1-3) (2005), 212-229.

Formula

E.g.f.: (1/2)+(1/4)*tan(x)*(1+exp(2*x) + 2*exp(x)*sin(x)) + (1/2)*exp(x)*cos(x).

a(n) ~ n! * (1 + 2*exp(Pi/2) + exp(Pi) + (-1)^n*(2/exp(Pi/2) - 1/exp(Pi) - 1)) * 2^(n-1) / Pi^(n+1). - Vaclav Kotesovec, Mar 20 2014

Example

Example: a(4) = 18 because the following 6 permutations contain the prohibited pattern: 1243, 1342, 1432, 2341, 2431, 3421.

Maple

b:= proc(u, o, s, t) option remember; `if`(u+o=0, 1,
       `if`(s, 0, add(b(u-j, o+j-1, t, false), j=1..u))+
       add(b(u+j-1, o-j, t, true), j=1..o))
    end:
a:= n-> b(n, 0, false$2):
seq(a(n), n=0..25);  # Alois P. Heinz, Oct 25 2013

Mathematica

CoefficientList[Series[1/2+1/4*Tan[x]*(1+E^(2*x) + 2*E^x*Sin[x]) + 1/2*E^x*Cos[x], {x, 0, 20}], x] * Range[0, 20]! (* Vaclav Kotesovec, Mar 20 2014 *)

Crossrefs

Sequence in context: A150075 A150076 A150077 * A057693 A053496 A079577

Adjacent sequences: A173382 A173383 A173384 * A173386 A173387 A173388

Keyword

nonn

Author

Signy Olafsdottir (signy06(AT)ru.is), Feb 17 2010

Extensions

More terms from Alois P. Heinz, Oct 25 2013

Status

approved