A295974 Number of length-n permutations avoiding descent patterns aba and bab.

1, 1, 2, 6, 14, 52, 204, 1010, 5466, 34090, 233026, 1765836, 14534404, 129916550, 1248875862, 12872804422, 141470905326, 1652327596652, 20430973234388, 266683791698634, 3664052636652962, 52859944626536554, 798893924217099426, 12622926284124944660

Offset

0,3

Comments

The descent pattern of a permutation is the sign of the first difference of the permutation, with "a" denoting a rise (+1) and "b" denoting a descent (-1). For example, the permutation 364125 has descent pattern abbaa.

Links

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

Richard Ehrenborg and JiYoon Jung, Descent pattern avoidance, Adv. Appl. Math. 49 (3-5) (2012), 375-390.

Richard Ehrenborg and JiYoon Jung, Descent pattern avoidance, arXiv preprint:1312.2027 [math.CO], 6 Dec 2013.

Formula

Ehrenborg and Jung prove that a(n) ~ 0.8908970548...*(0.6869765032...)^(n-3)*n!.

Example

For n = 4 the 10 permutations NOT counted are 1324, 1423, 2143, 2314, 2413, 3142, 3241, 3412, 4132, 4231.

Maple

b:= proc(u, o, t, h) option remember;
           `if`(u+o=0, 1, `if`(t=0, add(b(u-j, j-1, 1$2), j=1..u),
       add(`if`(h=3, 0, b(u-j, o+j-1, [1, 3, 1][t], 2)), j=1..u)+
       add(`if`(t=3, 0, b(u+j-1, o-j, 2, [1, 3, 1][h])), j=1..o)))
    end:
a:= n-> b(n, 0$3):
seq(a(n), n=0..30);  # Alois P. Heinz, Dec 01 2017

Mathematica

b[u_, o_, t_, h_] := b[u, o, t, h] = If[u + o == 0, 1, If[t == 0, Sum[b[u - j, j - 1, 1, 1], {j, 1, u}], Sum[If[h == 3, 0, b[u - j, o + j - 1, {1, 3, 1}[[t]], 2]], {j, 1, u}] + Sum[If[t == 3, 0, b[u + j - 1, o - j, 2, {1, 3, 1}[[h]]]], {j, 1, o}]]];
a[n_] := b[n, 0, 0, 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Dec 28 2017, after Alois P. Heinz *)

Crossrefs

Column k=0 of A295987.

Cf. A296054.

Sequence in context: A188491 A364677 A355093 * A324365 A346208 A354533

Adjacent sequences: A295971 A295972 A295973 * A295975 A295976 A295977

Keyword

nonn

Author

Jeffrey Shallit, Dec 01 2017

Extensions

a(13)-a(23) from Alois P. Heinz, Dec 01 2017

Status

approved