A374411 Triangle T(n, k) read by rows: Maximum number of linear patterns of length k in a circular permutation of length n taken from row n in A194832.

1, 1, 2, 1, 2, 3, 1, 2, 6, 4, 1, 2, 6, 16, 5, 1, 2, 6, 20, 25, 6, 1, 2, 6, 24, 60, 36, 7, 1, 2, 6, 24, 85, 126, 49, 8, 1, 2, 6, 24, 100, 222, 196, 64, 9, 1, 2, 6, 24, 115, 390, 511, 288, 81, 10, 1, 2, 6, 24, 120, 558, 1085, 912, 405, 100, 11, 1, 2, 6, 24, 120, 654, 1911, 2328, 1458, 550, 121, 12

Offset: 1

Author

Thomas Scheuerle, Jul 08 2024

Keywords

• nonn
• tabl

Comments

Pattern counting considers only one revolution otherwise every sufficiently long circular permutation, with enough revolutions allowed, contains every pattern.

Each column k is divisible by k, because as we count linear patterns inside a circular permutation, we may obtain all circular shifts of the subset which represents a particular pattern.

Examples

			The triangle begins:
   n| k: 1| 2| 3|  4|   5|   6|   7|  8|  9
  =========================================
  [1]    1
  [2]    1, 2
  [3]    1, 2, 3
  [4]    1, 2, 6,  4
  [5]    1, 2, 6, 16,   5
  [6]    1, 2, 6, 20,  25,   6
  [7]    1, 2, 6, 24,  60,  36,   7
  [8]    1, 2, 6, 24,  85, 126,  49,  8
  [9]    1, 2, 6, 24, 100, 222, 196, 64, 9
.
Row 5 of A194832 is [3, 1, 4, 2, 5].
T(5, 4) = 16 because we will find these 16 distinct patterns of length 4:
   [3, 1, 4, 2] [1, 4, 2, 3] [4, 2, 3, 1] [2, 3, 1, 4]
 These are rotations of the ordering [1, 4, 2, 3].
   [1, 4, 2, 5] [4, 2, 5, 1] [2, 5, 1, 4] [5, 1, 4, 2]
 These are rotations of the ordering [1, 3, 2, 4].
   [2, 5, 3, 1] [5, 3, 1, 2] [3, 1, 2, 5] [1, 2, 5, 3]
 These are rotations of the ordering [1, 2, 4, 3].
   [5, 3, 1, 4] [3, 1, 4, 5] [1, 4, 5, 3] [4, 5, 3, 1]
 These are rotations of the ordering [1, 3, 4, 2].
		

Crossrefs

Cf. A194832, A371823, A373778.

Formula

T(n, k+1)/(k+1) <= A371823(n-1, k) <= A373778(n-1, k).