OFFSET
1,2
COMMENTS
a(n) is the number of binary strings of length n that contain exactly one run of ones of length 1. - Félix Balado, Oct 03 2025
LINKS
Michael De Vlieger, Table of n, a(n) for n = 1..4083
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 pp. 15, 24.
Phyllis Chinn and Sylvia Heubach, Integer Sequences Related to Compositions without 2's, J. Int. Seq. 6(2) (2003) Article 03.2.3.
James J. Madden, A generating function for the distribution of runs in binary words, arXiv:1707.04351 [math.CO], 2017, Theorem 1.1, r=2, k=1.
Index entries for linear recurrences with constant coefficients, signature (4,-6,6,-5,2,-1).
FORMULA
a(n) = c(0)c(n-1) + c(1)c(n-2) + c(2)c(n-3) + ... + c(n-1)c(0), where c(i) is given by sequence A005251; generating function = (x(1-x)^2)/(1-2x+x^2-x^3)^2.
a(n) = Sum_{k=1..floor((n+2)/3)} k*binomial(n-k+1, 2*k-1). - Vladeta Jovovic, Apr 10 2004
a(n) = 4*a(n-1) - 6*a(n-2) + 6*a(n-3) - 5*a(n-4) + 2*a(n-5) - a(n-6) for n > 6. - Chai Wah Wu, Apr 15 2025
EXAMPLE
a(4)=6 since the compositions of 4 that do not contain a 2 are 1+1+1+1, 1+3, 3+1 and 4, for a total of 6 1's. Also there are 6 occurrences of 5 in the compositions of 8 (= 4+5-1): 1+1+1+5, 1+1+5+1, 1+5+1+1, 5+1+1+1, 5+3 and 3+5 (only compositions without 2's that contain a 5 are listed).
MATHEMATICA
Rest[CoefficientList[ Normal[Series[x(1 - x)^2/((1 - 2x + x^2 - x^3)^2), {x, 0, 50}]], x]]
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Silvia Heubach (sheubac(AT)calstatela.edu), Jan 23 2003
STATUS
approved