Six letter words from "MONSTER"

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.


You have to add the 3 cases in which the word is made of one single letter, not subtract them!

$3^6$ is the total number of words made of 1, 2, or 3 letters.

$3 \cdot 2^6$ is the total number of words made of 1 or 2 letters, but you are counting each word made of 1 letter twice: once you have fixed a triple of letters {A,B,C}, you can get AAAAAA in two ways, one by selecting {A,B} as your two-letter subset, and one by selecting {A,C}.

So you have subtracted the words made of 1 letter twice, and you have to add them back.

This is an example of the inclusion-exclusion principle at work.

Indeed, $\binom{7}{3}(3^6-3\cdot 2^6+3) = 18900$.


(Note: I'm not sure this is the right answer since it disagrees with OP's calculation, so I'd appreciate it if someone would check the solution.)

The letters in the word MONSTER are all distinct, so the question is how many ways we can form a string of $6$ characters with each character chosen from these $7$ choices, under the restriction that there are three different letters. To count this, we can choose which three letters they are first: a factor of $\binom73$. Once we've chosen the letters, we need to look at how to arrange them.

We can do so by cases: call the three letters $A,B,C$, then either there are $4$ of one letter and $1$ of the other two, or $3$ of one letter and $2$ and $1$ respectively of the other two, or $2$ of each letter. In the first case there are $\binom{6}{4}\binom{3}{1}\binom{2}{1}$ ways, in the second there are $\binom{6}{3}\binom{3}{1}\binom{3}{1}\binom{2}{1}$ ways, and in the third there are $\binom{6}{2}\binom{4}{2}\binom{3}{1}\binom{2}{1}$ ways. So the answer is $$\binom73\left[\binom{6}{4}\binom{3}{1}\binom{2}{1}+\binom{6}{3}\binom{3}{1}\binom{3}{1}\binom{2}{1}+\binom{6}{2}\binom{4}{2}\binom{3}{1}\binom{2}{1}\right]=34650.$$


Edit: $18900$ is correct, as explained in Matthew Daly's answer. I think I've figured out where I went wrong above: in counting the third case, the quantity $\binom62\binom42$ was intended to be the number of ways to partition a set of $6$ items into three $2$-member subsets, the logic being that we first choose one such subset and then choose another in the remaining $4$ items. That's wrong however, as it counts each possibility $3!=6$ times (according to the order in which the partitions are chosen). So the correct answer should actually be $$\binom73\left[\binom{6}{4}\binom{3}{1}\binom{2}{1}+\binom{6}{3}\binom{3}{1}\binom{3}{1}\binom{2}{1}+\frac1{3!}\binom{6}{2}\binom{4}{2}\binom{3}{1}\binom{2}{1}\right]=18900.$$