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
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 19.
David Broadhurst, Multiple Deligne values: a data mine with empirically tamed denominators, arXiv:1409.7204 [hep-th], 2014. See p. 10.
Leonard Rozendaal, Pisano word, tesselation, plane-filling fractal, Preprint, 2017.
Alexander Stoimenow, Generating Functions, Fibonacci Numbers and Rational Knots, arXiv:math/0210174 [math.GT], 2002.
Index entries for linear recurrences with constant coefficients, signature (0,1,2,1).
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-1) = A094686(n) - Fib(n). - Paul Barry, Jan 13 2005
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 *)
LinearRecurrence[{0, 1, 2, 1}, {1, 1, 1, 3}, 39] (* Jean-François Alcover, Sep 21 2017 *)
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
Paul Barry, Mar 15 2004
STATUS
approved