I need help with question 14 that are either odd or the square of an integer. 12

Question

I need help with question 14
that are either odd or the square of an integer. 12. Find the number of positive integers not exceeding 1000 that are either the square or the cube of an integer. 13. How many bit strings of length eight do not contain six consecutive Os? *14. How many permutations of the 26 letters of the English alphabet do not contain any of the strings fish, rat or bird? 15. How many permutations of the 10 digits either begin with the 3 digits 987, contain the digits 45 in the fifth and sixth positions, or end with the 3 digits 123? 16. How many elements are in the union of four sets if each of the sets has 100 elements, each pair of the sets shares 50 elements, each three of the sets share 25 elements, and there are 5 elements in all four sets? 17. How many elements are in the union of four sets if the sets have 50, 60, 70, and 80 elements, respectively, each pair of the sets has 5 elements in common, each triple of

Explanation / Answer

This is a problem concerning the inclusion-exclusion principle.

There are 26! total permutations of the 26 letters of the alphabet. We must subtract off the permutations that contain each of the forbidden words, then add back the permutations that contain two of the forbidden words, and finally subtract off the permutations that contain all three forbidden words.

There are 23! permutations that contain "fish". (Imagine the word "fish" as a single "letter" of the alphabet along with the other 22 letters of the alphabet individually; there are now 23 "letters" whose permutations we must count).

There are 24! permutations that contain "rat". (Here "rat" is a single "letter" with 23 other letters individually)

There are 23! permutations that contain "bird".

Now there are 21! permutations that contain both "fish" and "rat" (Each of "fish" and "rat" is seen as a "letter", along with the 19 other letters individually, for 21 total "letters").

There are no permutations that contain both "fish" and "bird", and no permutations that contain both "bird" and "rat", since these pairs of words overlap in a letter that makes it impossible for an alphabetic permutation to contain both words. Similarly, there are no permutations that contain all three words.

Thus, by the inclusion-exclusion principle, the number of permutations that contain none of the words "fish," "bird," and "rat" is

26! - (23! + 24! + 23!) + 21!

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.