Six letter words from "MONSTER"

Question

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.

Answer 1

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.

Answer 2

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$.

Answer 3

(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.$$

Answer 4

Brute force is indeed rarely a solution, but when two answers differ, and the complexity is reasonable, it can prove one wrong :-)

The C code below counts in base 7 (number of letters, in the "word" array count[6]) and enumerates the number of cases where we have 4 kinds of letters that are not used (i.e. when the count of each letter (array a[7]) has 4 zeroes in it).

 int j,ok = 0,total = 0,go = 1; // 'ok' is number of correct matches
 int count[6] = { 0 };          // "words", as 6 digits from 0 to 6

 while ( go ) {
      total++;                 // total cases, should be 7^6
      int a[7] = { 0 };        // Counter in base 7
      for(int j=0 ; j<6 ; j++) {
            a[ count[j] ]++;   // Inc digit at count[j] in a
      }
      int zero = 0;            // Tautology :-)
      for(j=0 ; j<7 ; j++) {
            if (a[j] == 0) zero++; // Count digits of 0 count
      }
      if (zero == 4) ok++; // Need 4 zeroes...

      // Count in base 7 (number is reverse but that's not important!)
      for(j=0 ; j<6 ; j++) {
            if (++count[j] < 7) break; // Leave this loop if in base
            if (j == 5) go = 0;        // 7^6 reached, leave main loop
            count[j] = 0;
      }
 }
 printf("Total: %d, matches: %d\n", total, ok);

And the winner is

Total: $\boxed{117649}$, matches: $\color{blue}{\boxed{18900}}$

The 'UNCOPYRIGHTABLE' mentioned above (maybe below, but more likely above) should be solvable on a decent computer thanks to some optimisations...