A177528 -id:A177528 - cp's OEIS frontend

A242784 Number A(n,k) of permutations of [n] avoiding the consecutive step pattern given by the binary expansion of k, where 1=up and 0=down; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 4, 1, 1, 1, 1, 2, 5, 8, 1, 1, 1, 1, 2, 6, 17, 16, 1, 1, 1, 1, 2, 6, 21, 70, 32, 1, 1, 1, 1, 2, 6, 19, 90, 349, 64, 1, 1, 1, 1, 2, 6, 21, 70, 450, 2017, 128, 1, 1, 1, 1, 2, 6, 23, 90, 331, 2619, 13358, 256, 1, 1

Offset: 0

Alois P. Heinz, May 22 2014

			A(4,5) = 19 because there are 4! = 24 permutations of {1,2,3,4} and only 5 of them do not avoid the consecutive step pattern up, down, up given by the binary expansion of 5 = 101_2: (1,3,2,4), (1,4,2,3), (2,3,1,4), (2,4,1,3), (3,4,1,2).
Square array A(n,k) begins:
  1, 1,   1,     1,     1,     1,     1,     1,     1, ...
  1, 1,   1,     1,     1,     1,     1,     1,     1, ...
  1, 1,   2,     2,     2,     2,     2,     2,     2, ...
  1, 1,   4,     5,     6,     6,     6,     6,     6, ...
  1, 1,   8,    17,    21,    19,    21,    23,    24, ...
  1, 1,  16,    70,    90,    70,    90,   111,   116, ...
  1, 1,  32,   349,   450,   331,   450,   642,   672, ...
  1, 1,  64,  2017,  2619,  1863,  2619,  4326,  4536, ...
  1, 1, 128, 13358, 17334, 11637, 17334, 33333, 34944, ...

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

Columns give: 0, 1: A000012, 2: A011782, 3: A049774, 4, 6: A177479, 5: A177477, 7: A117158, 8, 14: A177518, 9: A177519, 10: A177520, 11, 13: A177521, 12: A177522, 15: A177523, 16, 30: A177524, 17: A177525, 18, 22: A177526, 19, 25: A177527, 20, 26: A177528, 21: A177529, 23, 29: A177530, 24, 28: A177531, 27: A177532, 31: A177533, 32, 62: A177534, 33: A177535, 34, 46: A177536, 35, 49: A177537, 36, 54: A177538, 37, 41: A177539, 38: A177540, 39, 57: A177541, 40, 58: A177542, 42: A177543, 43, 53: A177544, 44, 50: A177545, 45: A177546, 47, 61: A177547, 48, 60: A177548, 51: A177549, 52: A177550, 55, 59: A177551, 56: A177552, 63: A177553, 127: A230051, 255: A230231, 511: A230232, 1023: A230233, 2047: A254523.
Main diagonal gives A242785.
Cf. A242783, A335308.

A:= proc(n, k) option remember; local b, m, r, h;
      if k<2 then return 1 fi;
      m:= iquo(k, 2, 'r'); h:= 2^ilog2(k);
      b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t=m and r=0, 0, add(b(u-j, o+j-1, irem(2*t, h)), j=1..u))+
      `if`(t=m and r=1, 0, add(b(u+j-1, o-j, irem(2*t+1, h)), j=1..o)))
      end; forget(b);
      b(n, 0, 0)
    end:
seq(seq(A(n, d-n), n=0..d), d=0..15);

Clear[A]; A[n_, k_] := A[n, k] = Module[{b, m, r, h}, If[k < 2, Return[1]]; {m, r} = QuotientRemainder[k, 2]; h = 2^Floor[Log[2, k]]; b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, If[t == m && r == 0, 0, Sum[b[u - j, o + j - 1, Mod[2*t, h]], {j, 1, u}]] + If[t == m && r == 1, 0, Sum[b[u + j - 1, o - j, Mod[2*t + 1, h]], {j, 1, o}]]]; b[n, 0, 0]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 15}] // Flatten (* Jean-François Alcover, Sep 22 2014, translated from Maple *)

A317639 Number of equivalence classes of Dyck paths of semilength n for the consecutive pattern UDUDD, where U=(1,1) and D=(1,-1).

Original entry on oeis.org

1, 1, 1, 2, 4, 6, 10, 19, 32, 54, 98, 170, 292, 520, 909, 1577, 2787, 4883, 8515, 14998, 26299, 45984, 80863, 141844, 248381, 436406, 765649, 1341844, 2356500, 4134749, 7249981, 12728630, 22335110, 39174776, 68766785, 120670190, 211689586, 371558266, 652014636

Offset: 0

Alois P. Heinz, Aug 02 2018

nonn

Two Dyck paths of the same length are equivalent with respect to a given pattern if they have equal sets of occurrences of this pattern.

Alois P. Heinz, Table of n, a(n) for n = 0..4096
J.-L. Baril, A. Petrossian, Equivalence classes of Dyck paths modulo some statistics, 2014.
J.-L. Baril, A. Petrossian, Equivalence Classes of Motzkin Paths Modulo a Pattern of Length at Most Two, J. Int. Seq. 18 (2015) 15.7.1
K. Manes, A. Sapounakis, I. Tasoulas, P. Tsikouras, Equivalence classes of ballot paths modulo strings of length 2 and 3, arXiv:1510.01952 [math.CO], 2015.
Wikipedia, Counting lattice paths

Cf. A000108, A001519, A177528, A244885, A244886, A274114, A274115, A274289.

b:= proc(x, y) option remember; `if`(y<0 or y>x, 0, `if`(x=0, 1,
     `if`(y=0, b(x-2, y)+b(x-6, y+2), b(x-1, y-1))+b(x-5, y+1)))
    end:
a:= n-> b(2*n, 0):
seq(a(n), n=0..42);

b[x_, y_] := b[x, y] = If[y < 0 || y > x, 0, If[x == 0, 1, If[y == 0, b[x - 2, y] + b[x - 6, y + 2], b[x - 1, y - 1]] + b[x - 5, y + 1]]];
a[n_] := b[2n, 0];
Table[a[n], {n, 0, 42}] (* Jean-François Alcover, Aug 20 2018, from Maple *)

cp's OEIS Frontend

A242784 Number A(n,k) of permutations of [n] avoiding the consecutive step pattern given by the binary expansion of k, where 1=up and 0=down; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica