A212804 - OEIS

%I #138 Mar 09 2025 12:28:47

%S 1,0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,

%T 6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,

%U 832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976

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

%C A variant of the Fibonacci number A000045.

%C Number of compositions of n into parts >= 2. - _Joerg Arndt_, Aug 13 2012

%C From _Petros Hadjicostas_, Jan 08 2019: (Start)

%C For n >= 0, a(n) is the number of unmarked circular binary words (necklaces) of length n+1 with exactly one occurrence of the pattern 00 (provided we allow the strings of length 1, i.e., 0 and 1, to wrap around themselves on a circle to form strings of length 2). See the comments for array A320341.

%C Using MacMahon's bijection between necklaces and cyclic compositions, we conclude that a(n) is also the number of (unmarked) cyclic compositions of n+1 with exactly one 1.

%C Removing the single 1 from each cyclic composition of n+1, we get all linear compositions of n with each part >= 2, which is what is stated above by _Joerg Arndt_. (End)

%D John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 84.

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

%H Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, <a href="https://ajc.maths.uq.edu.au/pdf/84/ajc_v84_p398.pdf">Dyck Paths with catastrophes modulo the positions of a given pattern</a>, Australasian J. Comb. (2022) Vol. 84, No. 2, 398-418.

%H Jia Huang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Huang/huang8.html">Partially Palindromic Compositions</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 11.

%H J. J. Madden, <a href="http://arxiv.org/abs/1707.04351">A generating function for the distribution of runs in binary words</a>, arXiv:1707.04351 [math.CO], 2017, Theorem 1.1, r=1 and k=0.

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

%F G.f.: 1/(1 - (Sum_{k >= 2} x^k)). - _Joerg Arndt_, Aug 13 2012

%F a(n) = Fibonacci(n+1) - Fibonacci(n). - _Arkadiusz Wesolowski_, Oct 29 2012

%F G.f.: 1 - x*Q(0) where Q(k) = 1 - (1 + x)/(1 - x/(x - 1/Q(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Mar 06 2013

%F G.f.: 3*x^3/(3*x - Q(0)) - x^2 + 1, where Q(k) = 1 - 1/(4^k - x*16^k/(x*4^k - 1/(1 + 1/(2*4^k - 4*x*16^k/(2*x*4^k + 1/Q(k+1)))))); (continued fraction). - _Sergei N. Gladkovskii_, May 21 2013

%F G.f.: G(0)*(1 - x)/(2 - x), where G(k) = 1 + 1/(1 - (x*(5*k - 1))/((x*(5*k + 4)) - 2/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Jun 15 2013

%F G.f.: 1 + Q(0)*x^2/2, where Q(k) = 1 + 1/(1 - x*(2*k + 1 + x)/( x*(2*k + 2 + x) + 1/Q(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Aug 29 2013

%F a(n) = Sum_{k=0..n} (C(k, n-k) - C(k, n-k-1)). - _Peter Luschny_, Oct 01 2014

%F a(n) = (2^(-1-n)*((1 - sqrt(5))^n*(1 + sqrt(5)) + (-1 + sqrt(5))*(1 + sqrt(5))^n))/sqrt(5). - _Colin Barker_, Sep 25 2016

%F a(n) = A000045(n-1), n >= 1. - _R. J. Mathar_, Apr 14 2018

%F E.g.f.: exp((1 - sqrt(5))*x/2)*(3 + sqrt(5) + 2*exp(sqrt(5)*x))/(5 + sqrt(5)). - _Stefano Spezia_, Mar 09 2025

%e From _Petros Hadjicostas_, Jan 08 2019: (Start)

%e For n = 6, we have a(6) = 5. The binary necklaces of length n+1 = 7 with exactly one occurrence of 00 are as follows: 0011111, 0010111, 0011011, 0011101, and 0010101.

%e The corresponding cyclic compositions of n+1 = 7 with exactly one 1 (under MacMahon's bijection) are as follows: 1+6, 1+2+4, 1+3+3, 1+4+2, 1+2+2+2.

%e Of course, removing the 1 from the cyclic composition, we get a (linear) composition of n = 6 with parts >= 2 (as stated above by _Joerg Arndt_): 6, 2+4, 3+3, 4+2, 2+2+2. (For linear compositions, 2+4 is not the same as 4+2.) (End)

%p a := n -> -I^n*ChebyshevU(n-2, -I/2):

%p seq(simplify(a(n)), n = 0..49);  # _Peter Luschny_, Dec 03 2023

%t Table[Fibonacci[n-1], {n, 0, 40}] (* _Vladimir Reshetnikov_, Sep 24 2016 *)

%o (Magma)

%o [Fibonacci(n + 1) - Fibonacci(n): n in [0..50]]; // _Vincenzo Librandi_, Dec 09 2012

%o (Sage)

%o def A212804():

%o     a, b = True, False

%o     x, y = 1, 0

%o     while True:

%o         yield x if a else -x

%o         x, y = y, x - y

%o         a, b = b, a

%o a = A212804()

%o print([next(a) for _ in range(50)]) # _Peter Luschny_, Mar 19 2020

%Y Cf. A000045, A105809 (alternating row sums).

%Y Column k=1 of A320341.

%K nonn,easy,changed

%O 0,5

%A _N. J. A. Sloane_, May 27 2012, following a suggestion from _R. K. Guy_.