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

A177470 Number of permutations of order n avoiding the consecutive pattern 11'22'.

Original entry on oeis.org

1, 1, 2, 6, 18, 70, 300, 1435, 7910, 47376, 316008, 2314158, 18331236, 158024724, 1462752720, 14497475850, 153488070450, 1724035906450, 20515906356660, 257720354712106, 3406481187714176, 47293781230517640, 687760952277462336, 10456003715906638162, 165890170459303164420

Offset: 0

Signy Olafsdottir (signy06(AT)ru.is), May 09 2010

nonn

To avoid 11'22' means not to have four consecutive letters such that the first letter is less than the third one and the second letter is less than the fourth one.

S. Kitaev, Introduction to partially ordered patterns, Discrete Applied Mathematics 155 (2007), 929-944.
Rémy Sigrist, C program

Cf. A117156, A177471, A177472, A177473, A177475, A177476, A177477, A177478, A177479, A177480, A177481, A177482, A177483, A177484, A376694.

C
```
// See Links section.
```

a(0) = 1 and a(10)-a(16) from Rémy Sigrist, Mar 13 2023

Edited and a(17)-a(24) added by Max Alekseyev, Oct 01 2024

A376694 Number of permutations of order n avoiding consecutive pattern 121'3.

Original entry on oeis.org

1, 1, 2, 6, 22, 100, 548, 3482, 25256, 206298, 1871704, 18676354, 203323724, 2397969518, 30455963576, 414446765490, 6015821216380, 92778775395190, 1515047281161392, 26114701159308242, 473827422862284740, 9027024454944900390, 180165845677134636856, 3759286756628732868754, 81850596163629861103004

Offset: 0

Max Alekseyev, Oct 01 2024

nonn

To avoid 121'3 means not to have four consecutive letters such that the first letter and the third one is less than the second, and the second one is less than and the fourth one.

S. Kitaev, Introduction to partially ordered patterns, Discrete Applied Mathematics 155 (2007), 929-944. [WARNING: The sequence is erroneously given as 1, 2, 6, 20, 83, 411, ...]

Cf. A117156, A177470, A177471, A177472, A177473, A177475, A177476, A177477, A177478, A177479, A177480, A177481, A177482, A177483, A177484.

A177472 Number of permutations of order n avoiding the consecutive pattern 11'2'2.

Original entry on oeis.org

1, 1, 2, 6, 18, 71, 322, 1665, 9789, 64327, 468914, 3748920, 32699022, 308710917, 3138821688, 34186918427, 397173376849, 4902547569617, 64073734206528, 883940288032392, 12836250526983672, 195724485831901029, 3126468139092090818, 52211816154041174670, 909843384081141844312

Offset: 0

Signy Olafsdottir (signy06(AT)ru.is), May 09 2010

nonn

To avoid 11'2'2 means not to have four consecutive letters such that the first letter is less than the last one, and the second letter is less than the third one.

S. Kitaev, Introduction to partially ordered patterns, Discrete Applied Mathematics 155 (2007), 929-944.

Cf. A117156, A177470, A177471, A177473, A177475, A177476, A177477, A177478, A177479, A177480, A177481, A177482, A177483, A177484, A376694.

Edited and terms a(0), a(10)-a(24) added by Max Alekseyev, Oct 02 2024

A177473 Number of permutations of order n avoiding the consecutive pattern 12'1'2.

Original entry on oeis.org

1, 1, 2, 6, 18, 61, 272, 1410, 8048, 51550, 372995, 2976679, 25686748, 239687103, 2419267562, 26194183096, 301838412516, 3692782460824, 47891164866100, 655887513203263, 9449915113835659, 142923476094740969, 2265214890150056647, 37539217881003574022, 649054317768293760078

Offset: 0

Signy Olafsdottir (signy06(AT)ru.is), May 09 2010

nonn

To avoid 12'1'2 means not to have four consecutive letters such that the first one is less than the fourth letter and the second letter is larger than the third one.

S. Kitaev, Introduction to partially ordered patterns, Discrete Applied Mathematics 155 (2007), 929-944.

Cf. A117156, A177470, A177471, A177472, A177475, A177476, A177477, A177478, A177479, A177480, A177481, A177482, A177483, A177484, A376694.

Edited and terms a(0), a(10)-a(24) added by Max Alekseyev, Oct 01 2024

A177475 Number of permutations of order n avoiding the consecutive pattern 131'2.

Original entry on oeis.org

1, 1, 2, 6, 20, 81, 390, 2161, 13678, 96983, 764368, 6630898, 62748250, 643442919, 7104914398, 84062375725, 1060919238874, 14226075039395, 201982580807466, 3027049675655253, 47753241018325280, 790998083929598213, 13726222157931958274, 249018700470309832015, 4714071198944211367704

Offset: 0

Signy Olafsdottir (signy06(AT)ru.is), May 09 2010

nonn

To avoid 131'2 means not to have four consecutive letters such that if the third letter is removed, then in the obtained 3 letter word the smallest letter is the first one, and the largest letter is the second one.

S. Kitaev, Introduction to partially ordered patterns, Discrete Applied Mathematics 155 (2007), 929-944.
S. Kitaev, Introduction to partially ordered patterns.

Cf. A117156, A177470, A177471, A177472, A177473, A177476, A177477, A177478, A177479, A177480, A177481, A177482, A177483, A177484, A376694.

Edited and terms a(0),a(10)-a(24) added by Max Alekseyev, Oct 02 2024

A177476 Number of partitions of order n avoiding the consecutive pattern 231'1.

Original entry on oeis.org

1, 1, 2, 6, 20, 83, 402, 2245, 14192, 100650, 792508, 6859260, 64772648, 662630653, 7301841444, 86212535179, 1085834949064, 14530898302390, 205897508769218, 3079580500287978, 48485072137150344, 801518797091165406, 13881049047327393608, 251325130816997882224, 4748240560493406374592

Offset: 0

Signy Olafsdottir (signy06(AT)ru.is), May 09 2010

nonn

To avoid 231'1 means not to have four consecutive letters such that if the third letter is removed, then in the obtained 3 letter word the smallest letter is the last one, and the largest letter is the second one.

S. Kitaev, Introduction to partially ordered patterns, Discrete Applied Mathematics 155 (2007), 929-944.

Cf. A117156, A177470, A177471, A177472, A177473, A177475, A177477, A177478, A177479, A177480, A177481, A177482, A177483, A177484, A376694.

ok[{x_, y_, , z}] := Not[x>z && y>z && y>x]; a[n_] := Length@ Select[ Permutations@ Range@ n, AllTrue[ Partition[#, 4, 1], ok] &]; a /@ Range[0, 9]

a(0), a(10)-a(14) from Alois P. Heinz, Mar 10 2020
a(15)-a(16) from Giovanni Resta, Mar 11 2020
a(17)-a(24) from Max Alekseyev, Oct 02 2024

A177480 Number of permutations of order n avoiding the consecutive pattern egfh with e

Original entry on oeis.org

1, 1, 2, 6, 20, 84, 412, 2300, 14676, 104536, 825660, 7168860, 67826340, 695174208, 7671602644, 90700227700, 1143825611348, 15325929083336, 217429459642252, 3256039887793868, 51325896829151684, 849518895902379696, 14730333827970237220, 267028337196612514596, 5051094767395355339476

Offset: 0

Signy Olafsdottir (signy06(AT)ru.is), May 09 2010

nonn

To avoid egfh means not to have four consecutive letters such that the first and the second letters are less than the third and the fourth letters.

S. Kitaev, Introduction to partially ordered patterns, Discrete Applied Mathematics 155 (2007), 929-944.

Cf. A117156, A177470, A177471, A177472, A177473, A177475, A177476, A177477, A177478, A177479, A177481, A177482, A177483, A177484, A376694.

ok[{e_, f_, g_, h_}] := e > g || e > h || f > g || f > h; a[n_] := Length@ Select[ Permutations[Range@n], AllTrue[ Partition[#, 4, 1], ok] &]; a /@ Range[0, 9] (* Giovanni Resta, Mar 11 2020 *)

a(0), a(10)-a(14) from Alois P. Heinz, Mar 10 2020
a(15)-a(16) from Giovanni Resta, Mar 11 2020
Edited and a(17)-a(24) added by Max Alekseyev, Oct 01 2024

A177481 Number of permutations of order n avoiding the consecutive pattern efgh with e

Original entry on oeis.org

1, 1, 2, 6, 20, 80, 404, 2368, 15488, 114480, 948992, 8625672, 85223792, 913869056, 10567326528, 130796711016, 1726077013456, 24213357455936, 359694651093152, 5638959807231240, 93052021458248400, 1612444736747193696, 29271726199933801536, 555518182602741687432, 11001032351303890637648

Offset: 0

Signy Olafsdottir (signy06(AT)ru.is), May 09 2010

nonn

To avoid efgh means not to have four consecutive letters such that the first and the third letters are less than the second and the fourth letters.

S. Kitaev, Introduction to partially ordered patterns, Discrete Applied Mathematics 155 (2007), 929-944.

Cf. A117156, A177470, A177471, A177472, A177473, A177475, A177476, A177477, A177478, A177479, A177480, A177482, A177483, A177484, A376694.

ok[{e_,f_,g_,h_}] := e>f || e>h || g>f || g>h; a[n_] := Length@ Select[ Permutations[ Range@ n], AllTrue[ Partition[#, 4, 1], ok] &]; Array[a, 9, 0] (* Giovanni Resta, Mar 11 2020 *)

a(0), a(10)-a(16) from Giovanni Resta, Mar 11 2020

Edited and a(17)-a(24) added by Max Alekseyev, Oct 01 2024

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

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

A177470 Number of permutations of order n avoiding the consecutive pattern 11'22'.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

C

Extensions

A376694 Number of permutations of order n avoiding consecutive pattern 121'3.

Views

Author

Keywords

Comments

Links

Crossrefs

A177472 Number of permutations of order n avoiding the consecutive pattern 11'2'2.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A177473 Number of permutations of order n avoiding the consecutive pattern 12'1'2.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A177475 Number of permutations of order n avoiding the consecutive pattern 131'2.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A177476 Number of partitions of order n avoiding the consecutive pattern 231'1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A177480 Number of permutations of order n avoiding the consecutive pattern egfh with e

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A177481 Number of permutations of order n avoiding the consecutive pattern efgh with e

Views

Author

Keywords

Comments

Links

Crossrefs

Programs