A331330 a(n) is the number of sparse rulers of length n where the length of the first segment is unique.

0, 1, 1, 3, 4, 8, 14, 26, 46, 85, 155, 286, 528, 980, 1824, 3410, 6392, 12022, 22675, 42885, 81312, 154540, 294362, 561849, 1074463, 2058462, 3950220, 7592403, 14614105, 28168227, 54363000, 105043517, 203200635, 393496975, 762765642, 1479957400, 2874038529, 5585986973, 10865544853, 21150913457, 41201771886

Offset: 0

Author

Peter Luschny, Jan 24 2020

Keywords

• nonn

Comments

A sparse ruler, or simply a ruler, is a strict increasing finite sequence of nonnegative integers starting from 0 called marks. See A103294 for more definitions.

Also number of compositions of n where the first part is unique. - Christian Sievers, May 06 2025

Examples

			All rulers of length four are listed below; those marked with x are counted: [0,4]x, [0,3,4]x, [0,2,4], [0,1,4]x, [0,2,3,4]x, [0,1,3,4], [0,1,2,4], [0,1,2,3,4].
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..2000 (first 101 terms from Bert Dobbelaere)

Crossrefs

Cf. A331332, A103294.

Programs

Maple

b:= proc(n, i) option remember; `if`(n=0, 1, add(
     `if`(i=j, 0, b(n-j, `if`(nAlois P. Heinz, Feb 06 2020

Mathematica

b[n_, i_] := b[n, i] = If[n==0, 1, Sum[If[i==j, 0, b[n-j, If[nJean-François Alcover, Nov 15 2020, after Alois P. Heinz *)

PARI

\\ omits the initial 0
lista(n)=Vec(sum(k=1,n,(x^k+x*O(x^n))/(1-x/(1-x)+x^k))) \\ Christian Sievers, May 06 2025

Python

cache={}
def f( n, l1):
  args=(n, l1)
  if args in cache: return cache[args]
  s=0
  for l in range(1, n+1):
    if l!=l1:
      s += 1 if l==n else f(n-l, l1)
  cache[args] = s
  return s
def a331330(n):
  if n==0: return 0
  s=1
  for l1 in range(1, n+1):
    s += f( n-l1, l1)
  return s
# Bert Dobbelaere, Feb 06 2020

Formula

a(n) = A331332(n,1) for n >= 1.

Conjecture: a(n) ~ 2^n / (n * log(2)). - Vaclav Kotesovec, Nov 16 2020

G.f.: Sum_{k>=1} x^k/(1-x/(1-x)+x^k). - Christian Sievers, May 06 2025

Extensions

More terms from Bert Dobbelaere, Feb 06 2020