

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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

4,1


COMMENTS

a(n) = 2^(n+4)  sum of all elements of the nth 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*xx^22*x^3+8*x^4) / ( (2*x1)*(x^4+x1) ).  R. J. Mathar, Nov 28 2011


CROSSREFS

Sequence in context: A031025 A140675 A161532 * A262105 A105270 A039337
Adjacent sequences: A118645 A118646 A118647 * A118649 A118650 A118651


KEYWORD

nonn


AUTHOR

Tanya Khovanova, May 10 2006


STATUS

approved



