login
A093040
Expansion of (1+x)/((1+x+x^2)(1-x-x^2)).
8
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
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
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.
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
2*a(n) = A057078(n) + A000045(n+2). - R. J. Mathar, Sep 16 2017
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
Sequence in context: A001130 A348529 A069825 * A022935 A374762 A192813
KEYWORD
easy,nonn
AUTHOR
Paul Barry, Mar 15 2004
STATUS
approved