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

By Gus Wiseman

Jun 21 2020

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670. 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).

Columns:
1. comps = Number of compositions of n matching/avoiding the given pattern.
2. patt  = Number of patterns of length n matching/avoiding the given pattern.
3. prix  = Number of permutations of the prime indices (or factors) of n matching/avoiding the given pattern.
4. stc   = Numbers k such that the k-th composition in standard order (A066099) matches/avoids the given pattern.

                  comps:   patt:    prix:    stc:   
                  -------  -------  -------  -------
  match ():       A011782  A000670  A008480* A001477
  match (1):      A131577  A000670* A008480  A000027
  match (1,1):    A261982  A019472  A335487  A335488
  match (1,2):    A056823  A002051  A335447  A335485
  match (2,1):    A056823  A002051  A008480* A335486
  match (1,1,1):  A335455  A335508  A335510  A335512
  match (1,1,2):  A335470  A335509  A335446  A335476
  match (1,2,1):  A335470  A335509  A335446  A335466
  match (2,1,1):  A335470  A335509  A335446  A335478
  match (1,2,2):  A335472  A335509  A335453  A335475
  match (2,1,2):  A335472  A335509  A335453  A335468
  match (2,2,1):  A335472  A335509  A335453  A335477
  match (1,2,3):  A335514  A335515  A335520  A335479
  match (1,3,2):  A335514  A335515  A335520  A335480
  match (2,1,3):  A335514  A335515  A335520  A335481
  match (2,3,1):  A335514  A335515  A335520  A335482
  match (3,1,2):  A335514  A335515  A335520  A335483
  match (3,2,1):  A335514  A335515  A335520  A335484

  avoid ():       {0}      A000004  A000004  {}
  avoid (1):      A000007  A000007  A000007  {0}
  avoid (1,1):    A032020  A000142  A335489  A233564
  avoid (1,2):    A000041  A011782  A000012  A114994
  avoid (2,1):    A000041  A011782  A000012  A225620
  avoid (1,1,1):  A232432  A080599  A335511  A335513
  avoid (1,1,2):  A335471  A001710  A335449  A335522
  avoid (1,2,1):  A335471  A001710  A335449  A335467
  avoid (2,1,1):  A335471  A001710  A335449  A335523
  avoid (1,2,2):  A335473  A001710  A335450  A335525
  avoid (2,1,2):  A335473  A001710  A335450  A335469
  avoid (2,2,1):  A335473  A001710  A335450  A335524
  avoid (1,2,3):  A102726  A226316  A335521  dense
  avoid (1,3,2):  A102726  A226316  A335521  dense
  avoid (2,1,3):  A102726  A226316  A335521  dense
  avoid (2,3,1):  A102726  A226316  A335521  dense
  avoid (3,1,2):  A102726  A226316  A335521  dense
  avoid (3,2,1):  A102726  A226316  A335521  dense

Latest version: https://docs.google.com/document/d/e/2PACX-1vQiRtjvNcvMLAqzpp4R2HmiWiiFE3qLundk8xemwExxqIURDW4WPlsJ1S3VhB1X7kTVrvYkupa2ZXlW/pub