A338993 - OEIS

%I #37 Sep 08 2021 06:34:22

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

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

%U 50,30,20,14,10,8,6,4,2,12,132,60,36,24,18,12,10,8,6,4,2

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

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

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

%H M. K. Goh and R. Y. Zhao, <a href="https://arxiv.org/abs/2012.12339">Arithmetic subsequences in a random ordering of an additive set</a>, arXiv:2012.12339 [math.CO], 2020.

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

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

%e Triangle T(n,k) begins:

%e   n/k  1   2   3   4   5   6   7   8   9  10  11  12 ...

%e    1   1

%e    2   2   2

%e    3   3   6   2

%e    4   4  12   4   2

%e    5   5  20   8   4   2

%e    6   6  30  12   6   4   2

%e    7   7  42  18  10   6   4   2

%e    8   8  56  24  14   8   6   4   2

%e    9   9  72  32  18  12   8   6   4   2

%e   10  10  90  40  24  16  10   8   6   4   2

%e   11  11 111  50  30  20  14  10   8   6   4   2

%e   12  12 132  60  36  24  18  12  10   8   6   4   2

%e   ...

%e For n=4 and k=3 the T(4,3)=4 permutations are 123, 234, 321, and 432.

%t 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 *)

%o (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

%Y Cf. A008279.

%K nonn,tabl

%O 1,2

%A _Marcel K. Goh_, Nov 17 2020