A242784 -id:A242784 - cp's OEIS frontend

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

1, 1, 2, 6, 24, 116, 4, 672, 48, 4536, 504, 34944, 5376, 302896, 59488, 496, 2916992, 697856, 13952, 30899616, 8720448, 296736, 357080064, 116109312, 5812224, 4470310976, 1645662912, 110697408, 349504, 60269056512, 24776769024, 2114735616, 17730048

Offset: 0

Alois P. Heinz, May 23 2014

			T(5,1) = 4: (1,5,4,3,2), (2,5,4,3,1), (3,5,4,2,1), (4,5,3,2,1).
Triangle T(n,k) begins:
:  0 :        1;
:  1 :        1;
:  2 :        2;
:  3 :        6;
:  4 :       24;
:  5 :      116,       4;
:  6 :      672,      48;
:  7 :     4536,     504;
:  8 :    34944,    5376;
:  9 :   302896,   59488,    496;
: 10 :  2916992,  697856,  13952;
: 11 : 30899616, 8720448, 296736;

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

Column k=0 gives A177518.
Row sums give: A000142.
Cf. 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, 4, 1][t])*`if`(t=4, x, 1), j=1..u)+
      add(b(u+j-1, o-j, 2), 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, 4, 1}[[t]]]*If[t==4, x, 1], {j, 1, u}]+
     Sum[b[u + j - 1, o - j, 2], {j, 1, o}]]];
T[n_] := CoefficientList[b[n, 0, 1], x];
T /@ Range[0, 15] // Flatten (* Jean-François Alcover, Mar 23 2021, after Alois P. Heinz *)

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

Original entry on oeis.org

1, 2, 6, 24, 116, 672, 4536, 34944, 302896, 2916992, 30899616, 357080064, 4470310976, 60269056512, 870591770496, 13414154256384, 219604379097856, 3806644208863232, 69650568655858176, 1341477655028219904, 27128858382696129536, 574755293400886321152

Offset: 1

R. H. Hardin, May 10 2010

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..175

Column k=0 of A242820.

Columns k=8,14 of A242784.

a(n) ~ c * n! / r^n, where r = 1.03841563726655630653502212237531835609230623619708108964... is the root of the equation cos(r) - sin(r) + exp(-r) = 0, and c = 1.1718801964367046779834894478269895859267745270209175... . - Vaclav Kotesovec, Aug 21 2014

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

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

Original entry on oeis.org

1, 1, 2, 6, 24, 109, 588, 3654, 26125, 209863, 1876502, 18441367, 197776850, 2297242583, 28739304385, 385195455471, 5507210188401, 83657067537498, 1345556172013026, 22844387886649418, 408258252653717337, 7660885499702743124, 150600621665021781932

Offset: 0

R. H. Hardin, May 10 2010

nonn

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

Column k=0 of A230695.

Column k=9 of A242784.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t<3, add(b(u+j-1, o-j, 1), j=1..o), 0)+
      add(b(u-j, o+j-1, `if`(t in [0,3], 0, t+1)), j=1..u))
    end:
a:= n-> b(n, 0, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 07 2013

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

a(n) ~ c * d^n * n!, where d = 0.89356257576899599804435763285311831354458355576519..., c = 1.593348415562339201282264582915828860634166516332738... . - Vaclav Kotesovec, Aug 29 2014

a(17)-a(22) from Alois P. Heinz, Oct 07 2013

a(0)=1 from Alois P. Heinz, Apr 20 2022

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

Original entry on oeis.org

1, 1, 2, 6, 24, 104, 528, 3296, 23168, 179712, 1573632, 15207424, 158880768, 1801996288, 22088716288, 289379395584, 4040899657728, 60045059489792, 944460646318080, 15670973219667968, 273813250221277184, 5024207327266603008, 96554813072964845568

Offset: 0

R. H. Hardin, May 10 2010

nonn

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

Column k=0 of A230797.

Column k=10 of A242784.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      add(b(u+j-1, o-j, `if`(t=2, 3, 1)), j=1..o) +`if`(t<3,
      add(b(u-j, o+j-1, `if`(t=1, 2, 0)), j=1..u), 0))
    end:
a:= n-> b(n, 0, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 07 2013

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

a(n) ~ c * d^n * n!, where d = 0.87361286073825385348141673848..., c = 1.678751353034864037734331900009... . - Vaclav Kotesovec, Aug 28 2014

a(17)-a(22) from Alois P. Heinz, Oct 07 2013

A177528 Number of permutations of {1,...,n} avoiding adjacent step pattern up, down, up, down, down.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 685, 4550, 34440, 292320, 2746800, 28402925, 320224500, 3909695400, 51396618000, 723952593000, 10876269801125, 173607227828250, 2934111079914750, 52343975053683000, 982945842995115000, 19381240178451775625, 400347201716808478750

Offset: 0

R. H. Hardin, May 10 2010

nonn

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

Columns k=20,26 of A242784.

Cf. A317639.

b:= proc(u, o, t) option remember; `if`(t>5, 0, `if`(u+o+t<6, (u+o)!,
      add(b(u-j, o+j-1, [1, 3, 1, 5, 6][t]), j=1..u)+
      add(b(u+j-1, o-j, [2, 2, 4, 2, 4][t]), j=1..o)))
    end:
a:= n-> `if`(n=0, 1, add(b(j-1, n-j, 1), j=1..n)):
seq(a(n), n=0..25);  # Alois P. Heinz, Oct 21 2013

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

a(n) ~ c * d^n * n!, where d = 0.93892752514028508419326638408810575968441290684141..., c = 1.4248368339815259677105814450156343177071690245... . - Vaclav Kotesovec, Jan 17 2015

a(17)-a(22) from Alois P. Heinz, Oct 21 2013

A220183 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k triple descents (n>=0,0<=k<=n-3). We say that i is a triple descent of a permutation p if p(i) > p(i+1) > p(i+2) > p(i+3).

Original entry on oeis.org

1, 1, 2, 6, 23, 1, 111, 8, 1, 642, 67, 10, 1, 4326, 602, 99, 12, 1, 33333, 5742, 1093, 137, 14, 1, 288901, 59504, 12425, 1852, 181, 16, 1, 2782082, 666834, 151635, 24970, 3029, 231, 18, 1, 29471046, 8054684, 1981499, 355906, 48455, 4902, 287, 20, 1

Offset: 0

Geoffrey Critzer, Dec 12 2012

Row sums = n!.

T(n,0) = A117158.

			:     1;
:     1;
:     2;
:     6;
:    23,    1;
:   111,    8,    1;
:   642,   67,   10,   1;
:  4326,  602,   99,  12,  1;
: 33333, 5742, 1093, 137, 14, 1;
T(5,1) = 8 because we have: (4,5,3,2,1), (3,5,4,2,1), (2,5,4,3,1), (5,4,3,1,2), (1,5,4,3,2), (5,4,2,1,3), (5,3,2,1,4), (4,3,2,1,5).

Alois P. Heinz, Rows n = 0..143, flattened
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 210

Cf. A162975, A242783, A242784.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
      add(b(u-j, o+j-1, 1), j=1..u)+
      add(b(u+j-1, o-j, [2, 3, 3][t])*`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..14);  # Alois P. Heinz, Oct 29 2013

nn=10; u=y-1; a=Apply[Plus, Table[Normal[Series[y x^4/(1-y x - y x^2-y x^3), {x,0,nn}]][[n]]/(n+3)!, {n,1,nn-3}]]/.y->u; Range[0,nn]! CoefficientList[Series[1/(1-x-a), {x,0,nn}], {x,y}]//Grid

E.g.f.: 1/(1 - x - Sum_{k,n} I(n,k)(y - 1)^k*x^n/n!) where I(n,k) is the coefficient of y^k*x^n in the ordinary generating function expansion of y x^4/(1 - y*x - y*x^2 - y*x^3) See Flajolet and Sedgewick reference in Links section.

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

Original entry on oeis.org

1, 1, 2, 6, 24, 111, 612, 3906, 28701, 236527, 2167862, 21824925, 239861934, 2854894485, 36602472117, 502718236303, 7365503262033, 114653301213668, 1889769527067410, 32877891905367530, 602116339324675145, 11578253045158664158, 233244225298760907868

Offset: 0

R. H. Hardin, May 10 2010

nonn

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

Columns k=11,13 of A242784.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1, `if`(t<3,
      add(b(u+j-1, o-j, `if`(t=2, 3, 1)), j=1..o), 0)+
      add(b(u-j, o+j-1, `if`(irem(t, 2)=0, 0, 2)), j=1..u))
    end:
a:= n-> b(n, 0, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 07 2013

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

a(n) ~ c * d^n * n!, where d = 0.91568163084580807076940792182223499091165..., c = 1.44100339681864767911275854344010332196608... . - Vaclav Kotesovec, Aug 29 2014

a(17)-a(22) from Alois P. Heinz, Oct 07 2013

a(0)=1 from Alois P. Heinz, Apr 20 2022

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

Original entry on oeis.org

1, 1, 2, 6, 24, 114, 648, 4284, 32256, 273616, 2578352, 26725776, 302273664, 3703441104, 48865510848, 690823736064, 10417318281216, 166907223390976, 2831507368842752, 50703852290781696, 955742450175919104, 18916030525704006144, 392213482250102734848

Offset: 0

R. H. Hardin, May 10 2010

nonn

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

Column k=12 of A242784.

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      add(b(u+j-1, o-j, `if`(t in [0, 3], 1, 2)), j=1..o)+`if`(t<3,
      add(b(u-j, o+j-1, `if`(t=2, 3, 0)), j=1..u), 0))
    end:
a:= n-> b(n, 0, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 07 2013

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

a(n) ~ c * d^n * n!, where d = 0.942475018599378010857210678432739023432859616925664352..., c = 1.284751954587372264742653082845227922651555734159194626... . - Vaclav Kotesovec, Aug 29 2014

a(17)-a(22) from Alois P. Heinz, Oct 07 2013

a(0)=1 from Alois P. Heinz, Apr 20 2022

A177524 Number of permutations of {1,...,n} avoiding adjacent step pattern up, down, down, down, down.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 715, 4970, 39480, 352800, 3502800, 38255900, 455795100, 5883052500, 81774966000, 1217871018000, 19346879737625, 326549862671250, 5835951345093750, 110091785625495000, 2186122850020215000, 45580964489553559375, 995625115672520581250

Offset: 0

R. H. Hardin, May 10 2010

nonn

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

Columns k=16,30 of A242784.

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

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

a(n) ~ c * d^n * n!, where d = 0.9928637443921790380857377558103269268777241137790934589694993..., c = 1.0369478195304845650491426260146999487076420703190374702807322... . - Vaclav Kotesovec, Aug 29 2014

a(17)-a(22) from Alois P. Heinz, Oct 20 2013

A177525 Number of permutations of {1,...,n} avoiding adjacent step pattern up, down, down, down, up.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 701, 4774, 37128, 324576, 3153961, 33709743, 393044544, 4964774568, 67536381485, 984328864872, 15302821821071, 252773481889854, 4420945845050347, 81616873102658977, 1586065426493434829, 32363206963164145993, 691807691094619216393

Offset: 0

R. H. Hardin, May 10 2010

nonn

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

Column k=17 of A242784.

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

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

a(n) ~ c * d^n * n!, where d = 0.971652908773770631708593889167049741726729704564696579529716779..., c = 1.15870633318154171410681190800508780736090448111042904596... . - Vaclav Kotesovec, Jan 17 2015

a(17)-a(22) from Alois P. Heinz, Oct 21 2013

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A177528 Number of permutations of {1,...,n} avoiding adjacent step pattern up, down, up, down, down.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A220183 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} having k triple descents (n>=0,0<=k<=n-3). We say that i is a triple descent of a permutation p if p(i) > p(i+1) > p(i+2) > p(i+3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Links