How many binary strings of length 12 (that is; sequences of length 12 whose entries are chosen from { 0, 1 }) have every occurrence of two 1’s separated by at least two 0’s? For example, 100100010000 is such a string, while 010100000000 is not. Please do not actually find all such strings (except as a check of your own); a counting analysis is required. Hint: partition the set of all such strings according to the number of 1’s that appear in the string.
Thanks
Counting and Permutation
2009-10-28 4:44 am
回答 (1)
2009-10-28 5:34 am
✔ 最佳答案
It is easy to know that the range of the number of '1' in the strings is 0 to 4.When four '1' in the strings , we can make a transfer :
Delete two '0' between two '1'
For example : 100 100 010000 ---> 11010000
Case 1 : when four '1' in the strings :
We may cross out 3 groups of '00' between four '1' ;
After transfer : The strings becomes of length 12 - 2*3 = 6 , and must have and only have four '1' .
So there are 6C4 = 15 cases.
Case 2 : when three '1' in the strings :
We may cross out 2 groups of '00' between three '1' ;
The length of the strings = 12 - 2*2 = 8 , and must have and only have three '1' .
8C3 = 56 cases
Case 3 : when two '1' in the strings :
We may cross out 1 group of '00' between two '1' ;
The length of the strings = 12 - 2 = 10 , and must have and only have
two '1' .
10C2 = 45 cases
Case 4 : when one '1' in the strings , 12 cases.
Case 5 : when no '1' in the strings , 1 case.
Total 15 + 56 + 45 + 12 + 1 = 129 cases.
收錄日期: 2021-04-21 22:03:43
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20091027000051KK01373