Count the number of strings of length 9 over the alphabet {a, b, c} subject to e
ID: 3012424 • Letter: C
Question
Count the number of strings of length 9 over the alphabet {a, b, c} subject to each of the following restrictions.
(d) The first character is the same as the last character, or the last character is a, or the first character is a.
(e) The string contains at least seven consecutive a's.
(f) The characters in the string "abababa" appear consecutively somewhere in the 9-character string. (So "ccabababa" would be such a 9-character string, but "cababcaba" would not.)
(g) The string has exactly 2 a's or exactly 3 b's. (h) The string has exactly 2 a's or exactly 2 b's or exactly 2 c's
Explanation / Answer
(d) The first character is the same as the last character, or the last character is a, or the first character is a.
Case 1: when the first character is same as the last character.
The remaining 7 characters can be any thing from a, b, c. The number of ways of choosing one character for the first and the last position is 3 ways. So, the total number of strings with same first and last character =3*3^7=6561
Case 2: the last character is a.
Here, the first character can not be a otherwise it will same as the case1. So, for the first character we have two choices. and the remaining 7 characters we have the number of ways as 3^7. Therefore, the total number of strings with last character as a is=2*3^7*1=4374
Case 3:the first character is a.
Here, the last character can not be a otherwise it will same as the case1. So, for the last character we have two choices. and the remaining 7 characters we have the number of ways as 3^7. Therefore, the total number of strings with first character as a is=2*3^7*1=4374
Therefore, the total number of strings of length 9 with the first character is the same as the last character, or the last character is a, or the first character is a
=6561+4374+4374
=15309
e) The string contains at least seven consecutive a's.
The string can have 7 consecutive a's or, 8 consecutive a's or all the 9 characters as a.
Case1: 7 consecutive a's
we will consider these 7 consecutive a's as a single character. so, we will have 3 places to be filled up.
(i) 7 a's in the first place, second place by b or c, third place by a, b, or c. =1*2*3=6
(ii) first place by b or c, 7 a's in the second place, third place by b, or c. =2*1*2=4
(iii) first place by a, b or c, second place by b or c, and 7 a's in the third place =3*2*1=6
So, the total number of strings with 7 consecutive a's =6+4+6=16
Case 2: string with 8 consecutive a's,
Consider the 8 a's a single character. So, we have to places to be filled up. Since, we need 8 consecutive a's we can not select the remaining one character as a, so we have two choices for the remaining character.
(i) 8 a's in the first place, and second place by b or c. =1*2=2
(ii) 8 a's in the second place, and first place by b or c. =2*1=2
So, the total number of strings with 8 consecutive a's =2+2=4
Case 3: strings with 9 consecutive a's.
There is only one possibility since the length of the string is 9. So, the number of string with 9 consecutive a's =1
Therefore, the total number of strings with at least 7 consecutive a's
=16+4+1
=21
F) The characters in the string "abababa" appear consecutively somewhere in the 9-character string. (So "ccabababa" would be such a 9-character string, but "cababcaba" would not.)
We will consider the stirng "abababa" as a single character. So, we will have 3 places to be filled up with one character as "abababa" and the remaining two characters from a, b, or c. We can select the two characters from a, b or c in C(3, 2)=3 ways. These two characters can be used along with "abababa" to form a 9 character string in 3!*2=12
That means, the total number of 9 character strings where "abababa" appear consecutively =12
(g) The string has exactly 2 a's or exactly 3 b's.
Case 1: string exactly has 2 a's
So, the remaining 7 characters should be choosen from b and c.
(i) When 2 a's are together, we can place the 7 characters from b or c in 7 places in 2^7 ways. These 7 characters make 8 places for the string with 2 a's and this 2 a's string can be placed at any of these 8 places in 8 ways. So, the total number of string when 2 a's are together is =8*2^7=1024
(ii) when 2 a's are not together, the 7 characters can be places in 2^7 ways, and there would 8 places for the 2 a's and these 2 a's can be placed at any of these 8 places in P(8, 2)/2!=56/2=28
So, the total the number of string where 2 a's are not together =28*2^7=3584
Therefore, the number of strings with exactly 2 a's =1024+3584=4608
Case 2: Strings have exactly 3 b's
Similary as in case 1, (i), when 3 b's are together, the number of strings=7*2^6=448
(ii) When 2 b's are together. We can place the 6 characters from a or c in 6 places, there would 7 places to be filled up by these two set of b's (1 b and 2 b's). We can place these b's in 7 places in P(7,2 )= 42 ways.
So, the total number of strings in thise case =42*2^6=2688
(iii) when no b's are together. So, 7 places can be filled up in P(7, 3)/3!=35, So, the total number of strings in this case =35*2^6=2240
Therefore, the total number of strings with exactly 3 b’s =448+2688+2240=5376
Case 3; When there are exactly 2 a's and 3 b's.
The 4 places should be filled by c, which can done in 1 way. These 3 c’s make 5 places which should be filled by a’s or b’s. So, 4 places can be filled by these strings in P(4, 2)= 12
The 4 places created by 3 c’s can be filled by 2 a’s and 3 b’s in P(4, 3)= 24
The 4 places created by 3 c’s can be filled by 2 a’s and 3 b’s in P(4, 4)= 24
The 4 places created by 3 c’s can be filled by 2 a’s and 3 b’s in P(4, 3)/2!= 24/2=12
The 4 places created by 3 c’s can be filled by 2 a’s and 3 b’s in P(4, 4)/2!= 24/2=12
The 4 places created by 3 c’s can be filled by 2 a’s and 3 b’s in P(5, 4)/(3!*2!)= 120/12=10
Therefore, the total number of strings with exactly 2 a’s and 3 b’s =12+24+24+12+12+10=94
Thus, the total number of strings with exactly 2 a’s or 3 b’s
=4608+5376-94
=9890