login
A349976
Triangle read by rows, number of subsets S of [n] with |distset(S)| = k. T(n, k) for 0 <= k <= n.
11
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,5
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].
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.]
EXAMPLE
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}.
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 *)
PROG
(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))
CROSSREFS
Cf. A000079 (row sums), A103295 (main diagonal), A349972 (subdiagonal).
Sequence in context: A208342 A157283 A067049 * A090641 A055216 A216236
KEYWORD
nonn,tabl,hard
AUTHOR
Peter Luschny, Dec 09 2021
STATUS
approved