login
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

%I #19 Jul 19 2024 22:34:41

%S 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,

%T 24,85,126,49,8,1,2,6,24,100,222,196,64,9,1,2,6,24,115,390,511,288,81,

%U 10,1,2,6,24,120,558,1085,912,405,100,11,1,2,6,24,120,654,1911,2328,1458,550,121,12

%N 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.

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

%C 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.

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

%e The triangle begins:

%e n| k: 1| 2| 3| 4| 5| 6| 7| 8| 9

%e =========================================

%e [1] 1

%e [2] 1, 2

%e [3] 1, 2, 3

%e [4] 1, 2, 6, 4

%e [5] 1, 2, 6, 16, 5

%e [6] 1, 2, 6, 20, 25, 6

%e [7] 1, 2, 6, 24, 60, 36, 7

%e [8] 1, 2, 6, 24, 85, 126, 49, 8

%e [9] 1, 2, 6, 24, 100, 222, 196, 64, 9

%e .

%e Row 5 of A194832 is [3, 1, 4, 2, 5].

%e T(5, 4) = 16 because we will find these 16 distinct patterns of length 4:

%e [3, 1, 4, 2] [1, 4, 2, 3] [4, 2, 3, 1] [2, 3, 1, 4]

%e These are rotations of the ordering [1, 4, 2, 3].

%e [1, 4, 2, 5] [4, 2, 5, 1] [2, 5, 1, 4] [5, 1, 4, 2]

%e These are rotations of the ordering [1, 3, 2, 4].

%e [2, 5, 3, 1] [5, 3, 1, 2] [3, 1, 2, 5] [1, 2, 5, 3]

%e These are rotations of the ordering [1, 2, 4, 3].

%e [5, 3, 1, 4] [3, 1, 4, 5] [1, 4, 5, 3] [4, 5, 3, 1]

%e These are rotations of the ordering [1, 3, 4, 2].

%Y Cf. A194832, A371823, A373778.

%K nonn,tabl

%O 1,3

%A _Thomas Scheuerle_, Jul 08 2024