7
$\begingroup$

Here's a problem from my textbook:

On the island of Mumble, the Mumblian alphabet has only 5 letters, and every word in the Mumblian language has no more than three letters in it. How many words are possible if letters can be repeated?

I know we can break this problem into cases and the answer is $155$. But I want to know why my approach is incorrect.

My Approach: For the first letter, there are 5 ways, since we can only have letters. For the second and third letters, we have $6$ ways since we can also have no letters. So the final answer becomes $5*6*6$. Why am I getting the wrong answer?

$\endgroup$
1
  • 4
    $\begingroup$ You are counting "words" where the second letter is "blank" and so over-counting by $25$. $\endgroup$ Dec 17, 2019 at 4:42

5 Answers 5

18
$\begingroup$

If you don’t have a second letter in the word, you can’t have a third letter. Your approach didn’t account for that.

$\endgroup$
5
$\begingroup$

The problem with your approach is that the blank second letter is actually a different case than any of the five letters of the alphabet, because in that case the third letter must be blank. To fix your calculation you need to consider at least two cases.


There is a general approach that does not require doing cases every time.

Suppose there are $r$ letters, and the maximum word length is $n$. Then the number of possible words is the sum $$ \sum_{k=1}^n r^k = \frac{r^{n+1} - r}{r - 1}. $$

For example, with $r = 5$ and $n = 3,$ the number of words is $$ \frac{5^{3+1} - 5}{5 - 1} = \frac{625 - 5}{4} = 155. $$

$\endgroup$
2
  • $\begingroup$ I like your general formula (+1); I think you meant $n$ where you typed $L$ $\endgroup$ Dec 17, 2019 at 6:03
  • 1
    $\begingroup$ @J.W.Tanner Good catch on the $L.$ I changed my mind about notation when the formula was half written and forgot to replace that symbol. $\endgroup$
    – David K
    Dec 17, 2019 at 6:08
2
$\begingroup$

It's easier to count as follows:

  • There are 5 words with one letter.

  • There are 25 words with two letters ($5 \cdot 5$).

  • ...

Can you finish it?

$\endgroup$
2
  • 2
    $\begingroup$ I know how to do it by case. But I want to know why my approach is wrong. $\endgroup$ Dec 17, 2019 at 4:38
  • 2
    $\begingroup$ -1 for not reading the question. They clearly state that they know how to arrive at the correct answer, and want to know why the alternate method fails. $\endgroup$
    – Brady Gilg
    Dec 17, 2019 at 17:17
1
$\begingroup$

number of single letter words: 5

number of two letter words without repetition: 5*5

number of three letter words without repetition: 5*5*5

Taking the sum of these combinations = 155.

We can also instead expand our alphabet to include a null or space character. But this requires a small caveat: if a space is chosen in the first position, all characters after must be spaces, and the same is true in the second and third positions. So

5 + 5*5 + 5*5*5 = 5(1+5(1+5))

This is why your logic has issues.

$\endgroup$
0
$\begingroup$

One letter words

1 * 5 = 5

Two letter words

5 * 5

Three letter words

5 * 5 * 5

Here is a (not efficient but easy to follow code version I quickly did up to demonstrate)

static void Main(string[] args) {
        Console.WriteLine("Mumble");

        // 5 letters in alphabet - A,B,C,D,E
        // 3 letters max in a word
        // 1 letter min in a word
        // output total number of words

        string[] alphabet = new string[5] { "A", "B", "C", "D", "E" };

        int max = 3;
        int min = 1;

        int count = 0;

        //first letter
        for (int i = 0; i < alphabet.Length; i++) {
            Console.WriteLine(alphabet[i]);
            count++;
        }

        //first and second
        for (int i = 0; i < alphabet.Length; i++) {
            for (int x = 0; x < alphabet.Length; x++) {
                Console.WriteLine(alphabet[i] + alphabet[x]);
                count++;
            }
        }

        //all three
        for (int i = 0; i < alphabet.Length; i++) {
            for (int x = 0; x < alphabet.Length; x++) {
                for (int y = 0; y < alphabet.Length; y++) {
                    Console.WriteLine(alphabet[i] + alphabet[x] + alphabet[y]);
                    count++;
                }
            }
        }
            Console.WriteLine("Total: " + count);
            Console.Read();
        }
    }
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .