OFFSET
0,9
COMMENTS
If n=k then T(n,k)=1.
A sparse ruler, or simply a ruler, is a strict increasing finite sequence of nonnegative integers starting from 0 called marks.
A segment of a ruler is the space between two adjacent marks. The number of segments is the number of marks - 1.
A ruler is complete if the set of all distances it can measure is {1,2,3,...,k} for some integer k>=1.
A ruler is perfect if it is complete and no complete ruler with the same length possesses less marks.
A ruler is optimal if it is perfect and no perfect ruler with the same number of segments has a greater length.
The 'empty ruler' with length n=0 is considered perfect and optimal.
REFERENCES
G. S. Bloom and S. W. Golomb, Numbered complete graphs, unusual rulers, and assorted applications. Theory and Applications of Graphs, Lecture Notes in Math. 642, (1978), 53-65.
R. K. Guy, Modular difference sets and error correcting codes. in: Unsolved Problems in Number Theory, 3rd ed. New York: Springer-Verlag, chapter C10, pp. 181-183, 2004.
J. C. P. Miller, Difference bases: Three problems in additive number theory, pp. 299-322 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.
LINKS
Fausto A. C. Cariboni, Rows n = 0..49, flattened (rows n = 0..39 from Hugo Pfoertner)
G. S. Bloom and S. W. Golomb, Applications of numbered undirected graphs, Proc. IEEE 65 (1977), 562-570.
Peter Luschny, Perfect and Optimal Rulers
Peter Luschny, Table of Counts
Peter Luschny, Perfect rulers
Eric Weisstein's World of Mathematics, Perfect Rulers
B. Wichmann, A note on restricted difference bases, J. Lond. Math. Soc. 38 (1963), 465-466.
EXAMPLE
Rows begin:
[1],
[0,1],
[0,0,1],
[0,0,2,1],
[0,0,0,3,1],
[0,0,0,4,4,1],
[0,0,0,2,9,5,1],
[0,0,0,0,12,14,6,1],
[0,0,0,0,8,27,20,7,1],
...
a(19)=T(5,4)=4 counts the complete rulers with length 5 and 4 segments: {[0,2,3,4,5],[0,1,3,4,5],[0,1,2,4,5],[0,1,2,3,5]}
MATHEMATICA
marks[n_, k_] := Module[{i}, i[0] = 0; iter = Sequence @@ Table[{i[j], i[j - 1] + 1, n - k + j - 1}, {j, 1, k}]; Table[Join[{0}, Array[i, k], {n}],
iter // Evaluate] // Flatten[#, k - 1]&];
completeQ[ruler_List] := Range[ruler[[-1]]] == Sort[ Union[ Flatten[ Table[ ruler[[i]] - ruler[[j]], {i, 1, Length[ruler]}, {j, 1, i - 1}]]]];
rulers[n_, k_] := Select[marks[n, k - 1], completeQ];
T[n_, n_] = 1; T[_, 0] = 0; T[n_, k_] := Length[rulers[n, k]];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Quiet (* Jean-François Alcover, Jul 05 2019 *)
PROG
(Sage)
def isComplete(R) :
S = Set([])
L = len(R)-1
for i in range(L, 0, -1) :
for j in (1..i) :
S = S.union(Set([R[i]-R[i-j]]))
return len(S) == R[L]
def Partsum(T) :
return [add([T[j] for j in range(i)]) for i in (0..len(T))]
def Ruler(L, S) :
return map(Partsum, Compositions(L, length=S))
def CompleteRuler(L, S) :
return tuple(filter(isComplete, Ruler(L, S)))
for n in (0..8):
print([len(CompleteRuler(n, k)) for k in (0..n)]) # Peter Luschny, Jul 05 2019
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Feb 28 2005
EXTENSIONS
Typo in data corrected by Jean-François Alcover, Jul 05 2019
STATUS
approved