|
|
A079289
|
|
For even n, a(n) = a(n-2) + a(n-1) + 2^(n/2-2), n>2. For odd n, a(n) = a(n-2) + a(n-1).
|
|
3
|
|
|
1, 1, 2, 3, 6, 9, 17, 26, 47, 73, 128, 201, 345, 546, 923, 1469, 2456, 3925, 6509, 10434, 17199, 27633, 45344, 72977, 119345, 192322, 313715, 506037, 823848, 1329885, 2161925, 3491810, 5670119, 9161929, 14864816, 24026745, 38957097, 62983842
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Generalized Fibonacci sequence: a(n) = a(n-2) + a(n-1), and for even n a row sum of Pascal's triangle (a power of two) is added.
Call a multiset of nonzero integers good if the sum of the cubes is the square of the sum. The number of ascending chains of good multisets starting from the empty set by adding one element at a time is a(n). - Michael Somos, Apr 14 2005
a(n) is the number of compositions of n which consist of an initial (possibly empty) subsequence of even summands and a remaining (possibly empty) sequence of odd summands.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = a(n-2) + a(n-1) + floor(2^(n/2-2))*(1-(-1)^(n+1))/2 for n>1.
G.f.: (1-x^2)^2/((1-x-x^2)*(1-2*x^2)).
If n = 2k+1, a(n) = the convolution Sum_{j=0,..k} c(j)*F(n-2j), where c(j) = A011782(j) = 2^(j-1) and f(j)= A000045(j).
If n = 2k, a(n) = c(k) + the convolution Sum_{j=0,..(k-1)} c(j)*F(n-2j), where c(j)=A011782(j)=2^(j-1) and f(j)= A000045(j). (End)
|
|
EXAMPLE
|
a(4) = 6 from the good multisets {-1,-1,1,1}, {-1,1,1,2}, {-2,-1,1,2}, {-2,1,2,2}, {-3,1,2,3}, {1,2,3,4}.
a(4) = 6 because there are six compositions of four, in which the initial parts are all even and the final parts are all odd: 4, 3+1, 1+3, 2+2, 2+1+1, 1+1+1+1.
|
|
MATHEMATICA
|
CoefficientList[Series[(1-x^2)^2/(1-x-x^2)/(1-2x^2), {x, 0, 37}], x]
LinearRecurrence[{1, 3, -2, -2}, {1, 1, 2, 3, 6}, 25] (* G. C. Greubel, Aug 16 2016; corrected by Georg Fischer, Apr 02 2019 *)
nxt[{n_, a_, b_}]:={n+1, b, If[EvenQ[n], a+b, a+b+2^((n+1)/2-2)]}; Join[{1}, NestList[ nxt, {2, 1, 2}, 40][[All, 2]]] (* Harvey P. Dale, Jul 13 2019 *)
|
|
PROG
|
(PARI) {a(n)=local(A); if(n<3, (n>=0)+(n>1), A=vector(n, i, i); for(i=3, n, A[i]=A[i-1]+A[i-2]+ if(i%2==0, 2^(i/2-2))); A[n])} /* Michael Somos, Apr 14 2005 */
(Magma) I:=[1, 1, 2, 3, 6]; [n le 5 select I[n] else Self(n-1)+3*Self(n-2) -2*Self(n-3)-2*Self(n-4): n in [1..40]]; // Vincenzo Librandi, Aug 05 2013
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|