cp's OEIS Frontend

A052920 a(n) = a(n-3) + a(n-5) with initial values 1,0,0,1,0.

%I A052920 #47 Jul 02 2025 16:01:58
%S A052920 1,0,0,1,0,1,1,0,2,1,1,3,1,3,4,2,6,5,5,10,7,11,15,12,21,22,23,36,34,
%T A052920 44,58,57,80,92,101,138,149,181,230,250,319,379,431,549,629,750,928,
%U A052920 1060,1299,1557,1810,2227,2617,3109,3784,4427,5336,6401,7536,9120,10828
%N A052920 a(n) = a(n-3) + a(n-5) with initial values 1,0,0,1,0.
%C A052920 From _Bob Selcoe_, May 19 2014: (Start)
%C A052920 Since a(n) is a recurrence of the form a(n) = a(n-F1) + a(n-F2) where seed values are a(0)=1 and a(n)=0 for n<0 exclusively (that is, a(n) is the number of compositions of n into parts F1 and F2), apply the following definitions and operations:
%C A052920 I. Generally, let m' be the maximum and k' be the minimum values such that n = F1*m' + (F2-F1)*k'.
%C A052920 Ia. In this sequence, since F1=3 and F2=5, then n = 3*m' + 2*k'. So for example, when n=49, m'=15 and k'=2 because 49 = 3*15 + 2*2.
%C A052920 II. Let G be the greatest common factor of F1 and F2 (in this sequence, G=1).
%C A052920 IIa. When n = F1*m' + (F2-F1)*k' is null, a(n)=0. When G=1, the greatest such value of n is F1*F2 - F1 - F2. So in this sequence, the greatest value of n where a(n)=0 is 3*5 - 3 - 5 = 7.
%C A052920 III. Then generally: a(n) = Sum_{i=0..j} ((m'-(F2-F1)*i)!/(k'+F1*i/G)!*(m'-k'-F2*i/G)!) where j is the maximum integer value such that j <= G*(m'-k')/F2.
%C A052920 IIIa. In this sequence, a(n) = Sum_{i=0..j} ((m'-2*i)!/(k'+3*i)!*(m'-k'-5*i)!). For example, when n=49, m'=15 and k'=2; therefore j=2 because 1*(15-2)/5 = 2.6. Thus a(49) = 15!/(2!*13!) + 13!/(5!*8!) + 11!/(8!*3!) = 105 + 1287 + 165 = 1557.
%C A052920 IV. Therefore: a(n) can be solved in closed form for all recurrences of this type.
%C A052920 Alternatively, a(n) equals the sum of the diagonal in the binomial triangle (i.e., Pascal's Triangle, A007318) with slope (F2-F1)/F1, starting at C(m',k'). In this sequence, the slope is 2/3. (End)
%H A052920 G. C. Greubel, <a href="/A052920/b052920.txt">Table of n, a(n) for n = 0..1000</a>
%H A052920 Tomislav Došlić, Mate Puljiz, Stjepan Šebek, and Josip Žubrinić, <a href="https://arxiv.org/abs/2401.01225">Predators and altruists arriving on jammed Riviera</a>, arXiv:2401.01225 [math.CO], 2024. See p. 16.
%H A052920 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=903">Encyclopedia of Combinatorial Structures 903</a>
%H A052920 Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Janjic/janjic73.html">Binomial Coefficients and Enumeration of Restricted Words</a>, Journal of Integer Sequences, 2016, Vol 19, #16.7.3.
%H A052920 E. Wilson, <a href="http://www.anaphoria.com/meruone.PDF">The Scales of Mt. Meru</a>
%H A052920 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,1,0,1).
%F A052920 G.f.: 1/(1 - x^3 - x^5).
%F A052920 a(n) = a(n-3) + a(n-5), with a(0)=1, a(1)=0, a(2)=0, a(3)=1, a(4)=0.
%F A052920 a(n) = Sum_{alpha=RootOf(-1 +z^3 +z^5)} (1/3233)*(-60 + 661*alpha + 100*alpha^2 + 36*alpha^3 + 250*alpha^4)*alpha^(-1-n).
%F A052920 a(n) = Sum_{i=0..j} ( (m'-2*i)!/(k'+3*i)!*(m'-k'-5*i)!) (see comments for definitions of variables).
%e A052920 a(49) = 15!/(2!*13!) + 13!/(5!*8!) + 11!/(8!*3!) = 105 + 1287 + 165 = 1557.
%p A052920 spec := [S,{S=Sequence(Prod(Union(Z,Prod(Z,Z,Z)),Z,Z))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);
%p A052920 seq(coeff(series(1/(1 -x^3 -x^5), x, n+1), x, n), n = 0..70); # _G. C. Greubel_, Oct 16 2019
%t A052920 LinearRecurrence[{0,0,1,0,1},{1,0,0,1,0},70] (* _Harvey P. Dale_, Jan 12 2016 *)
%o A052920 (PARI) my(x='x+O('x^70)); Vec(1/(1 - x^3 - x^5)) \\ _G. C. Greubel_, Oct 16 2019
%o A052920 (Magma) R<x>:=PowerSeriesRing(Integers(), 70); Coefficients(R!( 1/(1 - x^3 - x^5) )); // _G. C. Greubel_, Oct 16 2019
%o A052920 (Sage)
%o A052920 def A052920_list(prec):
%o A052920     P.<x> = PowerSeriesRing(ZZ, prec)
%o A052920     return P(1/(1 - x^3 - x^5)).list()
%o A052920 A052920_list(70) # _G. C. Greubel_, Oct 16 2019
%o A052920 (GAP) a:=[1,0,0,1,0];; for n in [6..70] do a[n]:=a[n-3]+a[n-5]; od; a; # _G. C. Greubel_, Oct 16 2019
%Y A052920 Cf. A007318 (binomial triangle).
%K A052920 easy,nonn
%O A052920 0,9
%A A052920 encyclopedia(AT)pommard.inria.fr, Jan 25 2000
%E A052920 More terms from _James Sellers_, Jun 05 2000