

A212804


Expansion of (1  x)/(1  x  x^2).


26



1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

A variant of the Fibonacci number A000045.
Number of compositions of n into parts >= 2.  Joerg Arndt, Aug 13 2012
From Petros Hadjicostas, Jan 08 2019: (Start)
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.
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.
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)


LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
J. J. Madden, A generating function for the distribution of runs in binary words, arXiv:1707.04351 [math.CO], 2017, Theorem 1.1, r=1 and k=0.
Index entries for linear recurrences with constant coefficients, signature (1,1).


FORMULA

G.f.: (1  x)/(1  x  x^2) = (1  x)*G(0)/(x*sqrt(5)) where G(k)= 1 ((1)^k)*2^k/(a^k  b*x*a^k*2^k/(b*x*2^k  2*((1)^k)*c^k/G(k+1))) and a = 3 + sqrt(5), b = 1 + sqrt(5), c = 3  sqrt(5); (continued fraction, 3rd kind, 3step).  Sergei N. Gladkovskii, Jun 04 2012
G.f.: 1/(1  (Sum_{k >= 2} x^k)).  Joerg Arndt, Aug 13 2012
a(n) = Fibonacci(n+1)  Fibonacci(n).  Arkadiusz Wesolowski, Oct 29 2012
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
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
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
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
a(n) = Sum_{k=0..n} (C(k, nk)  C(k, nk1)).  Peter Luschny, Oct 01 2014
a(n) = (2^(1n)*((1  sqrt(5))^n*(1 + sqrt(5)) + (1 + sqrt(5))*(1 + sqrt(5))^n))/sqrt(5).  Colin Barker, Sep 25 2016
a(n) = A000045(n1), n >= 1.  R. J. Mathar, Apr 14 2018


EXAMPLE

From Petros Hadjicostas, Jan 08 2019: (Start)
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.
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.
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)


MATHEMATICA

Table[Fibonacci[n1], {n, 0, 40}] (* Vladimir Reshetnikov, Sep 24 2016 *)


PROG

(MAGMA)
[Fibonacci(n + 1)  Fibonacci(n): n in [0..50]]; // Vincenzo Librandi, Dec 09 2012
(Sage)
def A212804():
a, b = True, False
x, y = 1, 0
while True:
yield x if a else x
x, y = y, x  y
a, b = b, a
a = A212804()
print([next(a) for _ in range(50)]) # Peter Luschny, Mar 19 2020


CROSSREFS

Cf. A000045, A105809 (alternating row sums).
Column k=1 of A320341.
Sequence in context: A000045 A324969 A020695 * A132916 A274163 A177194
Adjacent sequences: A212801 A212802 A212803 * A212805 A212806 A212807


KEYWORD

nonn,easy


AUTHOR

N. J. A. Sloane, May 27 2012, following a suggestion from R. K. Guy.


STATUS

approved



