login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A118648
a(n) is the number of binary strings of length n+3 such that there exists a subsequence of length 4 with 2 ones in it.
0
11, 25, 54, 114, 237, 486, 988, 1998, 4027, 8097, 16253, 32587, 65286, 130727, 261668, 523631, 1047669, 2095900, 4192576, 8386223, 16773924, 33549888, 67102592, 134209071, 268423507, 536854419, 1073719059, 2147452226
OFFSET
4,1
COMMENTS
a(n) = 2^(n+4) - sum of all elements of the n-th power of the matrix [[1 1 0 0 0] [0 0 1 0 0] [0 0 0 1 0] [0 0 0 0 1] [1 1 0 0 0]] which is the transition matrix for the last four bits being 0000, 0001, 0010, 0100, 1000. - Joshua Zucker, Aug 04 2006
FORMULA
G.f.: -x^4*(-11+8*x-x^2-2*x^3+8*x^4) / ( (2*x-1)*(x^4+x-1) ). - R. J. Mathar, Nov 28 2011
MATHEMATICA
LinearRecurrence[{3, -2, 0, 1, -2}, {11, 25, 54, 114, 237}, 30] (* Harvey P. Dale, Aug 14 2019 *)
CROSSREFS
Sequence in context: A140675 A161532 A328560 * A262105 A105270 A039337
KEYWORD
nonn
AUTHOR
Tanya Khovanova, May 10 2006
STATUS
approved