## Problem of the Day #307: Counting Binary StringsJanuary 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$.

1. Lamis Alsheikh - January 23, 2012

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)