cp's OEIS Frontend

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

%I A331330 #38 May 06 2025 09:24:25
%S A331330 0,1,1,3,4,8,14,26,46,85,155,286,528,980,1824,3410,6392,12022,22675,
%T A331330 42885,81312,154540,294362,561849,1074463,2058462,3950220,7592403,
%U A331330 14614105,28168227,54363000,105043517,203200635,393496975,762765642,1479957400,2874038529,5585986973,10865544853,21150913457,41201771886
%N A331330 a(n) is the number of sparse rulers of length n where the length of the first segment is unique.
%C A331330 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.
%C A331330 Also number of compositions of n where the first part is unique. - _Christian Sievers_, May 06 2025
%H A331330 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 A331330 a(n) = A331332(n,1) for n >= 1.
%F A331330 Conjecture: a(n) ~ 2^n / (n * log(2)). - _Vaclav Kotesovec_, Nov 16 2020
%F A331330 G.f.: Sum_{k>=1} x^k/(1-x/(1-x)+x^k). - _Christian Sievers_, May 06 2025
%e A331330 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 A331330 b:= proc(n, i) option remember; `if`(n=0, 1, add(
%p A331330      `if`(i=j, 0, b(n-j, `if`(n<i+j, 0, i))), j=1..n))
%p A331330     end:
%p A331330 a:= proc(n) option remember; add(b(n-j, j), j=1..n) end:
%p A331330 seq(a(n), n=0..50);  # _Alois P. Heinz_, Feb 06 2020
%t A331330 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 A331330 a[n_] := a[n] = Sum[b[n-j, j], {j, 1, n}];
%t A331330 a /@ Range[0, 50] (* _Jean-François Alcover_, Nov 15 2020, after _Alois P. Heinz_ *)
%o A331330 (Python)
%o A331330 cache={}
%o A331330 def f( n, l1):
%o A331330   args=(n, l1)
%o A331330   if args in cache: return cache[args]
%o A331330   s=0
%o A331330   for l in range(1, n+1):
%o A331330     if l!=l1:
%o A331330       s += 1 if l==n else f(n-l, l1)
%o A331330   cache[args] = s
%o A331330   return s
%o A331330 def a331330(n):
%o A331330   if n==0: return 0
%o A331330   s=1
%o A331330   for l1 in range(1, n+1):
%o A331330     s += f( n-l1, l1)
%o A331330   return s
%o A331330 # _Bert Dobbelaere_, Feb 06 2020
%o A331330 (PARI) \\ omits the initial 0
%o A331330 lista(n)=Vec(sum(k=1,n,(x^k+x*O(x^n))/(1-x/(1-x)+x^k))) \\ _Christian Sievers_, May 06 2025
%Y A331330 Cf. A331332, A103294.
%K A331330 nonn
%O A331330 0,4
%A A331330 _Peter Luschny_, Jan 24 2020
%E A331330 More terms from _Bert Dobbelaere_, Feb 06 2020