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

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

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

Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, Dyck Paths with catastrophes modulo the positions of a given pattern, Australasian J. Comb. (2022) Vol. 84, No. 2, 398-418.

Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 11.

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/(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, n-k) - C(k, n-k-1)). - Peter Luschny, Oct 01 2014

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

a(n) = A000045(n-1), 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)

Maple

a := n -> -I^n*ChebyshevU(n-2, -I/2):
seq(simplify(a(n)), n = 0..49);  # Peter Luschny, Dec 03 2023

Mathematica

Table[Fibonacci[n-1], {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