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.

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

Links

Table of n, a(n) for n=4..31.

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

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

Adjacent sequences: A118645 A118646 A118647 * A118649 A118650 A118651

Keyword

nonn

Author

Tanya Khovanova, May 10 2006

Status

approved