8
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I love that idea of freedom, I was tempted to think in a more general way but I suppose this felt enough of a handful to me. Thank you for your simple explanation, I have previously done Stirling numbers, I'll keep it in mind to broaden my thinking in such ways. And thank you for your kind formatting of my question. $\endgroup$ – PiToThei Dec 15 '19 at 9:36
  • 1
    $\begingroup$ This is the right way to think about the problem. (+1) $\endgroup$ – YiFan Dec 15 '19 at 10:12
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I did realize this a bit ago, had to think for a while to realize the bit I was getting wrong. Thank you very much! $\endgroup$ – PiToThei Dec 16 '19 at 10:29
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for the answer, I appreciate it, but I'm not quite sure about the second part where you apply combinations to the three selected letters. That's where our calculation differs. I am not able to understand the point of selecting 4 letters from a 6 letter word, which is made up of repetitions of 3 letters. I hope you get what I'm trying to say. Appreciate it though. Do let me know your thoughts if you can. $\endgroup$ – PiToThei Dec 15 '19 at 8:02
  • $\begingroup$ Plus, I linked it to the process of consecutive tosses. Like, with two letters, H and T, we get n consecutive tosses as 2^n. So with 3 letters, 3^n. What do you think? $\endgroup$ – PiToThei Dec 15 '19 at 8:04
  • 1
    $\begingroup$ @PiToThei not sure how this is related to consecutive tosses; but I think I've figured out where I went wrong, do have a look at the edited answer. $\endgroup$ – YiFan Dec 15 '19 at 10:26
  • $\begingroup$ I'm glad you could get the answer too. Thanks for the effort! $\endgroup$ – PiToThei Dec 15 '19 at 10:47
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I'm sorry I couldn't totally understand the code as I've not learnt C, but I think I do understand what you meant by it. Kind of, lol. Not yet well versed in computer programming, tbh. But I really appreciate that you took the time. And well, I thought using a bit of brute force, so to speak, could be a fun little brainstorm session for me. Thank you very much! $\endgroup$ – PiToThei Dec 15 '19 at 9:40
  • 1
    $\begingroup$ Thanks for confirming that I was wrong :) But seriously, this helped me in discovering my mistake. (+1) $\endgroup$ – YiFan Dec 15 '19 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.