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,9

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)

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

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

Example

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

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

Prog

(PARI) my(x='x+O('x^70)); Vec(1/(1 - x^3 - x^5)) \\ G. C. Greubel, Oct 16 2019
(Magma) R<x>:=PowerSeriesRing(Integers(), 70); Coefficients(R!( 1/(1 - x^3 - x^5) )); // G. C. Greubel, Oct 16 2019
(Sage)
def A052920_list(prec):
    P.<x> = PowerSeriesRing(ZZ, prec)
    return P(1/(1 - x^3 - x^5)).list()
A052920_list(70) # G. C. Greubel, Oct 16 2019
(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

Crossrefs

Cf. A007318 (binomial triangle).

Sequence in context: A092865 A098925 A102426 * A320250 A089141 A336084

Adjacent sequences: A052917 A052918 A052919 * A052921 A052922 A052923

Keyword

easy,nonn

Author

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

Extensions

More terms from James A. Sellers, Jun 05 2000

Status

approved