|
|
A093040
|
|
Expansion of (1+x)/((1+x+x^2)(1-x-x^2)).
|
|
4
|
|
|
1, 1, 1, 3, 4, 6, 11, 17, 27, 45, 72, 116, 189, 305, 493, 799, 1292, 2090, 3383, 5473, 8855, 14329, 23184, 37512, 60697, 98209, 158905, 257115, 416020, 673134, 1089155, 1762289, 2851443, 4613733, 7465176, 12078908, 19544085, 31622993, 51167077
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
The sequence 0,1,1,1,3... has a(n) = Fib(n+1)/2-A049347(n)/2. It counts paths of length n between two of the vertices of the graph with adjacency matrix [0,1,0,0;0,0,1,1;1,1,0,0;0,0,1,0].
Diagonal sums of Riordan array ((1+x), x(1+x)^2). - Paul Barry, May 31 2006
a(n) is the number of compositions of n into parts 1,2,3 with no two consecutive 1's. For example a(5) = 6 because we have: 3+2, 2+3, 1+3+1, 2+2+1, 2+1+2, 1+2+2. - Geoffrey Critzer, Mar 15 2014
a(n) is the number of compositions of n+1 into an odd number of parts 1 and 2, that is, the number of barcodes of width n+1 with alternating black and white bars of width 1 or 2 and black border (see the first recurrence formula). - Grégoire Nicollier, Apr 04 2022
|
|
REFERENCES
|
MacKay, Information Theory, Inference and Learning Algorithms, CUP, 2003, p. 251
|
|
LINKS
|
|
|
FORMULA
|
G.f.: ((1+x)/(1-x-x^2)+(1-x^2)/(1-x^3))/2.
a(n) = a(n-2) + 2*a(n-3) + a(n-4).
a(n) = Fib(n+2)/2+sqrt(3)sin(2*Pi*n/3+Pi/3)/3 = Fib(n+2)/2+A057078(n)/2.
a(n-1) = Sum_{k=0..floor(n/2)} if(mod(n-k, 2)=1, binomial(n-k, k), 0).
a(n) = Sum_{k=0..floor(n/2)} binomial(2k+1,n-2k). - Paul Barry, May 31 2006
a(n) = floor(Fibonacci(n+3)/2) - floor(Fibonacci(n+1)/2). - Gary Detlefs, Mar 13 2011
a(n) = a(n-2) + 2*a(n-3) + a(n-4), a(-3-n) = (-1)^n * A005252(n) for all n in Z. - Michael Somos, Mar 19 2014
a(n-1) + 2*a(n) - a(n+2) = a(n) - a(n-1) - a(n-2) = A057078(n) for all n in Z. - Michael Somos, Mar 19 2014
|
|
EXAMPLE
|
G.f. = 1 + x + x^2 + 3*x^3 + 4*x^4 + 6*x^5 + 11*x^6 + 17*x^7 + 27*x^8 + 45*x^9 + ...
|
|
MATHEMATICA
|
CoefficientList[Series[((1+x)/(1-x-x^2)+(1-x^2)/(1-x^3))/2, {x, 0, 50}], x] (* Vincenzo Librandi, Jul 10 2012 *)
a[ n_] := SeriesCoefficient[ If[ n < 0, x^3 (1 + x) / (1 + 2 x + x^2 - x^4), (1 + x) / (1 - x^2 - 2 x^3 - x^4)], {x, 0, Abs@n}]; (* Michael Somos, Mar 19 2014 *)
|
|
PROG
|
(Magma) [Floor(Fibonacci(n+3)/2)-Floor(Fibonacci(n+1)/2): n in [1..50]]; // Vincenzo Librandi, Jul 10 2012
(PARI) Vec(((1+x)/(1-x-x^2)+(1-x^2)/(1-x^3))/2 + O(x^50)) \\ Michel Marcus, Sep 27 2014
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|