login
Triangle T, read by rows: T(n,k) = number of complete rulers with length n and k segments (n >= 0, k >= 0).
22

%I #44 Apr 22 2022 17:24:50

%S 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,

%T 14,6,1,0,0,0,0,8,27,20,7,1,0,0,0,0,4,40,48,27,8,1,0,0,0,0,0,38,90,75,

%U 35,9,1,0,0,0,0,0,30,134,166,110,44,10,1,0,0,0,0,0,14,166,311,277,154,54,11,1

%N Triangle T, read by rows: T(n,k) = number of complete rulers with length n and k segments (n >= 0, k >= 0).

%C If n=k then T(n,k)=1.

%C A sparse ruler, or simply a ruler, is a strict increasing finite sequence of nonnegative integers starting from 0 called marks.

%C A segment of a ruler is the space between two adjacent marks. The number of segments is the number of marks - 1.

%C A ruler is complete if the set of all distances it can measure is {1,2,3,...,k} for some integer k>=1.

%C A ruler is perfect if it is complete and no complete ruler with the same length possesses less marks.

%C A ruler is optimal if it is perfect and no perfect ruler with the same number of segments has a greater length.

%C The 'empty ruler' with length n=0 is considered perfect and optimal.

%D 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.

%D 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.

%D 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.

%H Fausto A. C. Cariboni, <a href="/A103294/b103294.txt">Rows n = 0..49, flattened</a> (rows n = 0..39 from Hugo Pfoertner)

%H G. S. Bloom and S. W. Golomb, <a href="https://doi.org/10.1109/PROC.1977.10517">Applications of numbered undirected graphs</a>, Proc. IEEE 65 (1977), 562-570.

%H Peter Luschny, <a href="http://www.luschny.de/math/rulers/prulers.html">Perfect and Optimal Rulers</a>

%H Peter Luschny, <a href="http://www.luschny.de/math/rulers/rulercnt.html">Table of Counts</a>

%H Peter Luschny, <a href="http://oeis.org/wiki/User:Peter_Luschny/PerfectRulers">Perfect rulers</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PerfectRuler.html">Perfect Rulers</a>

%H B. Wichmann, <a href="https://doi.org/10.1112/jlms/s1-38.1.465">A note on restricted difference bases</a>, J. Lond. Math. Soc. 38 (1963), 465-466.

%H <a href="/index/Per#perul">Index entries for sequences related to perfect rulers</a>

%e Rows begin:

%e [1],

%e [0,1],

%e [0,0,1],

%e [0,0,2,1],

%e [0,0,0,3,1],

%e [0,0,0,4,4,1],

%e [0,0,0,2,9,5,1],

%e [0,0,0,0,12,14,6,1],

%e [0,0,0,0,8,27,20,7,1],

%e ...

%e 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]}

%t 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}],

%t iter // Evaluate] // Flatten[#, k - 1]&];

%t completeQ[ruler_List] := Range[ruler[[-1]]] == Sort[ Union[ Flatten[ Table[ ruler[[i]] - ruler[[j]], {i, 1, Length[ruler]}, {j, 1, i - 1}]]]];

%t rulers[n_, k_] := Select[marks[n, k - 1], completeQ];

%t T[n_, n_] = 1; T[_, 0] = 0; T[n_, k_] := Length[rulers[n, k]];

%t Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Quiet (* _Jean-François Alcover_, Jul 05 2019 *)

%o (Sage)

%o def isComplete(R) :

%o S = Set([])

%o L = len(R)-1

%o for i in range(L,0,-1) :

%o for j in (1..i) :

%o S = S.union(Set([R[i]-R[i-j]]))

%o return len(S) == R[L]

%o def Partsum(T) :

%o return [add([T[j] for j in range(i)]) for i in (0..len(T))]

%o def Ruler(L, S) :

%o return map(Partsum, Compositions(L, length=S))

%o def CompleteRuler(L, S) :

%o return tuple(filter(isComplete, Ruler(L, S)))

%o for n in (0..8):

%o print([len(CompleteRuler(n,k)) for k in (0..n)]) # _Peter Luschny_, Jul 05 2019

%Y Row sums give A103295.

%Y Column sums give A103296.

%Y The first nonzero entries in the rows give A103300.

%Y The last nonzero entries in the columns give A103299.

%Y The row numbers of the last nonzero entries in the columns give A004137.

%Y Cf. A103295 through A103301, A004137, A212661.

%K nonn,tabl

%O 0,9

%A _Peter Luschny_, Feb 28 2005

%E Typo in data corrected by _Jean-François Alcover_, Jul 05 2019