A335520 -id:A335520 - cp's OEIS frontend

A335515 Number of patterns of length n matching the pattern (1,2,3).

0, 0, 0, 1, 19, 257, 3167, 38909, 498235, 6811453, 100623211, 1612937661, 28033056683, 526501880989, 10639153638795, 230269650097469, 5315570416909995, 130370239796988957, 3385531348514480651, 92801566389186549245, 2677687663571344712043, 81124824154544921317597

Offset: 0

Gus Wiseman, Jun 19 2020

nonn

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			The a(3) = 1 through a(4) = 19 patterns:
  (1,2,3)  (1,1,2,3)
           (1,2,1,3)
           (1,2,2,3)
           (1,2,3,1)
           (1,2,3,2)
           (1,2,3,3)
           (1,2,3,4)
           (1,2,4,3)
           (1,3,2,3)
           (1,3,2,4)
           (1,3,4,2)
           (1,4,2,3)
           (2,1,2,3)
           (2,1,3,4)
           (2,3,1,4)
           (2,3,4,1)
           (3,1,2,3)
           (3,1,2,4)
           (4,1,2,3)

Andrew Howroyd, Table of n, a(n) for n = 0..200
Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

The complement A226316 is the avoiding version.
Compositions matching this pattern are counted by A335514 and ranked by A335479.
Permutations of prime indices matching this pattern are counted by A335520.
Patterns are counted by A000670 and ranked by A333217.
Patterns matching the pattern (1,1) are counted by A019472.
Permutations matching (1,2,3) are counted by A056986.
Combinatory separations are counted by A269134.
Patterns matched by standard compositions are counted by A335454.
Minimal patterns avoided by a standard composition are counted by A335465.
Cf. A034691, A158005, A158009, A238279, A333218, A333379, A333942.

allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n],MatchQ[#,{_,x_,_,y_,_,z_,_}/;x

seq(n)=Vec( serlaplace(1/(2-exp(x + O(x*x^n)))) - 1/2 - 1/(1+sqrt(1-8*x+8*x^2 + O(x*x^n))), -(n+1)) \\ Andrew Howroyd, Jan 28 2024

a(n) = A000670(n) - A226316(n). - Andrew Howroyd, Jan 28 2024

a(9) onwards from Andrew Howroyd, Jan 28 2024

A335514 Number of (1,2,3)-matching compositions of n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 4, 14, 42, 114, 292, 714, 1686, 3871, 8696, 19178, 41667, 89386, 189739, 399144, 833290, 1728374, 3565148, 7319212, 14965880, 30496302, 61961380, 125577752, 253971555, 512716564, 1033496947, 2080572090, 4183940550, 8406047907, 16875834728

Offset: 0

Gus Wiseman, Jun 22 2020

nonn

			The a(6) = 1 through a(8) = 14 compositions:
  (1,2,3)  (1,2,4)    (1,2,5)
           (1,1,2,3)  (1,3,4)
           (1,2,1,3)  (1,1,2,4)
           (1,2,3,1)  (1,2,1,4)
                      (1,2,2,3)
                      (1,2,3,2)
                      (1,2,4,1)
                      (2,1,2,3)
                      (1,1,1,2,3)
                      (1,1,2,1,3)
                      (1,1,2,3,1)
                      (1,2,1,1,3)
                      (1,2,1,3,1)
                      (1,2,3,1,1)

Andrew Howroyd, Table of n, a(n) for n = 0..500
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

The version for permutations is A056986.
The avoiding version is A102726.
These compositions are ranked by A335479.
The version for patterns is A335515.
The version for prime indices is A335520.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Patterns matched by compositions are counted by A335456.
Cf. A011782, A032020, A106356, A226316, A269134, A333755, A335465, A335521.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],MatchQ[#,{_,x_,_,y_,_,z_,_}/;x

a(n > 0) = 2^(n - 1) - A102726(n).

Terms a(21) and beyond from Andrew Howroyd, Dec 31 2020

A226316 Expansion of g.f. 1/2 + 1/(1+sqrt(1-8x+8x^2)).

Original entry on oeis.org

1, 1, 3, 12, 56, 284, 1516, 8384, 47600, 275808, 1624352, 9694912, 58510912, 356467392, 2189331648, 13540880384, 84265071360, 527232146944, 3314742364672, 20930141861888, 132673039491072, 843959152564224, 5385800362473472, 34470606645280768, 221213787774230528, 1423139139514138624

Offset: 0

N. J. A. Sloane, Jun 09 2013

nonn

From Robert A. Proctor, Jul 18 2017: (Start)
a(n) is the number of words of length n on {1,2,...,r} with positive multiplicities as 1 <= r <= n avoiding the pattern 123. [This is easy to see from the next comment.]
a(n) is the number of 123-avoiding ordered set partitions of {1,2,...,n}. [This is Cor. 2.3 of the Chen-Dai-Zhou reference.] (End)

			From _Gus Wiseman_, Jun 25 2020: (Start)
The a(0) = 1 through a(3) = 12 words that are (1,2,3)-avoiding and cover an initial interval:
  ()  (1)  (1,1)  (1,1,1)
           (1,2)  (1,1,2)
           (2,1)  (1,2,1)
                  (1,2,2)
                  (1,3,2)
                  (2,1,1)
                  (2,1,2)
                  (2,1,3)
                  (2,2,1)
                  (2,3,1)
                  (3,1,2)
                  (3,2,1)
(End)

Vincenzo Librandi, Table of n, a(n) for n = 0..100
Daniel Birmajer, Juan B. Gil, David S. Kenepp, and Michael D. Weiner, Restricted generating trees for weak orderings, arXiv:2108.04302 [math.CO], 2021.
W. Y. C. Chen, A. Y. L. Dai and R. D. P. Zhou, Ordered Partitions Avoiding a Permutation of Length 3, arXiv preprint arXiv:1304.3187 [math.CO], 2013.
Anders Claesson, Giulio Cerbai, Dana C. Ernst, and Hannah Golab, Pattern-avoiding Cayley permutations via combinatorial species, arXiv:2407.19583 [math.CO], 2024.
Robert A. Proctor and Matthew J. Willis, Parabolic Catalan numbers count flagged Schur functions and their appearances as type A Demazure characters (key polynomials), arXiv preprint arXiv:1706.04649 [math.CO], 2017.
Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Cf. A220097.
Sequences covering an initial interval are counted by A000670.
(1,2,3)-matching permutations are counted by A056986.
(1,2,3)-avoiding permutations are counted by A000108.
(1,2,3)-matching compositions are counted by A335514.
(1,2,3)-avoiding compositions are counted by A102726.
(1,2,3)-matching patterns are counted by A335515.
(1,2,3)-avoiding patterns are counted by A226316 (this sequence).
(1,2,3)-matching permutations of prime indices are counted by A335520.
(1,2,3)-avoiding permutations of prime indices are counted by A335521.
(1,2,3)-matching compositions are ranked by A335479.
Cf. A158005, A158009, A333217, A335465.

a:= proc(n) option remember; `if`(n<4, [1$2, 3, 12][n+1],
      ((9*n-3)*a(n-1) -(16*n-20)*a(n-2) +(8*n-16)*a(n-3))/(n+1))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 18 2013

CoefficientList[Series[1/2 + 1 / (1 + Sqrt[1 - 8 x + 8 x^2]), {x, 0, 30}], x] (* Vincenzo Librandi, Jun 18 2013 *)
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n],!MatchQ[#,{_,x_,_,y_,_,z_,_}/;xGus Wiseman, Jun 25 2020 *)

a(n) ~ sqrt((sqrt(2)-1)/Pi)*2^(n-1/2)*(2+sqrt(2))^n/n^(3/2). - Vaclav Kotesovec, Jun 29 2013
Conjecture: (n+1)*a(n) +3*(-3*n+1)*a(n-1) +4*(4*n-5)*a(n-2) +8*(-n+2)*a(n-3)=0. - R. J. Mathar, Apr 02 2015
a(n) = A000670(n) - A335515(n). - Gus Wiseman, Jun 25 2020

A335479 Numbers k such that the k-th composition in standard order (A066099) matches the pattern (1,2,3).

Original entry on oeis.org

52, 104, 105, 108, 116, 180, 200, 208, 209, 210, 211, 212, 216, 217, 220, 232, 233, 236, 244, 308, 328, 360, 361, 364, 372, 400, 401, 404, 408, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425, 428, 432, 433, 434, 435, 436, 440, 441, 444, 456, 464, 465, 466

Offset: 1

Gus Wiseman, Jun 18 2020

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			The sequence of terms together with the corresponding compositions begins:
   52: (1,2,3)
  104: (1,2,4)
  105: (1,2,3,1)
  108: (1,2,1,3)
  116: (1,1,2,3)
  180: (2,1,2,3)
  200: (1,3,4)
  208: (1,2,5)
  209: (1,2,4,1)
  210: (1,2,3,2)
  211: (1,2,3,1,1)
  212: (1,2,2,3)
  216: (1,2,1,4)
  217: (1,2,1,3,1)
  220: (1,2,1,1,3)

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.
Gus Wiseman, Statistics, classes, and transformations of standard compositions

The version counting permutations is A056986.
Patterns matching this pattern are counted by A335515 (by length).
Permutations of prime indices matching this pattern are counted by A335520.
These compositions are counted by A335514 (by sum).
Constant patterns are counted by A000005 and ranked by A272919.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Combinatory separations are counted by A269134.
Patterns matched by standard compositions are counted by A335454.
Minimal patterns avoided by a standard composition are counted by A335465.
Other permutations:
- A335479 (1,2,3)
- A335480 (1,3,2)
- A335481 (2,1,3)
- A335482 (2,3,1)
- A335483 (3,1,2)
- A335484 (3,2,1)
Cf. A034691, A056986, A108917, A114994, A158005, A238279, A333224, A333257, A334968, A335456, A335458.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
Select[Range[0,100],MatchQ[stc[#],{_,x_,_,y_,_,z_,_}/;x

A335480 Numbers k such that the k-th composition in standard order (A066099) matches the pattern (1,3,2).

Original entry on oeis.org

50, 98, 101, 102, 114, 178, 194, 196, 197, 198, 202, 203, 205, 206, 210, 226, 229, 230, 242, 306, 324, 354, 357, 358, 370, 386, 388, 389, 390, 393, 394, 395, 396, 397, 398, 402, 404, 405, 406, 407, 410, 411, 413, 414, 418, 421, 422, 434, 450, 452, 453, 454

Offset: 1

Gus Wiseman, Jun 18 2020

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			The sequence of terms together with the corresponding compositions begins:
   50: (1,3,2)
   98: (1,4,2)
  101: (1,3,2,1)
  102: (1,3,1,2)
  114: (1,1,3,2)
  178: (2,1,3,2)
  194: (1,5,2)
  196: (1,4,3)
  197: (1,4,2,1)
  198: (1,4,1,2)
  202: (1,3,2,2)
  203: (1,3,2,1,1)
  205: (1,3,1,2,1)
  206: (1,3,1,1,2)
  210: (1,2,3,2)

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.
Gus Wiseman, Statistics, classes, and transformations of standard compositions

The version counting permutations is A056986.
Patterns matching this pattern are counted by A335515 (by length).
Permutations of prime indices matching this pattern are counted by A335520.
These compositions are counted by A335514 (by sum).
Constant patterns are counted by A000005 and ranked by A272919.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Permutations matching (1,3,2,4) are counted by A158009.
Combinatory separations are counted by A269134.
Patterns matched by standard compositions are counted by A335454.
Minimal patterns avoided by a standard composition are counted by A335465.
Other permutations:
- A335479 (1,2,3)
- A335480 (1,3,2)
- A335481 (2,1,3)
- A335482 (2,3,1)
- A335483 (3,1,2)
- A335484 (3,2,1)
Cf. A034691, A056986, A108917, A114994, A158005, A238279, A333224, A333257, A334968, A335456, A335458.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
Select[Range[0,100],MatchQ[stc[#],{_,x_,_,y_,_,z_,_}/;x

A335482 Numbers k such that the k-th composition in standard order (A066099) matches the pattern (2,3,1).

Original entry on oeis.org

41, 81, 83, 89, 105, 145, 161, 163, 165, 166, 167, 169, 177, 179, 185, 209, 211, 217, 233, 289, 290, 291, 297, 305, 321, 323, 325, 326, 327, 329, 331, 332, 333, 334, 335, 337, 339, 345, 353, 355, 357, 358, 359, 361, 369, 371, 377, 401, 417, 419, 421, 422, 423

Offset: 1

Gus Wiseman, Jun 18 2020

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			The sequence of terms together with the corresponding compositions begins:
   41: (2,3,1)
   81: (2,4,1)
   83: (2,3,1,1)
   89: (2,1,3,1)
  105: (1,2,3,1)
  145: (3,4,1)
  161: (2,5,1)
  163: (2,4,1,1)
  165: (2,3,2,1)
  166: (2,3,1,2)
  167: (2,3,1,1,1)
  169: (2,2,3,1)
  177: (2,1,4,1)
  179: (2,1,3,1,1)
  185: (2,1,1,3,1)

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.
Gus Wiseman, Statistics, classes, and transformations of standard compositions

The version counting permutations is A056986.
Patterns matching this pattern are counted by A335515 (by length).
Permutations of prime indices matching this pattern are counted by A335520.
These compositions are counted by A335514 (by sum).
Constant patterns are counted by A000005 and ranked by A272919.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Permutations matching (1,3,2,4) are counted by A158009.
Combinatory separations are counted by A269134.
Patterns matched by standard compositions are counted by A335454.
Minimal patterns avoided by a standard composition are counted by A335465.
Other permutations:
- A335479 (1,2,3)
- A335480 (1,3,2)
- A335481 (2,1,3)
- A335482 (2,3,1)
- A335483 (3,1,2)
- A335484 (3,2,1)
Cf. A034691, A056986, A108917, A114994, A158005, A238279, A333224, A333257, A334968, A335456, A335458.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
Select[Range[0,100],MatchQ[stc[#],{_,x_,_,y_,_,z_,_}/;z

A335483 Numbers k such that the k-th composition in standard order (A066099) matches the pattern (3,1,2).

Original entry on oeis.org

38, 70, 77, 78, 102, 134, 140, 141, 142, 150, 154, 155, 157, 158, 166, 198, 205, 206, 230, 262, 268, 269, 270, 276, 278, 281, 282, 283, 284, 285, 286, 294, 301, 302, 306, 308, 309, 310, 311, 314, 315, 317, 318, 326, 333, 334, 358, 390, 396, 397, 398, 406, 410

Offset: 1

Gus Wiseman, Jun 18 2020

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			The sequence of terms together with the corresponding compositions begins:
   38: (3,1,2)
   70: (4,1,2)
   77: (3,1,2,1)
   78: (3,1,1,2)
  102: (1,3,1,2)
  134: (5,1,2)
  140: (4,1,3)
  141: (4,1,2,1)
  142: (4,1,1,2)
  150: (3,2,1,2)
  154: (3,1,2,2)
  155: (3,1,2,1,1)
  157: (3,1,1,2,1)
  158: (3,1,1,1,2)
  166: (2,3,1,2)

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.
Gus Wiseman, Statistics, classes, and transformations of standard compositions

The version counting permutations is A056986.
Patterns matching this pattern are counted by A335515 (by length).
Permutations of prime indices matching this pattern are counted by A335520.
These compositions are counted by A335514 (by sum).
Constant patterns are counted by A000005 and ranked by A272919.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Permutations matching (1,3,2,4) are counted by A158009.
Combinatory separations are counted by A269134.
Patterns matched by standard compositions are counted by A335454.
Minimal patterns avoided by a standard composition are counted by A335465.
Other permutations:
- A335479 (1,2,3)
- A335480 (1,3,2)
- A335481 (2,1,3)
- A335482 (2,3,1)
- A335483 (3,1,2)
- A335484 (3,2,1)
Cf. A034691, A056986, A108917, A114994, A158005, A238279, A333224, A333257, A334968, A335456, A335458.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
Select[Range[0,100],MatchQ[stc[#],{_,x_,_,y_,_,z_,_}/;y

A335481 Numbers k such that the k-th composition in standard order (A066099) matches the pattern (2,1,3).

Original entry on oeis.org

44, 88, 89, 92, 108, 152, 172, 176, 177, 178, 179, 180, 184, 185, 188, 216, 217, 220, 236, 296, 300, 304, 305, 312, 332, 344, 345, 348, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 364, 368, 369, 370, 371, 372, 376, 377, 380, 408, 428, 432, 433, 434, 435

Offset: 1

Gus Wiseman, Jun 18 2020

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			The sequence of terms together with the corresponding compositions begins:
   44: (2,1,3)
   88: (2,1,4)
   89: (2,1,3,1)
   92: (2,1,1,3)
  108: (1,2,1,3)
  152: (3,1,4)
  172: (2,2,1,3)
  176: (2,1,5)
  177: (2,1,4,1)
  178: (2,1,3,2)
  179: (2,1,3,1,1)
  180: (2,1,2,3)
  184: (2,1,1,4)
  185: (2,1,1,3,1)
  188: (2,1,1,1,3)

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.
Gus Wiseman, Statistics, classes, and transformations of standard compositions

The version counting permutations is A056986.
Patterns matching this pattern are counted by A335515 (by length).
Permutations of prime indices matching this pattern are counted by A335520.
These compositions are counted by A335514 (by sum).
Constant patterns are counted by A000005 and ranked by A272919.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Permutations matching (1,3,2,4) are counted by A158009.
Combinatory separations are counted by A269134.
Patterns matched by standard compositions are counted by A335454.
Minimal patterns avoided by a standard composition are counted by A335465.
Other permutations:
- A335479 (1,2,3)
- A335480 (1,3,2)
- A335481 (2,1,3)
- A335482 (2,3,1)
- A335483 (3,1,2)
- A335484 (3,2,1)
Cf. A034691, A056986, A108917, A114994, A158005, A238279, A333224, A333257, A334968, A335456, A335458.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
Select[Range[0,100],MatchQ[stc[#],{_,x_,_,y_,_,z_,_}/;y

A335484 Numbers k such that the k-th composition in standard order (A066099) matches the pattern (3,2,1).

Original entry on oeis.org

37, 69, 75, 77, 101, 133, 137, 139, 141, 149, 150, 151, 155, 157, 165, 197, 203, 205, 229, 261, 265, 267, 269, 274, 275, 277, 278, 279, 281, 283, 285, 293, 297, 299, 300, 301, 302, 303, 309, 310, 311, 315, 317, 325, 331, 333, 357, 389, 393, 395, 397, 405, 406

Offset: 1

Gus Wiseman, Jun 18 2020

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			The sequence of terms together with the corresponding compositions begins:
   37: (3,2,1)
   69: (4,2,1)
   75: (3,2,1,1)
   77: (3,1,2,1)
  101: (1,3,2,1)
  133: (5,2,1)
  137: (4,3,1)
  139: (4,2,1,1)
  141: (4,1,2,1)
  149: (3,2,2,1)
  150: (3,2,1,2)
  151: (3,2,1,1,1)
  155: (3,1,2,1,1)
  157: (3,1,1,2,1)
  165: (2,3,2,1)

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.
Gus Wiseman, Statistics, classes, and transformations of standard compositions

The version counting permutations is A056986.
Patterns matching this pattern are counted by A335515 (by length).
Permutations of prime indices matching this pattern are counted by A335520.
These compositions are counted by A335514 (by sum).
Constant patterns are counted by A000005 and ranked by A272919.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Permutations matching (1,3,2,4) are counted by A158009.
Combinatory separations are counted by A269134.
Patterns matched by standard compositions are counted by A335454.
Minimal patterns avoided by a standard composition are counted by A335465.
Other permutations:
- A335479 (1,2,3)
- A335480 (1,3,2)
- A335481 (2,1,3)
- A335482 (2,3,1)
- A335483 (3,1,2)
- A335484 (3,2,1)
Cf. A034691, A056986, A108917, A114994, A158005, A238279, A333224, A333257, A334968, A335456, A335458.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
Select[Range[0,100],MatchQ[stc[#],{_,x_,_,y_,_,z_,_}/;z

A335521 Number of (1,2,3)-avoiding permutations of the prime indices of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 5, 1, 1, 2, 2, 2, 6, 1, 2, 2, 4, 1, 5, 1, 3, 3, 2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 9, 1, 2, 3, 1, 2, 5, 1, 3, 2, 5, 1, 10, 1, 2, 3, 3, 2, 5, 1, 5, 1, 2, 1, 9, 2, 2, 2

Offset: 1

Gus Wiseman, Jun 19 2020

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			The a(n) permutations for n = 1, 6, 12, 24, 30, 36, 60, 72, 120:
  ()  (12)  (112)  (1112)  (132)  (1122)  (1132)  (11122)  (11132)
      (21)  (121)  (1121)  (213)  (1212)  (1312)  (11212)  (11312)
            (211)  (1211)  (231)  (1221)  (1321)  (11221)  (11321)
                   (2111)  (312)  (2112)  (2113)  (12112)  (13112)
                           (321)  (2121)  (2131)  (12121)  (13121)
                                  (2211)  (2311)  (12211)  (13211)
                                          (3112)  (21112)  (21113)
                                          (3121)  (21121)  (21131)
                                          (3211)  (21211)  (21311)
                                                  (22111)  (23111)
                                                           (31112)
                                                           (31121)
                                                           (31211)
                                                           (32111)

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

These compositions are counted by A102726.
Patterns avoiding this pattern are counted by A226316.
The complement A335520 is the matching version.
Permutations of prime indices are counted by A008480.
Patterns are counted by A000670 and ranked by A333217.
Anti-run permutations of prime indices are counted by A335452.
Cf. A056239, A056986, A112798, A238279, A281188, A333221, A333755, A335456, A335460, A335462, A335463.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Length[Select[Permutations[primeMS[n]],!MatchQ[#,{_,x_,_,y_,_,z_,_}/;x

For n > 0, a(n) + A335520(n) = A008480(n).

cp's OEIS Frontend

A335515 Number of patterns of length n matching the pattern (1,2,3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A335514 Number of (1,2,3)-matching compositions of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A226316 Expansion of g.f. 1/2 + 1/(1+sqrt(1-8*x+8*x^2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A335479 Numbers k such that the k-th composition in standard order (A066099) matches the pattern (1,2,3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A335480 Numbers k such that the k-th composition in standard order (A066099) matches the pattern (1,3,2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A335482 Numbers k such that the k-th composition in standard order (A066099) matches the pattern (2,3,1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A335483 Numbers k such that the k-th composition in standard order (A066099) matches the pattern (3,1,2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A335481 Numbers k such that the k-th composition in standard order (A066099) matches the pattern (2,1,3).

Views

Author

A226316 Expansion of g.f. 1/2 + 1/(1+sqrt(1-8x+8x^2)).