cp's OEIS Frontend

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.

%I A338993 #37 Sep 08 2021 06:34:22
%S A338993 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 A338993 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 A338993 50,30,20,14,10,8,6,4,2,12,132,60,36,24,18,12,10,8,6,4,2
%N 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.
%C A338993 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 A338993 Proof can be found in Lemma 1 of Goh and Zhao (2020).
%H A338993 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 A338993 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 A338993 T(n,k) = 2*n*f - (k-1)*(f^2 + f), where f = floor((n-1)/(k-1)), for 2 <= k <= n.
%e A338993 Triangle T(n,k) begins:
%e A338993   n/k  1   2   3   4   5   6   7   8   9  10  11  12 ...
%e A338993    1   1
%e A338993    2   2   2
%e A338993    3   3   6   2
%e A338993    4   4  12   4   2
%e A338993    5   5  20   8   4   2
%e A338993    6   6  30  12   6   4   2
%e A338993    7   7  42  18  10   6   4   2
%e A338993    8   8  56  24  14   8   6   4   2
%e A338993    9   9  72  32  18  12   8   6   4   2
%e A338993   10  10  90  40  24  16  10   8   6   4   2
%e A338993   11  11 111  50  30  20  14  10   8   6   4   2
%e A338993   12  12 132  60  36  24  18  12  10   8   6   4   2
%e A338993   ...
%e A338993 For n=4 and k=3 the T(4,3)=4 permutations are 123, 234, 321, and 432.
%t A338993 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 A338993 (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 A338993 Cf. A008279.
%K A338993 nonn,tabl
%O A338993 1,2
%A A338993 _Marcel K. Goh_, Nov 17 2020