A230177 - OEIS

A230177

Number of binary strings of length n avoiding "squares" (that is, repeated blocks of the form xx) with |x| > 3.

1, 2, 4, 8, 16, 32, 64, 128, 240, 464, 866, 1642, 3048, 5720, 10642, 19868, 36894, 68722, 127630, 237324, 440594, 818584, 1519802, 2822630, 5240262, 9730478, 18065252, 33542006, 62272196, 115616582, 214646190, 398507348, 739840164, 1373551484, 2550032248

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

LINKS

Table of n, a(n) for n=0..34.

R. C. Entringer, D. E. Jackson and J. A. Schatz, On nonrepetitive sequences, J. Combin. Theory Ser. A. 16 (1974), 159-164.

Nathaniel Johnston, C code for computing this sequence

EXAMPLE

a(8) = 256 - 16 = 240 because there are 256 binary strings of length 8, 16 of which contain a repeated block of length 4: 00000000, 00010001, 00100010, ..., 11111111.

CROSSREFS

Cf. A229614, A230127, A230216.

Sequence in context: A229617 A306316 A275061 * A216264 A054045 A008860

Adjacent sequences: A230174 A230175 A230176 * A230178 A230179 A230180

KEYWORD

nonn

AUTHOR

Nathaniel Johnston, Oct 11 2013

STATUS

approved