## Problem of the Day #307: Counting Binary Strings
*January 20, 2012*

*Posted by Saketh in : potd , trackback*

Determine, in terms of $n$, the number of binary strings of length $2n-1$ that do not contain any substrings of length $n$ that are all $0$ or all $1$.

## Comments»

all possibilities: 2^(2n-1)

number of possibilities that we have substrings of length n that are all 1 : n* 2^(n-1)

so number of possibilities in which we have substrings of length n that are all 1 or 0:

n* 2^n

so the number is: 2^(2n-1) – n 2^n

= (2^n)(2^(n-1) – n)