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

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, 44, 58, 57, 80, 92, 101, 138, 149, 181, 230, 250, 319, 379, 431, 549, 629, 750, 928, 1060, 1299, 1557, 1810, 2227, 2617, 3109, 3784, 4427, 5336, 6401, 7536, 9120, 10828

Offset: 0

Author

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Keywords

• easy
• nonn

Comments

From Bob Selcoe, May 19 2014: (Start)

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:

I. Generally, let m' be the maximum and k' be the minimum values such that n = F1*m' + (F2-F1)*k'.

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.

II. Let G be the greatest common factor of F1 and F2 (in this sequence, G=1).

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.

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.

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.

IV. Therefore: a(n) can be solved in closed form for all recurrences of this type.

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)

Examples

			a(49) = 15!/(2!*13!) + 13!/(5!*8!) + 11!/(8!*3!) = 105 + 1287 + 165 = 1557.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• Tomislav Došlić, Mate Puljiz, Stjepan Šebek, and Josip Žubrinić, Predators and altruists arriving on jammed Riviera, arXiv:2401.01225 [math.CO], 2024. See p. 16.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 903
• Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3.
• E. Wilson, The Scales of Mt. Meru
• Index entries for linear recurrences with constant coefficients, signature (0,0,1,0,1).

Crossrefs

Cf. A007318 (binomial triangle).

Programs

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

Magma

R:=PowerSeriesRing(Integers(), 70); Coefficients(R!( 1/(1 - x^3 - x^5) )); // G. C. Greubel, Oct 16 2019

Maple

spec := [S,{S=Sequence(Prod(Union(Z,Prod(Z,Z,Z)),Z,Z))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);
seq(coeff(series(1/(1 -x^3 -x^5), x, n+1), x, n), n = 0..70); # G. C. Greubel, Oct 16 2019

Mathematica

LinearRecurrence[{0,0,1,0,1},{1,0,0,1,0},70] (* Harvey P. Dale, Jan 12 2016 *)

PARI

my(x='x+O('x^70)); Vec(1/(1 - x^3 - x^5)) \\ G. C. Greubel, Oct 16 2019

Sage

def A052920_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P(1/(1 - x^3 - x^5)).list()
A052920_list(70) # G. C. Greubel, Oct 16 2019

Formula

G.f.: 1/(1 - x^3 - x^5).

a(n) = a(n-3) + a(n-5), with a(0)=1, a(1)=0, a(2)=0, a(3)=1, a(4)=0.

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).

a(n) = Sum_{i=0..j} ( (m'-2*i)!/(k'+3*i)!*(m'-k'-5*i)!) (see comments for definitions of variables).

Extensions

More terms from James Sellers, Jun 05 2000