OFFSET
0,2
COMMENTS
a(n) is the number of binary words of length n+2 such that there is at least one run of 0's and every run of 0's is of length >=2. a(1)=3 because we have: {0,0,0}, {0,0,1}, {1,0,0}. - Geoffrey Critzer, Jan 12 2013
INVERT transform of A099254: (1, 2, 1, -2, -4, -2, 3, 6, 3, ...). - Gary W. Adamson, Jan 11 2017
a(n) is the number of nonempty subsets A of {1, 2, ..., n+1} with the property that every element in A has at least one consecutive neighbor also in A. That is, for every element x in A, either x-1 is in A or x+1 is in A. - MingKun Yue, Mar 07 2025
LINKS
Seiichi Manyama, Table of n, a(n) for n = 0..4092
Félix Balado and Guénolé C. M. Silvestre, Systematic Enumeration of Fundamental Quantities Involving Runs in Binary Strings, arXiv:2602.10005 [math.CO], 2026. See p. 33.
Index entries for linear recurrences with constant coefficients, signature (3,-3,2,-1).
FORMULA
G.f.: 1/((1-2*x+x^2-x^3)*(1-x)).
a(n) = 3*a(n-1) - 3*a(n-2) + 2*a(n-3) - a(n-4). - Seiichi Manyama, Nov 25 2016
a(n) = Sum_{i=1..(n+3)} binomial((n+3)-i, (n+3)-3*i). - Wesley Ivan Hurt, Jul 07 2020
a(n) ~ (48 - 11*r + 29*r^2) / (23 * r^n), where r = 0.569840290998... is the root of the equation r*(2 - r + r^2) = 1. - Vaclav Kotesovec, Apr 15 2024
From MingKun Yue, Mar 07 2025: (Start)
a(n) = 2*a(n-1) - a(n-2) + a(n-3) + 1.
a(n) = a(n-1) + Sum_{i=1..(n-3)} a(i) + n. (End)
MATHEMATICA
nn=40; a=x^2/(1-x); Drop[CoefficientList[Series[(a+1)/(1-x a/(1-x))/(1-x)-1/(1-x), {x, 0, nn}], x], 2] (* Geoffrey Critzer, Jan 12 2013 *)
LinearRecurrence[{3, -3, 2, -1}, {1, 3, 6, 11}, 36] (* or *)
CoefficientList[ Series[1/(x^4 - 2 x^3 + 3 x^2 - 3 x + 1), {x, 0, 35}], x] (* Robert G. Wilson v, Nov 25 2016 *)
PROG
(PARI) Vec((1-x)^(-1)/(1-2*x+x^2-x^3)+O(x^99)) \\ Charles R Greathouse IV, Sep 27 2012
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
N. J. A. Sloane, Nov 17 2002
STATUS
approved