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

Words avoiding letters

#IE#words#letters

Statement

Count words of length 44 over {a,b,c}\{a,b,c\} avoiding the letter aa.

Hint

Direct count: 24=162^4=16.

With IE. Total 34=813^4=81, subtract words with at least one aa.

Show solutionHide solution

Solution

Direct. Words over {b,c}\{b,c\}: 24=162^4=16.

IE check. ∣A1∣|A_1| (a in position 1): 33=273^3=27; ∣A1∩A2∣|A_1\cap A_2|: 32=93^2=9; etc. ∣Ai∣=27|A_i|=27, ∣Ai∩Aj∣=9|A_i\cap A_j|=9, ∣Ai∩Aj∩Ak∣=3|A_i\cap A_j\cap A_k|=3, ∣A1∩⋯∩A4∣=1|A_1\cap\cdots\cap A_4|=1.

IE: 81−4⋅27+6⋅9−4⋅3+1=81−108+54−12+1=1681-4\cdot27+6\cdot9-4\cdot3+1=81-108+54-12+1=16. ✓

Conclusion. 1616 words.