login
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.
2
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,2
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).
LINKS
M. K. Goh and R. Y. Zhao, Arithmetic subsequences in a random ordering of an additive set, arXiv:2012.12339 [math.CO], 2020.
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.
EXAMPLE
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.
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 *)
PROG
(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
CROSSREFS
Cf. A008279.
Sequence in context: A297890 A083506 A248164 * A210222 A207621 A209157
KEYWORD
nonn,tabl
AUTHOR
Marcel K. Goh, Nov 17 2020
STATUS
approved