A331330 - OEIS

%I #30 Nov 16 2020 02:37:54

%S 0,1,1,3,4,8,14,26,46,85,155,286,528,980,1824,3410,6392,12022,22675,

%T 42885,81312,154540,294362,561849,1074463,2058462,3950220,7592403,

%U 14614105,28168227,54363000,105043517,203200635,393496975,762765642,1479957400,2874038529,5585986973,10865544853,21150913457,41201771886

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

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

%H Alois P. Heinz, <a href="/A331330/b331330.txt">Table of n, a(n) for n = 0..2000</a> (first 101 terms from Bert Dobbelaere)

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

%F Conjecture: a(n) ~ 2^n / (n * log(2)). - _Vaclav Kotesovec_, Nov 16 2020

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

%p b:= proc(n, i) option remember; `if`(n=0, 1, add(

%p      `if`(i=j, 0, b(n-j, `if`(n<i+j, 0, i))), j=1..n))

%p     end:

%p a:= proc(n) option remember; add(b(n-j, j), j=1..n) end:

%p seq(a(n), n=0..50);  # _Alois P. Heinz_, Feb 06 2020

%t b[n_, i_] := b[n, i] = If[n==0, 1, Sum[If[i==j, 0, b[n-j, If[n<i+j, 0, i]]], {j, 1, n}]];

%t a[n_] := a[n] = Sum[b[n-j, j], {j, 1, n}];

%t a /@ Range[0, 50] (* _Jean-François Alcover_, Nov 15 2020, after _Alois P. Heinz_ *)

%o (Python)

%o cache={}

%o def f( n, l1):

%o ..args=(n, l1)

%o ..if args in cache: return cache[args]

%o ..s=0

%o ..for l in range(1, n+1):

%o ....if l!=l1:

%o ......s += 1 if l==n else f(n-l, l1)

%o ..cache[args] = s

%o ..return s

%o def a331330(n):

%o ..if n==0: return 0

%o ..s=1

%o ..for l1 in range(1, n+1):

%o ....s += f( n-l1, l1)

%o ..return s

%o # _Bert Dobbelaere_, Feb 06 2020

%Y Cf. A331332, A103294.

%K nonn

%O 0,4

%A _Peter Luschny_, Jan 24 2020

%E More terms from _Bert Dobbelaere_, Feb 06 2020