1
$\begingroup$

I have a question about this problem that I am trying to figure out:

A string of letters is called a palindrome, if reading the string from left to right gives the same result as reading the string from right to left. For example, madam and racecar are palindromes. Recall that there are five vowels in the English alphabet: a, e, i, o, and u.

In this question, we consider strings consisting of 28 characters, with each character being a lowercase letter. Determine the number of such strings that
(i) start and end with the same letter, or
(ii) are palindromes, or
(iii) contain vowels only.

My answer so far:

$A = 26^{27}$,

$B = 26^{14}$,

$C = 5^{28}$

My question is, would I have to use a sum rule here or inclusion-exclusion rule? I am not sure about which method to use here. Any help would be appreciated.

$\endgroup$
1
  • $\begingroup$ Why would there be a sum or inclusion-exclusion? $\endgroup$ – David K Oct 4 '17 at 0:35
2
$\begingroup$

So, if I read the section that was boldface, now just a roman-numbered list, as meaning that if any of the given conditions are satisfied, then a string qualifies for the count, then you do indeed need to eliminate some double-counting, because these categories overlap.

However note that palindromes are a subset of words that start and end with the same letter, so in principle we don't need to count those separately at all; (ii) is completely contained within (i). So the only overlap that needs accounting for is: (iv) words consisting of vowels only that start and end with the same letter (which will be result D in your scheme).

Then your overall total is A + C - D.

$\endgroup$
4
  • $\begingroup$ would you mind elaborating a bit more for (iv)? - words that consists of voyels only, which I called C = 5^28. Just wanted to make sure if we are still talking about C. $\endgroup$ – Istiak Khan Oct 4 '17 at 0:52
  • $\begingroup$ No, your C corresponds to item (iii). (iv) is a new, smaller set that has the extra restriction of having the same start and end letter. $\endgroup$ – Joffan Oct 4 '17 at 0:55
  • $\begingroup$ I see, so D = 5^27. Thanks :) $\endgroup$ – Istiak Khan Oct 4 '17 at 0:58
  • $\begingroup$ And, for clarity, we're subtracting D because it's contained in both A and C so it's been counted twice if we just add them up. $\endgroup$ – Joffan Oct 4 '17 at 1:13
1
$\begingroup$

No, your answers are fine. You are just using the multiplication principle, noting how many choices you have at each step and how many steps there are. Inclusion-exclusion comes in if you can count some items more than once, but you have avoided that.

$\endgroup$
2
  • $\begingroup$ I assumed its one of those rules I mentioned before since A U B U C Would that be then ABC = (26^27)*(26^14)*(5^28)? I am a bit confused about this chapter. My teacher is not very clear on when to use what rule. $\endgroup$ – Istiak Khan Oct 4 '17 at 0:41
  • 1
    $\begingroup$ I think the question is determine the number of $28$-character strings of lower case English letters that start and end with the same letter or are palindromes or contain vowels only. $\endgroup$ – N. F. Taussig Oct 4 '17 at 0:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.