I would like to know the difference between "permutations with repetition" and "ways to choose $k$ elements from a set of $n$ elements if repetitions are allowed".
For instance:
- In a set $S$ of $k$ elements, the number of $n$-tuples over $S$ (words with repetition) is: $$k^n$$
- The number of ways to choose $k$ elements from a set of $n$ elements if repetitions are allowed is: $$\binom{n+k-1}{k}$$
Which is the difference among these two?
If I want to calculate the number of possible passwords of exactly 8 characters (uppercase 26 letters, lowercase 26 letters, and digits 10 numbers) which of the two formulas should I use and why?
Best Answer
Definitions
That, my friend, is all.
Permutations
When you think of permutations, the word that should come to mind, or should appear in the question is order. Indeed, in the case of a password, order matters, since $LFKJ$ is a different password from $FKLJ$.
In a set $S$ of $k$ elements, if one needs to make a word of $n$ letters, then order matters, since words may have the same letters and yet be different from each other, like TEA and ATE.
To argue why $k^n$ is the answer, imagine that you have to create a word with $n$ letters. First you create $n$ blanks, so the situation looks like this: $$ \underbrace{-~-~-~\ldots -~-~-}_{ \mbox{n blanks}} $$
Each blank, can be filled with any one of $k$ letters. So each blank has $k$ choices, and because there is no repetition, the blanks can be treated independently i.e. we can fill a blank without needing to look at the other blanks. Therefore, the answer is $k \times k\times ... \times k$, and there are $n$ blanks hence $k^n$.
Combinations
Now for combinations, the key word is set, or membership, if you like.
Take the example of choosing a committee of five people from a set of ten candidates. Indeed, it does not matter who was chosen first, who was chosen second etc., since the committee in the end, is the same. That is, the set of people in the committee matters, rather than the order in which they are chosen.
Thus, the context for combinations does not ring well with passwords, because here the set of letters in the password is not enough to determine the password itself : like with $LJKF$ and $FJLK$.
But sets don't have repeated elements , so where does that come in?
Now, as for combinations with repetitions, what does this even mean? After all we are speaking of a set, so randomly introducing a complexity in the form of repetitions does not make sense, does it?
Well, it does. Let us ask a question where there is an issue with respect to order, and with respect to number as well.
Indeed, this question seems initially to be one of permutations, since we have words involved, and these are in order.
However, the fact that we only care about the number of letters appearing, sort of removes the permutation angle from this.
For example, the words xyz and $yzx$ are the same because they contain the letters $x,y,z$ exactly once. However, $xxy$ and $xyy$ are not the same, because although they contain the same set of letters, the number of times each letter appears is different in both letters.
The idea of combinations with repetition is to be therefore taken in line with (any of) the following interpretations :
Calculation Time : Stars and Bars
The calculation is actually quite straightforward, we do it using a technique called Stars and Bars.
We go back to the problem of choosing $k$ elements from $n$ with repetitions. What we'll do is this : first write down $k$ stars like this : $$ \underbrace{*****....****}{\mbox{k stars}} $$
Now introduce exactly $n-1$ bars between these stars, so that the bars partition the stars into different groups. There are many ways to do this. How many? $$ **|****|******|*||**...|**|* $$ so now we have $n$ groups of stars, which are between bars. For example, in the division above, the first group has $2$ stars, while the second group has $4$ stars, the third has $6$, the fourth has $1$, the fifth has zero (this is possible!), and so on.
Now, consider a word that uses the first symbol two times, the second symbol four times, the third symbol six times, the fourth symbol once, never uses the fifth symbol, and so on. This word is a combination with repetition of length $k$ out of $n$ symbols.
Therefore, every combination with repetition corresponds to a pattern of $n-1$ bars between $k$ stars, and vice versa.
How many ways are there to put $n-1$ stars amongst $k$ bars? Well, imagine the situation where you have $n+k-1$ positions available to you. You fill exactly $k$ of these with stars, and the bars come in the rest of the places, giving such a diagram. Hence, the answer is $\binom{n+k-1}{k}$!
Your question
Your question is fairly straightforward. Indeed, order matters completely, and therefore it is a straightforward question of permutation with repetition. There are $26+26+10 = 62$ possible symbols, and eight positions to fill, so the answer better be $62^8$!
Conclusion
This post is to help you understand the difference between permutations, combinations and combinations with repetition, which is a fairly confusing concept. The key point is the various interpretations of combinations with repetition that rear their head every now and then. With practice you should be able to distinguish between these cases.