A227883 -id:A227883 - cp's OEIS frontend

A177477 Number of permutations of 1..n avoiding adjacent step pattern up, down, up.

1, 1, 2, 6, 19, 70, 331, 1863, 11637, 81110, 635550, 5495339, 51590494, 524043395, 5743546943, 67478821537, 844983073638, 11240221721390, 158365579448315, 2355375055596386, 36870671943986643, 606008531691619131, 10435226671431973345, 187860338952519968538

Offset: 0

Submitted independently by Signy Olafsdottir (signy06(AT)ru.is), May 09 2010 (9 terms) and R. H. Hardin, May 10 2010 (17 terms)

nonn

Suppose a < b, c < b, and c < d. To avoid abcd means not to have four consecutive letters such that the first letter is less than the second one, the third letter is less than the second one, and the third letter is less than the last one.

Alois P. Heinz, Table of n, a(n) for n = 0..468
Sergey Kitaev, Introduction to partially ordered patterns, Discrete Applied Mathematics 155 (2007), 929-944.

Column k=0 of A227884.
Column k=5 of A242784.
Cf. A227883, A245758.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
       add(b(u-j, o+j-1, [1, 3, 1][t]), j=1..u)+
      `if`(t=3, 0, add(b(u+j-1, o-j, 2), j=1..o)))
    end:
a:= n-> b(n, 0, 1):
seq(a(n), n=0..25);  # Alois P. Heinz, Mar 10 2020

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

a(n) ~ c * d^n * n!, where d = A245758 = 0.7827041801715217018447074977..., c = 2.035127405829990832658061124449458067... . - Vaclav Kotesovec, Aug 22 2014

a(18)-a(23) from Alois P. Heinz, Oct 06 2013

a(0)=1 prepended by Alois P. Heinz, Mar 10 2020

A227884 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step pattern up, down, up; triangle T(n,k), n>=0, 0<=k<=max(0,floor(n/2)-1), read by rows.

Original entry on oeis.org

1, 1, 2, 6, 19, 5, 70, 50, 331, 328, 61, 1863, 2154, 1023, 11637, 16751, 10547, 1385, 81110, 144840, 102030, 34900, 635550, 1314149, 1109973, 518607, 50521, 5495339, 12735722, 13046040, 6858598, 1781101, 51590494, 134159743, 157195762, 97348436, 36004400

Offset: 0

Alois P. Heinz, Oct 25 2013

			T(4,1) = 5: 1324, 1423, 2314, 2413, 3412.
Triangle T(n,k) begins:
:  0 :      1;
:  1 :      1;
:  2 :      2;
:  3 :      6;
:  4 :     19,       5;
:  5 :     70,      50;
:  6 :    331,     328,      61;
:  7 :   1863,    2154,    1023;
:  8 :  11637,   16751,   10547,   1385;
:  9 :  81110,  144840,  102030,  34900;
: 10 : 635550, 1314149, 1109973, 518607, 50521;

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

Columns k=0-1 give: A177477, A227883.
T(2n,n-1) gives A000364(n) for n>=2.
Row sums give: A000142.
Cf. A000111, A242783, A242784, A295987.

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

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

A245758 Decimal expansion of a constant related to A232899.

Original entry on oeis.org

7, 8, 2, 7, 0, 4, 1, 8, 0, 1, 7, 1, 5, 2, 1, 7, 0, 1, 8, 4, 4, 7, 0, 7, 4, 9, 7, 7, 3, 4, 6, 0, 9, 0, 5, 5, 0, 2, 1, 3, 1, 2, 9, 5, 0, 9, 4, 8, 6, 3, 7, 5, 1, 4, 7, 7, 5, 8, 3, 1, 8, 5, 2, 0, 8, 6, 5, 0, 8, 9, 7, 3, 8, 9, 0, 8, 8, 4, 7

Offset: 0

Vaclav Kotesovec, Aug 22 2014

			0.78270418017152170184470749773460905502131295094863751477583185208650897389...

Cf. A232899, A177477, A227883.

Equals lim n -> infinity (A232899(n)/n!)^(1/n).
Equals lim n -> infinity (A177477(n)/n!)^(1/n).
Equals lim n -> infinity (A227883(n)/n!)^(1/n).

cp's OEIS Frontend

A177477 Number of permutations of 1..n avoiding adjacent step pattern up, down, up.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A227884 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step pattern up, down, up; triangle T(n,k), n>=0, 0<=k<=max(0,floor(n/2)-1), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A245758 Decimal expansion of a constant related to A232899.

Views

Author

Keywords

Examples

Crossrefs

Formula