A386270 Total number of ones in runs of 1s of length <=2 over all binary strings of length n.
0, 1, 4, 9, 22, 52, 120, 272, 608, 1344, 2944, 6400, 13824, 29696, 63488, 135168, 286720, 606208, 1277952, 2686976, 5636096, 11796480, 24641536, 51380224, 106954752, 222298112, 461373440, 956301312, 1979711488, 4093640704, 8455716864, 17448304640, 35970351104
Offset: 0
Examples
For n=4, the binary strings that contain runs of 1s of length <=2 are: 0001, 0010, 0011, 0100, 0101, 0110, 1000, 1001, 1010, 1011, 1100, and 1101. The total number of ones in the runs of 1s of length <=2 is thus a(4)=22.
Links
- Index entries for linear recurrences with constant coefficients, signature (4,-4).
Formula
a(n) = n*2^(n-1) for n<3 and a(n) = (6+4*n)*2^(n-4) for n>=3.