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}$?

  • 1
    The other way around.2011-11-08
  • 0
    @Rasmus fixed now2011-11-08
  • 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
    This is not [combination with repetition](http://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition).2011-11-08
  • 0
    @Max, Thanks for the correction.2011-11-08
  • 0
    Well, it's combination with repetition and order.2011-11-08
  • 0
    Glad to help.Please edit accordingly so that I could remove the -1 :-)2011-11-08
  • 0
    @Rasmus:I still have doubts on the use of the term "combination" here.2011-11-08
  • 0
    @MaX: No problem with -1 :) When I was editing I even did not see this comment.2011-11-08
  • 0
    Removed -1; but "permutation with repetition" generally means "arrangements of similar objects",this problem could be described in the following ways: (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, I have mentioned other cases in my answer.However the answer in all cases is $n^r$.2011-11-08
  • 0
    Yes, now your answer looks nice and very complete.2011-11-08
  • 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.