A338993 Triangle read by rows: T(n,k) is the number of k-permutations of {1,...,n} that form a nontrivial arithmetic progression, 1 <= k <= n.

1, 2, 2, 3, 6, 2, 4, 12, 4, 2, 5, 20, 8, 4, 2, 6, 30, 12, 6, 4, 2, 7, 42, 18, 10, 6, 4, 2, 8, 56, 24, 14, 8, 6, 4, 2, 9, 72, 32, 18, 12, 8, 6, 4, 2, 10, 90, 40, 24, 16, 10, 8, 6, 4, 2, 11, 110, 50, 30, 20, 14, 10, 8, 6, 4, 2, 12, 132, 60, 36, 24, 18, 12, 10, 8, 6, 4, 2

Offset: 1

Author

Marcel K. Goh, Nov 17 2020

Keywords

• nonn
• tabl

Comments

The step size ranges from 1 to floor((n-1)/(k-1)) and for each r, there are 2*(n-(k-1)*r) possible ways to form a progression.

Proof can be found in Lemma 1 of Goh and Zhao (2020).

Examples

			Triangle T(n,k) begins:
  n/k  1   2   3   4   5   6   7   8   9  10  11  12 ...
   1   1
   2   2   2
   3   3   6   2
   4   4  12   4   2
   5   5  20   8   4   2
   6   6  30  12   6   4   2
   7   7  42  18  10   6   4   2
   8   8  56  24  14   8   6   4   2
   9   9  72  32  18  12   8   6   4   2
  10  10  90  40  24  16  10   8   6   4   2
  11  11 111  50  30  20  14  10   8   6   4   2
  12  12 132  60  36  24  18  12  10   8   6   4   2
  ...
For n=4 and k=3 the T(4,3)=4 permutations are 123, 234, 321, and 432.
		

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. A008279.

Programs

Mathematica

T[n_,k_]:=If[k==1, n,Sum[2(n-(k-1)r),{r,Floor[(n-1)/(k-1)]}]]; Flatten[Table[T[n,k],{n,12},{k,n}]] (* Stefano Spezia, Nov 17 2020 *)

PARI

T(n,k) = if (k==1, n, sum(r=1, (n-1)\(k-1), 2*(n-(k-1)*r))); \\ Michel Marcus, Sep 08 2021

Formula

T(n,k) = n, if k=1; Sum_{r=1..floor((n-1)/(k-1))} 2*(n-(k-1)*r), if 2 <= k <= n.

T(n,k) = 2*n*f - (k-1)*(f^2 + f), where f = floor((n-1)/(k-1)), for 2 <= k <= n.