A six letter word is formed using the letters of the word "MONSTER", with or without repetition. The number of words that contain exactly three different letters is?
I tried computing the possible number of words using Python, keeping the conditions in mind, and got an answer of around $18900$. But while thinking about it by theoretical methods, I first choose $3$ letters from $7$ in $\binom73$ ways, and then arranged those $3$ in $6$ places in $3^6$ ways, and then removed the $3$ cases where the whole word is made up of one letter, along with those $3(2^6)$ cases where the word was made up of only two letters among the three chosen.
Sorry if it's confusing, but any kind of help would be really appreciated.
Thank you.
Any helpful resources for discrete mathematics would also be appreciated.
Best Answer
I'm writing this without looking at anyone else's number or solution technique first. Combinatorics is a bit of an art, but the downside is that too much artfulness leads to different solutions. My style is to find solutions that would just as well if we were asked to find twenty letter words that used exactly nine letters from the word UNCOPYRIGHTABLE. There is a certain freedom to thinking "Three, six, and seven are relatively small numbers, so let's brute force this!" and too much freedom is dangerous. ^_^
First, let's think about the number of ways to make a six-letter word out of the letters ABC, where each letter is used at least once. This is the number of surjections from a set with six elements to a set with three elements. By the twelvefold way, this is $3!\{{6\atop3}\}=6\cdot90=540$. (The quantity in the bracket is a Strirling number of the second kind.)
In fact, we actually want our words to be made from three letters of the word MONSTER. Those three letters can be chosen in $\binom73=35$ ways, giving us a total of $35\cdot540=18900$ possibilities.