login
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.
5
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,9
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).
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).
EXAMPLE
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).
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 *)
PROG
(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))
(PARI) T(n, k) = if(k<=1, 1, (n - 1) \ (k - 1)) \\ Winston de Greef, Jan 31 2024
CROSSREFS
Sequence in context: A349703 A178239 A260534 * A085476 A124944 A094392
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Dec 14 2021
STATUS
approved