A093040 Expansion of (1+x)/((1+x+x^2)(1-x-x^2)).

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

Author

Paul Barry, Mar 15 2004

Keywords

• easy
• nonn

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

Examples

			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 + ...
		

References

• MacKay, Information Theory, Inference and Learning Algorithms, CUP, 2003, p. 251

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Levi Axelrod, Nathan Bickel, Anastasia Halfpap, Luke Hawranick, Alex Parker, and Cole Swain, Statistics of maximal independent sets in grid-like graphs, arXiv:2506.22317 [math.CO], 2025. See p. 20.
• 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).

Crossrefs

Cf. A005252, A057078.

Programs

Magma

[Floor(Fibonacci(n+3)/2)-Floor(Fibonacci(n+1)/2): n in [1..50]]; // Vincenzo Librandi, Jul 10 2012

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 *)

PARI

Vec(((1+x)/(1-x-x^2)+(1-x^2)/(1-x^3))/2 + O(x^50)) \\ Michel Marcus, Sep 27 2014

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