Permutations

Ask the math tutor!

Permutations

Postby jason » Wed Jul 19, 2017 5:55 am

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?





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

Return to Ask the tutor



Who is online

Users browsing this forum: No registered users and 1 guest