Maths WorkshopMaths problems with full solutions
Exercise 1728Combinatorics › Inclusion-exclusionL1Added 3 Nov 2026

Avoiding two letters

#IE#words#avoiding letters

Statement

Count words of length 44 over {a,b,c}\{a,b,c\} with no aa AND no bb.

Hint

Direct: only {c}\{c\} allowed.

Show solutionHide solution

Solution

Direct. Words using only cc: 14=11^4=1 word, cccccccc.

IE check. ∣A∪B∣|A\cup B| where AA=at least one aa, BB=at least one bb. ∣A∣=81−24=65|A|=81-2^4=65, ∣B∣=65|B|=65, ∣A∩B∣=81−1=80|A\cap B|=81-1=80 (all words with at least one aa or bb = total minus cccccccc). ∣A∪B∣=65+65−80=50|A\cup B|=65+65-80=50. Avoid both: 81−50=3181-50=31? That gives 31≠131\neq1.

Hmm, that's wrong. Let me redo: ∣A∩B∣|A\cap B| = words with both aa and bb (not just at least one of them). ∣A∩B∣|A\cap B| via IE: ∣A∣+∣B∣−∣A∪B∣|A|+|B|-|A\cup B| is circular.

Direct: total words with both aa and bb: (4?)\binom{4}{?}... easier: total 8181, minus words with no aa (16), minus no bb (16), plus no aa and no bb (1): 81−16−16+1=5081-16-16+1=50. So ∣A∩B∣=50−?|A\cap B|=50-?... wait, that IS ∣A∪B∣|A\cup B|. So ∣A∪B∣=50|A\cup B|=50. Then words with no aa and no bb: 81−50=3181-50=31. But that should be words using only cc: 11 word. Contradiction!

Ah, my IE is off: words with at least one aa OR at least one bb = 81 - (words with no aa AND no bb) = 81 - 1 = 80. So ∣A∪B∣=80|A\cup B|=80. Then avoid both aa and bb = words with no aa AND no bb = 1.

Conclusion. 11 word (cccc).

Lesson. IE must be applied carefully to the right sets.