login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A335518 Number of matching pairs of patterns, the first of length n and the second of length k. 1
1, 1, 1, 3, 3, 3, 13, 13, 25, 13, 75, 75, 185, 213, 75, 541, 541, 1471, 2719, 2053, 541, 4683, 4683, 13265, 32973, 40367, 22313, 4683, 47293, 47293, 136711, 408265, 713277, 625295, 271609, 47293 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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

LINKS

Table of n, a(n) for n=0..35.

Wikipedia, Permutation pattern

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

EXAMPLE

Triangle begins:

     1

     1     1

     3     3     3

    13    13    25    13

    75    75   185   213    75

   541   541  1471  2719  2053   541

  4683  4683 13265 32973 40367 22313  4683

Row n =2 counts the following pairs:

  ()<=(1,1)  (1)<=(1,1)  (1,1)<=(1,1)

  ()<=(1,2)  (1)<=(1,2)  (1,2)<=(1,2)

  ()<=(2,1)  (1)<=(2,1)  (2,1)<=(2,1)

MATHEMATICA

mstype[q_]:=q/.Table[Union[q][[i]]->i, {i, Length[Union[q]]}];

allnorm[n_]:=If[n<=0, {{}}, Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1]];

Table[Sum[Length[Union[mstype/@Subsets[y, {k}]]], {y, Join@@Permutations/@allnorm[n]}], {n, 0, 5}, {k, 0, n}]

CROSSREFS

Columns k = 0 and k = 1 are both A000670.

Row sums are A335517.

Patterns are ranked by A333217.

Patterns matched by a standard composition are counted by A335454.

Patterns contiguously matched by compositions are counted by A335457.

Minimal patterns avoided by a standard composition are counted by A335465.

Patterns matched by prime indices are counted by A335549.

Cf. A011782, A034691, A056986, A124771, A269134, A329744, A333257, A334299.

Sequence in context: A291407 A147823 A341211 * A269347 A183554 A229847

Adjacent sequences:  A335515 A335516 A335517 * A335519 A335520 A335521

KEYWORD

nonn,tabl,more

AUTHOR

Gus Wiseman, Jun 23 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 28 00:29 EST 2022. Contains 350654 sequences. (Running on oeis4.)