A296054 -id:A296054 - cp's OEIS frontend

A295987 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step patterns 010 or 101, where 1=up and 0=down; triangle T(n,k), n >= 0, k = max(0, n-3), read by rows.

1, 1, 2, 6, 14, 10, 52, 36, 32, 204, 254, 140, 122, 1010, 1368, 1498, 620, 544, 5466, 9704, 9858, 9358, 3164, 2770, 34090, 67908, 90988, 72120, 63786, 18116, 15872, 233026, 545962, 762816, 839678, 560658, 470262, 115356, 101042, 1765836, 4604360, 7458522

Offset: 0

Alois P. Heinz, Dec 01 2017

			Triangle T(n,k) begins:
:      1;
:      1;
:      2;
:      6;
:     14,     10;
:     52,     36,     32;
:    204,    254,    140,    122;
:   1010,   1368,   1498,    620,    544;
:   5466,   9704,   9858,   9358,   3164,   2770;
:  34090,  67908,  90988,  72120,  63786,  18116,  15872;
: 233026, 545962, 762816, 839678, 560658, 470262, 115356, 101042;

Alois P. Heinz, Rows n = 0..143, flattened

Column k=0 gives A295974.
Last elements of rows for n>3 give: A001250, A260786, 2*A000111.
Row sums give A000142.
Cf. A227884, A230695, A230797, A231384, A232933, A242783, A242819, A242820, A296054.

b:= proc(u, o, t, h) option remember; expand(
           `if`(u+o=0, 1, `if`(t=0, add(b(u-j, j-1, 1$2), j=1..u),
       add(`if`(h=3, x, 1)*b(u-j, o+j-1, [1, 3, 1][t], 2), j=1..u)+
       add(`if`(t=3, x, 1)*b(u+j-1, o-j, 2, [1, 3, 1][h]), j=1..o))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$3)):
seq(T(n), n=0..12);

b[u_, o_, t_, h_] := b[u, o, t, h] = Expand[If[u + o == 0, 1, If[t == 0, Sum[b[u - j, j - 1, 1, 1], {j, 1, u}], Sum[If[h == 3, x, 1]*b[u - j, o + j - 1, {1, 3, 1}[[t]], 2], {j, 1, u}] + Sum[If[t == 3, x, 1]*b[u + j - 1, o - j, 2, {1, 3, 1}[[h]]], {j, 1, o}]]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, 0, 0, 0]];
Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jun 07 2018, from Maple *)

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

Original entry on oeis.org

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

Jeffrey Shallit, Dec 01 2017

nonn

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.

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

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.

Column k=0 of A295987.

Cf. A296054.

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

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

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

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

cp's OEIS Frontend

A295987 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step patterns 010 or 101, where 1=up and 0=down; triangle T(n,k), n >= 0, k = max(0, n-3), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica