|
|
A052920
|
|
a(n) = a(n-3) + a(n-5) with initial values 1,0,0,1,0.
|
|
8
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,9
|
|
COMMENTS
|
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
|
|
|
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)
P.<x> = PowerSeriesRing(ZZ, prec)
return P(1/(1 - x^3 - x^5)).list()
(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
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
encyclopedia(AT)pommard.inria.fr, Jan 25 2000
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|