# Permutations

### Permutations

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

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:
${6 \choose 0}+{6 \choose 1}+{6 \choose 2}+{6 \choose 3}=1+6+15+20=42$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?

jason

Posts: 14
Joined: Wed Jan 11, 2017 10:17 am
Reputation: 1