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
KEYWORD
nonn,easy
AUTHOR
N. J. A. Sloane, May 27 2012, following a suggestion from R. K. Guy.
STATUS
approved