cp's OEIS Frontend

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.

%I A371822 #58 Jul 10 2024 15:04:37
%S A371822 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,
%T A371822 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,
%U A371822 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
%N 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.
%C A371822 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.
%C A371822 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.
%C A371822 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.
%C A371822 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.
%H A371822 Wikipedia, <a href="https://en.wikipedia.org/wiki/Superpattern">Superpattern</a>.
%e A371822 The first 10 rows:
%e A371822   1
%e A371822   1,  2
%e A371822   3,  1,  2
%e A371822   3,  1,  4,  2
%e A371822   2,  5,  3,  1,  4
%e A371822   2,  5,  3,  6,  1,  4
%e A371822   3,  6,  1,  4,  7,  2,  5
%e A371822   2,  5,  8,  3,  6,  1,  4,  7
%e A371822   6,  1,  9,  4,  7,  2,  5,  8,  3
%e A371822   7,  2, 10,  5,  8,  3,  6,  1,  9,  4
%Y A371822 A371823 lists the number of different patterns of length k in row n.
%Y A371822 Cf. A194832 (same rows cyclically shifted?).
%Y A371822 Cf. A342474, A373778.
%K A371822 nonn,tabl
%O A371822 1,3
%A A371822 _Thomas Scheuerle_, Jun 22 2024
%E A371822 Edited by _Peter Munn_, Jul 09 2024