A339941 Triangle read by rows: T(n,k) is the number of permutations of {1,...,n} whose longest embedded arithmetic progression has length k.

1, 0, 2, 0, 4, 2, 0, 10, 12, 2, 0, 20, 82, 16, 2, 0, 48, 516, 134, 20, 2, 0, 104, 3232, 1480, 198, 24, 2, 0, 282, 21984, 15702, 2048, 274, 28, 2, 0, 496, 168368, 162368, 28048, 3204, 362, 32, 2, 0, 1066, 1306404, 1902496, 374194, 39420, 4720, 462, 36, 2, 0, 2460, 11064306, 23226786, 4929828, 622140, 64020, 6644, 574, 40, 2

Offset: 1

Author

Marcel K. Goh, Dec 23 2020

Keywords

• nonn
• tabl

Comments

Asymptotics can be found in Goh and Zhao (2020). The column k=2 corresponds to the number of 3-free permutations of 1..n, for n>=2.

Examples

			Triangle T(n,k) begins:
  n/k 1    2         3         4        5       6      7     8    9 10 11 12
   1  1
   2  0    2
   3  0    4         2
   4  0   10        12         2
   5  0   20        82        16        2
   6  0   48       516       134       20       2
   7  0  104      3232      1480      198      24      2
   8  0  282     21984     15702     2048     274     28     2
   9  0  496    168368    162368    28048    3204    362    32    2
  10  0 1066   1306404   1902496   374194   39420   4720   462   36   2
  11  0 2460  11064306  23226786  4929828  622140  64020  6644  574  40  2
  12  0 6128 101355594 298314654 68584052 9719492 913440 98472 9024 698 44 2
		

Links

• M. K. Goh and R. Y. Zhao, Arithmetic subsequences in a random ordering of an additive set, arXiv:2012.12339 [math.CO], 2020.

Crossrefs

Cf. A003407 (column k=2), A338993, A339942.