A335517 Number of matching pairs of patterns, the longest having length n.

1, 2, 9, 64, 623, 7866, 122967

Offset

0,2

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

Wikipedia, Permutation pattern

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

Example

The a(0) = 1 through a(2) = 9 pairs of patterns:
  ()<=()    ()<=(1)      ()<=(1,1)
           (1)<=(1)      ()<=(1,2)
                         ()<=(2,1)
                        (1)<=(1,1)
                        (1)<=(1,2)
                        (1)<=(2,1)
                      (1,1)<=(1,1)
                      (1,2)<=(1,2)
                      (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]]], {y, Join@@Permutations/@allnorm[n]}], {n, 0, 5}]

Crossrefs

Row sums of A335518.

Patterns are counted by A000670 and 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: A141209 A269770 A269649 * A128577 A052514 A274395

Adjacent sequences: A335514 A335515 A335516 * A335518 A335519 A335520

Keyword

nonn,more

Author

Gus Wiseman, Jun 23 2020

Status

approved