A371822 Triangle read by rows. Row n is the lexicographically earliest permutation of [n] that can be obtained from row n-1 by inserting the element n and optional cyclic shifting to maximize the pattern density.

1, 1, 2, 3, 1, 2, 3, 1, 4, 2, 2, 5, 3, 1, 4, 2, 5, 3, 6, 1, 4, 3, 6, 1, 4, 7, 2, 5, 2, 5, 8, 3, 6, 1, 4, 7, 6, 1, 9, 4, 7, 2, 5, 8, 3, 7, 2, 10, 5, 8, 3, 6, 1, 9, 4, 7, 2, 10, 5, 8, 3, 11, 6, 1, 9, 4, 8, 3, 11, 6, 1, 9, 4, 12, 7, 2, 10, 5, 11, 6, 1, 9, 4, 12, 7, 2, 10, 5, 13, 8, 3, 11, 6, 1, 14, 9, 4, 12, 7, 2, 10, 5, 13, 8, 3

Offset: 1

Author

Thomas Scheuerle, Jun 22 2024

Keywords

• nonn
• tabl

Comments

The first 13 rows include shortest k-superpatterns for k up to 5. These k-superpatterns are also optimal superpatterns. Optimal means the overall pattern density including patterns of all length is maximal among all permutations of [n]. How many more shortest superpatterns will be given by this sequence? The next will be expected in row 17.

Row n is a k-superpattern if row n of A371823 starts with 1!, 2!, ..., k!. If n also coincides with A342474(k), then row n is a shortest possible k-superpattern.

At time of sequence publication, all known rows agree up to cyclic shift with rows from A194832. This could indicate that A194832 will at least almost optimize the pattern density for permutations on the circle.

The above observations are accompanied by strong statistical arguments: because (1+sqrt(5))/2 has the simplest continued fraction expansion of any irrational number it will optimize asymptotically the pattern density in the permutations induced by it.

Examples

			The first 10 rows:
  1
  1,  2
  3,  1,  2
  3,  1,  4,  2
  2,  5,  3,  1,  4
  2,  5,  3,  6,  1,  4
  3,  6,  1,  4,  7,  2,  5
  2,  5,  8,  3,  6,  1,  4,  7
  6,  1,  9,  4,  7,  2,  5,  8,  3
  7,  2, 10,  5,  8,  3,  6,  1,  9,  4
		

Links

• Wikipedia, Superpattern.

Crossrefs

A371823 lists the number of different patterns of length k in row n.

Cf. A194832 (same rows cyclically shifted?).

Cf. A342474, A373778.

Extensions

Edited by Peter Munn, Jul 09 2024