A242783 -id:A242783 - 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 *)

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.

A243105 Number of permutations of [n] with exactly ten (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Original entry on oeis.org

28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 298702188259102685572182, 0, 0, 0, 0, 1343764184037862976125525799963820, 0, 0, 0, 0, 0, 899099147941632652542743156466630723477224554496, 0, 0, 89963063825649646755150759614762027655562252125282

Offset: 15

Alois P. Heinz, Aug 19 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 15..130

Column k=10 of A242783.

A246221 Number of permutations of [n] with exactly one occurrence of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Original entry on oeis.org

1, 3, 50, 270, 602, 5376, 139714, 1366016, 15302031, 161855232, 2600075865, 24776769024, 83295229293, 1553561635125, 93399961380678, 2499411984278178, 42789384888638364, 1138928547765375000, 15344070225505482050, 450745170646586005994, 6999343174293499456470

Offset: 3

Alois P. Heinz, Aug 19 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 3..130

Column k=1 of A242783.

A246222 Number of permutations of [n] with exactly two (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Original entry on oeis.org

99, 0, 13303, 530432, 2715243, 14872704, 712988175, 2114735616, 14553496947, 22338508875, 9307563626682, 839345640802598, 8486108520773778, 298020352385025000, 10432593658200450596, 210875469472380711300, 944599826416703171100, 12667164470975664000000

Offset: 7

Alois P. Heinz, Aug 19 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 7..130

Column k=2 of A242783.

A246223 Number of permutations of [n] with exactly three (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Original entry on oeis.org

12, 0, 0, 158720, 74601, 0, 59062275, 17730048, 2099186631, 10006375, 206421198786, 135518026916798, 569885619485772, 13007265031125000, 5556193492800826418, 52483739349674666340, 51836903694327604380, 388109358965377200000, 302747316148839193725590

Offset: 7

Alois P. Heinz, Aug 19 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 7..130

Column k=3 of A242783.

A246224 Number of permutations of [n] with exactly four (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 255577419, 0, 0, 9542007262728, 6774382288791, 0, 2426035607748545873, 7229099931331250350, 1033055991550105110, 2319374753629800000, 19452094129713604966805, 438500213962184713953125, 45449834784068599467011795

Offset: 7

Alois P. Heinz, Aug 19 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 7..130

Column k=4 of A242783.

A246225 Number of permutations of [n] with exactly five (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Original entry on oeis.org

26546042, 0, 0, 222237912664, 0, 0, 902675188454625274, 523709583562561554, 4019286730558350, 0, 380750072712510202319, 378380322018952109375, 6458041428528147414728302, 18033623516991092062500, 51609923138804798955087048, 809786012867038620000000

Offset: 15

Alois P. Heinz, Aug 19 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 15..130

Column k=5 of A242783.

A246226 Number of permutations of [n] with exactly six (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Original entry on oeis.org

2340699, 0, 0, 0, 0, 0, 264152543774143518, 12327936260780536, 0, 0, 0, 0, 672873380447205487461117, 0, 340824919595050237301116, 0, 5490319613423481676641190699, 0, 10557477888680231517368491, 44567941059064479980820469827072, 21711236330372841724318248158224

Offset: 15

Alois P. Heinz, Aug 19 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 15..130

Column k=6 of A242783.

A246227 Number of permutations of [n] with exactly seven (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Original entry on oeis.org

171470, 0, 0, 0, 0, 0, 64556303422787162, 0, 0, 0, 0, 0, 53330837507335912360442, 0, 0, 0, 510289061406183066554328264, 0, 0, 253410955069956058210029266688, 0, 3671524606283906345376361339863458448, 41993835528908638694682902028400861

Offset: 15

Alois P. Heinz, Aug 19 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 15..130

Column k=7 of A242783.

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

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

A243105 Number of permutations of [n] with exactly ten (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Views

Author

Keywords

Links

Crossrefs

A246221 Number of permutations of [n] with exactly one occurrence of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Views

Author

Keywords

Links

Crossrefs

A246222 Number of permutations of [n] with exactly two (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Views

Author

Keywords

Links

Crossrefs

A246223 Number of permutations of [n] with exactly three (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Views

Author

Keywords

Links

Crossrefs

A246224 Number of permutations of [n] with exactly four (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Views

Author

Keywords

Links

Crossrefs

A246225 Number of permutations of [n] with exactly five (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Views

Author

Keywords

Links

Crossrefs

A246226 Number of permutations of [n] with exactly six (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Views

Author

Keywords

Links

Crossrefs

A246227 Number of permutations of [n] with exactly seven (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down.

Views

Author

Keywords

Links

Crossrefs