1
$\begingroup$

Let's say that we have an alphabet with two letters $A, B$.

We want to words with length = 4. This means that possible words are $2^{4}$.

Now if we want to make words with length = 300 and an alphabet of 100 letters, can we say that possible words are $100^{300}$?

  • 2
    Now the answer is simply yes.2011-11-08

2 Answers 2

1

Edited to correct the terminalogy (thanks to @MaX)

Yes. This a basic rule of combinatorics, known as "permutations with repetition".

Let us consider we have to fill these $n$ rooms (in your case $n$= 300 is the length of word). We are allowed to fill any of the rooms by an item from (say) $r$ items (in your case $r=100$ is the number of available letters).

$\begin{array}{|c|c|c|c|}\hline\\&&\vdots&&&&&\vdots&&& \end{array}$ We can do it in the following way: the first room can be filled in in exactly $r$ way. For each of these ways, the second room can also be filled in $r$ ways...and so on. So the total number of ways to fill the rooms is $r\times r\times\cdots\times r$ ($n$ times multiplication)=$r^n$.

  • 0
    :-)$\space \space$2011-11-08
1

I would say yes.

In case of the four letter word with two letter alphabet, we have a choice of $2$ letter for each letter of the 4 letter word, and then consistent to rule of product we get $2\times 2 \times 2\times 2= 2^4$.

likewise...

Note we are allowing repetition of letters of the alphabet in each case.


EDIT $1$:

This problem is the reminiscent of the problem of finding the number of possible way of distributing $r$ distinct items into $n$ distinct groups where some groups could be empty.


EDIT $2$:

Other ways to model this same problem:

$(1)$ Number of ways of drawing a sample of $r$ objects from a set of $n$ distinct object when order of drawing is important and we allow repetition.

$(2)$ Distributing $r$ distinct balls into $n$ distinct cells with any number of balls per cell.

However,the answer in all these cases is $n^r$, which is again consistent to the rule of product.