A164415 Number of binary strings of length n with no substrings equal to 0000, 0001, or 1100.
1, 2, 4, 8, 13, 22, 38, 65, 112, 193, 332, 572, 985, 1696, 2921, 5030, 8662, 14917, 25688, 44237, 76180, 131188, 225917, 389048, 669973, 1153750, 1986854, 3421529, 5892160, 10146793, 17473628, 30091052, 51819313, 89237200, 153673937, 264639398, 455731222
Offset: 0
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..2000 (first 500 terms from R. H. Hardin)
- Index entries for linear recurrences with constant coefficients, signature (1, 1, 1, -1).
Formula
G.f.: -(x+1)*(x^5-x^2-1)/(x^4-x^3-x^2-x+1). - R. J. Mathar, Nov 28 2011
Extensions
Edited by Alois P. Heinz, Oct 12 2017