login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A103294 Triangle T, read by rows: T(n,k) = number of complete rulers with length n and k segments (n >= 0, k >= 0). 21
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, 0, 0, 0, 0, 4, 40, 48, 27, 8, 1, 0, 0, 0, 0, 0, 38, 90, 75, 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 (list; table; graph; refs; listen; history; text; internal format)
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

Table of n, a(n) for n=0..90.

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.

Index entries for sequences related to perfect rulers

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

Row sums give A103295.

Column sums give A103296.

The first nonzero entries in the rows give A103300.

The last nonzero entries in the columns give A103299.

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

Cf. A103295 through A103301, A004137, A212661.

Sequence in context: A064287 A196389 A128206 * A198379 A079680 A037855

Adjacent sequences:  A103291 A103292 A103293 * A103295 A103296 A103297

KEYWORD

nonn,tabl

AUTHOR

Peter Luschny, Feb 28 2005

EXTENSIONS

Typo in data corrected by Jean-François Alcover, Jul 05 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 1 03:31 EST 2020. Contains 338833 sequences. (Running on oeis4.)