A349976 Triangle read by rows, number of subsets S of [n] with |distset(S)| = k. T(n, k) for 0 <= k <= n.

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 2, 3, 1, 5, 10, 4, 8, 4, 1, 6, 15, 6, 17, 10, 9, 1, 7, 21, 9, 31, 17, 25, 17, 1, 8, 28, 12, 51, 27, 47, 49, 33, 1, 9, 36, 16, 77, 43, 77, 97, 93, 63, 1, 10, 45, 20, 112, 62, 113, 169, 177, 187, 128

Offset: 0

Author

Peter Luschny, Dec 09 2021

Keywords

• nonn
• tabl
• hard

Comments

We use the notation [n] = {0, 1, ..., n-1}. If S is a subset of [n] then we define the distset of S (set of distances of S) as {|x - y|: x, y in S}.

For instance a subset S of [n] is a complete ruler (A103295) of length n - 1 if and only if distset(S) = [n].

Examples

			Triangle starts:
[n\k]  0, 1,  2,  3,  4,  5,  6,  7,  8,  9
-------------------------------------------
[ 0 ]  1;
[ 1 ]  1, 1;
[ 2 ]  1, 2,  1;
[ 3 ]  1, 3,  3,  1;
[ 4 ]  1, 4,  6,  2,  3;
[ 5 ]  1, 5, 10,  4,  8,  4;
[ 6 ]  1, 6, 15,  6, 17, 10,  9;
[ 7 ]  1, 7, 21,  9, 31, 17, 25, 17;
[ 8 ]  1, 8, 28, 12, 51, 27, 47, 49, 33;
[ 9 ]  1, 9, 36, 16, 77, 43, 77, 97, 93, 63;
.
Let S = {0, 3, 6, 7, 8}. Then S is a subset of [9] and distset(S) = [9].
For n = 7 the 9 subsets S with |distset(S)| = 3 are: {1, 2, 3}, {1, 3, 5}, {1, 4, 7}, {2, 3, 4}, {2, 4, 6}, {3, 4, 5}, {3, 5, 7}, {4, 5, 6}, {5, 6, 7}.
		

Links

• Fausto A. C. Cariboni, Rows n = 0..47, flattened (rows n = 0..36 from Peter Luschny)
• Scott Harvey-Arnold, Steven J. Miller, and Fei Peng, Distribution of missing differences in diffsets, arXiv:2001.08931 [math.CO], 2020. Also in: Combinatorial and Additive Number Theory IV, Springer 2021. [Table 2 and Table 3, page 276 and 277 in the book.]
• Peter Luschny, The first 37 rows, formatted as a triangular array.
• Index entries for sequences related to perfect rulers.

Crossrefs

Columns: A000012, A000027, A000217, A002620, A349975.

Cf. A000079 (row sums), A103295 (main diagonal), A349972 (subdiagonal).

Cf A349973, A349974, A350103.

Programs

Mathematica

distSetSize[s_] := Length @ Union[Map[Abs[Differences[#][[1]]] &, Union[Sort /@ Tuples[s, 2]]]]; T[n_, k_] := Count[Subsets[Range[0, n - 1]], ?(distSetSize[#] == k &)]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* _Amiram Eldar, Dec 12 2021 *)

SageMath

from collections import Counter
def DistsetLength(R) :
    S, L = Set([]), len(R)
    for r in R:
        for s in R:
            S = S.union(Set([abs(r - s)]))
    return len(S)
def A349976row(n):
    C = Counter(DistsetLength(s) for s in Subsets(n))
    return [C[k] for k in (0..n)]
for n in (0..9): print(A349976row(n))