A381476 Triangle read by rows: T(n,k) is the number of subsets of {1..n} with k elements such that every pair of distinct elements has a different difference, 0 <= k <= A143824(n).

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 4, 6, 2, 1, 5, 10, 6, 1, 6, 15, 14, 1, 7, 21, 26, 2, 1, 8, 28, 44, 10, 1, 9, 36, 68, 26, 1, 10, 45, 100, 60, 1, 11, 55, 140, 110, 1, 12, 66, 190, 190, 4, 1, 13, 78, 250, 304, 22, 1, 14, 91, 322, 466, 68, 1, 15, 105, 406, 676, 156

Offset

0,5

Comments

Equivalently, a(n) is the number of Sidon sets of {1..n} of size k.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..464 (rows 0..60)

Wikipedia, Sidon sequence.

Index entries for sequences related to Golomb rulers.

Formula

T(n,A143824(n)) = A382395(n).

Example

Triangle begins:
   0 | 1;
   1 | 1,  1;
   2 | 1,  2,  1;
   3 | 1,  3,  3;
   4 | 1,  4,  6,   2;
   5 | 1,  5, 10,   6;
   6 | 1,  6, 15,  14;
   7 | 1,  7, 21,  26,   2;
   8 | 1,  8, 28,  44,  10;
   9 | 1,  9, 36,  68,  26;
  10 | 1, 10, 45, 100,  60;
  11 | 1, 11, 55, 140, 110;
  12 | 1, 12, 66, 190, 190, 4;
  ...

Prog

(PARI)
row(n)={
  local(L=List());
  my(recurse(k, r, b, w)=
      if(k > n, if(r>=#L, listput(L, 0)); L[1+r]++,
         self()(k+1, r, b, w);
         b+=1<<k; if(!bitand(w, b<<k), self()(k+1, r+1, b, w + (b<<k)));
        );
  );
  recurse(1, 0, 0, 0);
  Vec(L)
}

Crossrefs

Columns 0..5 are A000012, A001477, A161680, A212964(n-1), A241688, A241689, A241690.

Row sums are A143823.

Cf. A003022, A143824, A325879, A382395.

Sequence in context: A124054 A299208 A334187 * A082870 A026009 A137171

Adjacent sequences: A381473 A381474 A381475 * A381477 A381478 A381479

Keyword

nonn,tabf

Author

Andrew Howroyd, Mar 27 2025

Status

approved