Find the number of binary strings of length 40, for which, in any sub-string of length 6, there are maximum 3 "1".

OK, to start with:

All possible sub-strings are 35 (40-5+1).

Let's check what happens in each string of length 6:

In order to find all possible arrangements so as to have at most 3 1s, we take the sum of the possible arrangements for 0, 1, 2 and 3:

[tex]{6 \choose 0}+{6 \choose 1}+{6 \choose 2}+{6 \choose 3}=1+6+15+20=42[/tex]out of the total 64 (2^6).

But for every 2 consecutive strings of length 6, we have 4 digits in common (omitting the 1st and last one).

What do we do next?