A350103 Triangle read by rows. Number of self-measuring subsets of the initial segment of the natural numbers strictly below n and cardinality k. Number of subsets S of [n] with S = distset(S) and |S| = k.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 4, 2, 1, 1, 1, 1, 5, 2, 1, 1, 1, 1, 1, 6, 3, 2, 1, 1, 1, 1, 1, 7, 3, 2, 1, 1, 1, 1, 1, 1, 8, 4, 2, 2, 1, 1, 1, 1, 1, 1, 9, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 10, 5, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 11, 5, 3, 2, 2, 1, 1, 1, 1, 1, 1

Offset: 0

Author

Peter Luschny, Dec 14 2021

Keywords

• nonn
• tabl

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}. We call a subset S of the natural numbers self-measuring if and only if S = distset(S).

Examples

			Triangle starts:
[ 0] [1]
[ 1] [1, 1]
[ 2] [1, 1,  1]
[ 3] [1, 1,  2, 1]
[ 4] [1, 1,  3, 1, 1]
[ 5] [1, 1,  4, 2, 1, 1]
[ 6] [1, 1,  5, 2, 1, 1, 1]
[ 7] [1, 1,  6, 3, 2, 1, 1, 1]
[ 8] [1, 1,  7, 3, 2, 1, 1, 1, 1]
[ 9] [1, 1,  8, 4, 2, 2, 1, 1, 1, 1]
[10] [1, 1,  9, 4, 3, 2, 1, 1, 1, 1, 1]
[11] [1, 1, 10, 5, 3, 2, 2, 1, 1, 1, 1, 1]
[12] [1, 1, 11, 5, 3, 2, 2, 1, 1, 1, 1, 1, 1]
.
The first  column is 1,1,...  because {} = distset({}) and |{}| = 0.
The second column is 1,1,... because {0} = distset({0}) and |{0}| = 1.
The third  column is n-1  because {0, j} = distset({0, j}) and |{0, j}| = 2 for j = 1..n - 1.
The main diagonal is 1,1,... because [n] = distset([n]) and |[n]| = n (these are the complete rulers A103295).
		

Links

• Winston de Greef, Table of n, a(n) of the first 150 rows, flattened (n = 0..11324)
• Peter Luschny, Illustrating self-measuring subsets of {0, 1, 2, 3}.

Crossrefs

Cf. A350102 (row sums), A349976, A103295, A003988, A010766, A123706.

Programs

Maple

T := (n, k) -> ifelse(k < 2, 1, floor((n - 1) / (k - 1))):
seq(print(seq(T(n, k), k = 0..n)), n = 0..12);

Mathematica

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

PARI

T(n, k) = if(k<=1, 1, (n - 1) \ (k - 1)) \\ Winston de Greef, Jan 31 2024

SageMath

# generating and counting (slow)
def isSelfMeasuring(R):
    S, L = Set([]), len(R)
    R = Set([r - 1 for r in R])
    for i in range(L):
        for j in (0..i):
            S = S.union(Set([abs(R[i] - R[i - j])]))
    return R == S
def A349976row(n):
    counter = [0] * (n + 1)
    for S in Subsets(n):
        if isSelfMeasuring(S): counter[len(S)] += 1
    return counter
for n in range(10): print(A349976row(n))

Formula

T(n, k) = floor((n - 1) / (k - 1)) for k >= 2.

T(n, k) = 1 if k = 0 or k = 1 or n >= k >= floor((n + 1)/2).