A387573 Total number of runs of 1's in all length n binary words in which 1's occur in runs of at least 3.

0, 0, 1, 3, 6, 10, 17, 31, 58, 106, 188, 328, 570, 990, 1715, 2957, 5074, 8674, 14787, 25149, 42676, 72260, 122104, 205952, 346804, 583100, 979013, 1641575, 2749150, 4598730, 7684437, 12827739, 21393326, 35646798, 59346996, 98726376, 164112814, 272611226, 452535543, 750730321

Offset

1,4

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (4,-6,4,1,-4,2,0,-1).

Formula

a(n) = Sum_{i=1..floor((n+1)/4)} i*binomial(n+1-2*i,2*i).

G.f.: x^3*(1 - x)/((1 - x + x^2)^2*(1 - x - x^2)^2).

Example

a(6) = 10 counts the number of runs of 1's in {000111, 001110, 011100, 111000, 001111, 011110, 111100, 011111, 111110, 111111}.
a(7) = 17 counts 15 words with one run of 1's and 1110111 has two runs of 1's.

Prog

(PARI) my(N=40); Vec(x^3*(1 - x)/((1 - x + x^2)^2*(1 - x - x^2)^2) + O(x*x^N), -N)
(PARI) a(n) = sum(i=1, (n+1)\4, i*binomial(n+1-2*i, 2*i))

Crossrefs

Column 3 of A388717.

Sequence in context: A092263 A259968 A242525 * A266617 A291608 A182152

Adjacent sequences: A387570 A387571 A387572 * A387574 A387575 A387576

Keyword

nonn,easy

Author

Andrew Howroyd, Oct 05 2025

Status

approved