When given some word with size $n$ which could have any amount of repeating letters, how many distinct $k$ letter words can be made from it?
Example: given the string $aaaaaaaabbbbbbbbcccccccccdddddeeeeef$ (8 $a$'s, 8 $b$'s, 9 $c$'s, 5 $d$'s and 1 $f$), how many distinct $4$ letter strings can be made?
In your example, you can either ignore the $f$ and form one of the $4^4$ words of length $4$ on the alphabet $\{a,b,c,d\}$ or choose a position for the unique $f$ ($4$ possibilities) and insert it in a word of length $3$ on the alphabet $\{a,b,c,d\}$ ($4^3$ possibilities). Altogether, you get $4^4 + 4\cdot 4^3 = 512$ possibilities.