login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; table; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=1..78.

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

Adjacent sequences:  A338990 A338991 A338992 * A338994 A338995 A338996

KEYWORD

nonn,tabl

AUTHOR

Marcel K. Goh, Nov 17 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 6 12:35 EDT 2022. Contains 357264 sequences. (Running on oeis4.)