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

Author

Jeffrey Shallit, Dec 01 2017

Keywords

• nonn

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.

Examples

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

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.

Crossrefs

Column k=0 of A295987.

Cf. A296054.

Programs

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

Formula

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

Extensions

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