A300760 -id:A300760 - cp's OEIS frontend

A334187 Number T(n,k) of k-element subsets of [n] avoiding 3-term arithmetic progressions; triangle T(n,k), n>=0, 0<=k<=A003002(n), read by rows.

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 4, 6, 2, 1, 5, 10, 6, 1, 1, 6, 15, 14, 4, 1, 7, 21, 26, 10, 1, 8, 28, 44, 25, 1, 9, 36, 68, 51, 4, 1, 10, 45, 100, 98, 24, 1, 11, 55, 140, 165, 64, 7, 1, 12, 66, 190, 267, 144, 25, 1, 13, 78, 250, 407, 284, 78, 6, 1, 14, 91, 322, 601, 520, 188, 22, 1

Offset: 0

Alois P. Heinz, May 14 2020

T(n,k) is defined for all n >= 0 and k >= 0. The triangle contains only elements with 0 <= k <= A003002(n). T(n,k) = 0 for k > A003002(n).

			Triangle T(n,k) begins:
  1;
  1,  1;
  1,  2,   1;
  1,  3,   3;
  1,  4,   6,   2;
  1,  5,  10,   6,    1;
  1,  6,  15,  14,    4;
  1,  7,  21,  26,   10;
  1,  8,  28,  44,   25;
  1,  9,  36,  68,   51,    4;
  1, 10,  45, 100,   98,   24;
  1, 11,  55, 140,  165,   64,   7;
  1, 12,  66, 190,  267,  144,  25;
  1, 13,  78, 250,  407,  284,  78,   6;
  1, 14,  91, 322,  601,  520, 188,  22,  1;
  1, 15, 105, 406,  849,  862, 386,  64,  4;
  1, 16, 120, 504, 1175, 1394, 763, 164, 14;
  ...

Fausto A. C. Cariboni, Rows n = 0..70, flattened (rows n = 0..40 from Alois P. Heinz)
Eric Weisstein's World of Mathematics, Nonaveraging Sequence
Wikipedia, Arithmetic progression
Wikipedia, Salem-Spencer set
Index entries related to non-averaging sequences

Columns k=0-4 give: A000012, A000027, A000217(n-1), A212964(n-1), A300760.
Row sums give A051013.
Last elements of rows give A262347.
Cf. A003002, A334892.

b:= proc(n, s) option remember; `if`(n=0, 1, b(n-1, s)+ `if`(
      ormap(j-> 2*j-n in s, s), 0, expand(x*b(n-1, s union {n}))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, {})):
seq(T(n), n=0..16);

b[n_, s_] := b[n, s] = If[n == 0, 1, b[n-1, s] + If[AnyTrue[s, MemberQ[s, 2 # - n]&], 0, Expand[x b[n-1, s ~Union~ {n}]]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, {}]];
T /@ Range[0, 16] // Flatten (* Jean-François Alcover, May 30 2020, after Maple *)

T(n,k) = Sum_{j=0..n} A334892(j,k).

T(n,A003002(n)) = A262347(n).

A300761 Number of non-equivalent ways (mod D_2) to select 4 points from n equidistant points on a straight line so that no selected point is equally distant from two other selected points.

Original entry on oeis.org

0, 1, 3, 6, 15, 28, 53, 87, 140, 210, 310, 434, 600, 803, 1061, 1368, 1747, 2190, 2723, 3337, 4060, 4884, 5840, 6916, 8148, 9525, 11083, 12810, 14747, 16880, 19253, 21851, 24720, 27846, 31278, 34998, 39060, 43447, 48213, 53340, 58887, 64834, 71243, 78093, 85448

Offset: 4

Heinrich Ludwig, Mar 15 2018

The condition of the selection is also known as "no 3-term arithmetic progressions".

A reflection of a selection is not counted. If reflections are to be counted see A300760.

Heinrich Ludwig, Table of n, a(n) for n = 4..1000

Cf. A002623, A300760.

a(n) = (n^4 - 12*n^3 + 54*n^2 - 88*n)/48 + (n == 1 (mod 2))*(-4*n + 19)/16 + (n == 5 (mod 6))/3 + (n == 2 (mod 6))/3 + (n == 2 (mod 4))/2.
a(n) = (n^4 - 12*n^3 + 54*n^2 - 88*n)/48 + b(n) + c(n), where
  b(n) = 0              for n even
  b(n) = (-4*n + 19)/16 for n odd
  c(n) = 0              for n == 0,1,3,4,7,9 (mod 12)
  c(n) = 1/3            for n == 5,8,11      (mod 12)
  c(n) = 1/2            for n == 6,10        (mod 12)
  c(n) = 5/6            for n == 2           (mod 12).
From Colin Barker, Mar 15 2018: (Start)
G.f.: x^5*(1 + x + 4*x^3 + x^4 + 5*x^5) / ((1 - x)^5*(1 + x)^2*(1 + x^2)*(1 + x + x^2)).
a(n) = 2*a(n-1) - a(n-3) - 2*a(n-5) + 2*a(n-6) + a(n-8) - 2*a(n-10) + a(n-11) for n>14.
(End)

cp's OEIS Frontend

A334187 Number T(n,k) of k-element subsets of [n] avoiding 3-term arithmetic progressions; triangle T(n,k), n>=0, 0<=k<=A003002(n), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula