A093040 - OEIS

%I #62 Mar 09 2024 12:32:09

%S 1,1,1,3,4,6,11,17,27,45,72,116,189,305,493,799,1292,2090,3383,5473,

%T 8855,14329,23184,37512,60697,98209,158905,257115,416020,673134,

%U 1089155,1762289,2851443,4613733,7465176,12078908,19544085,31622993,51167077

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

%C 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].

%C Diagonal sums of Riordan array ((1+x), x(1+x)^2). - _Paul Barry_, May 31 2006

%C 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

%C 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

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

%H Vincenzo Librandi, <a href="/A093040/b093040.txt">Table of n, a(n) for n = 0..1000</a>

%H Joshua P. Bowman, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL27/Bowman/bowman4.html">Compositions with an Odd Number of Parts, and Other Congruences</a>, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 19.

%H David Broadhurst, <a href="http://arxiv.org/abs/1409.7204">Multiple Deligne values: a data mine with empirically tamed denominators</a>, arXiv:1409.7204 [hep-th], 2014. See p. 10.

%H Leonard Rozendaal, <a href="https://hal.archives-ouvertes.fr/hal-01552281">Pisano word, tesselation, plane-filling fractal</a>, Preprint, 2017.

%H Alexander Stoimenow, <a href="https://arxiv.org/abs/math/0210174">Generating Functions, Fibonacci Numbers and Rational Knots</a>, arXiv:math/0210174 [math.GT], 2002.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,1,2,1).

%F G.f.: ((1+x)/(1-x-x^2)+(1-x^2)/(1-x^3))/2.

%F a(n) = a(n-2) + 2*a(n-3) + a(n-4).

%F a(n) = Fib(n+2)/2+sqrt(3)sin(2*Pi*n/3+Pi/3)/3 = Fib(n+2)/2+A057078(n)/2.

%F a(n-1) = Sum_{k=0..floor(n/2)} if(mod(n-k, 2)=1, binomial(n-k, k), 0).

%F a(n-1) = A094686(n) - Fib(n). - _Paul Barry_, Jan 13 2005

%F a(n) = Sum_{k=0..floor(n/2)} binomial(2k+1,n-2k). - _Paul Barry_, May 31 2006

%F a(n) = floor(Fibonacci(n+3)/2) - floor(Fibonacci(n+1)/2). - _Gary Detlefs_, Mar 13 2011

%F 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

%F 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

%F 2*a(n) = A057078(n) + A000045(n+2). - _R. J. Mathar_, Sep 16 2017

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

%t CoefficientList[Series[((1+x)/(1-x-x^2)+(1-x^2)/(1-x^3))/2,{x,0,50}],x] (* _Vincenzo Librandi_, Jul 10 2012 *)

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

%t LinearRecurrence[{0, 1, 2, 1}, {1, 1, 1, 3}, 39] (* _Jean-François Alcover_, Sep 21 2017 *)

%o (Magma) [Floor(Fibonacci(n+3)/2)-Floor(Fibonacci(n+1)/2): n in [1..50]]; // _Vincenzo Librandi_, Jul 10 2012

%o (PARI) Vec(((1+x)/(1-x-x^2)+(1-x^2)/(1-x^3))/2 + O(x^50)) \\ _Michel Marcus_, Sep 27 2014

%Y Cf. A005252, A057078.

%K easy,nonn

%O 0,4

%A _Paul Barry_, Mar 15 2004