How to calculate the number of possible combinations with repetitions?

Question

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:

1. In a set $S$ of $k$ elements, the number of $n$-tuples over $S$ (words with repetition) is: $$k^n$$
2. 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?

Answer 1

Definitions

Permutation : Each of several possible ways in which objects can be ordered or arranged.

Combination : Each of several possible ways in which one makes a "collection" or "set" of objects chosen from a larger set.

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.

You have three letters $w,x,y$ and are to make repeated combinations of three letters. These are three letter words, in which only the number of times each letter appears matters. How many are there?

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 :

Number of $n$ letter words with repetition that can be formed from an $r$ letter alphabet, but where only the number of times each letter appears matters.

Number of ways to place $r$ identical objects in $n$ different jars.

Number of solutions to the equation $x_1 + ... + x_n = r$ where $x_i \geq 0$ for all $i$.

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.

Answer 2

Trying to explain by following example

X:{A,B,C,D,E}

1)How many ways you can form a 3 letter word from set X??

Since repetitions are allowed, the first letter can be selected in 5 ways, the second letter can also be selected in 5 ways and same for the third letter.

Hence $5 * 5 * 5 = 5^3$ = 125 ways

2)How many ways you can select 3 letters from set X given repetitions are allowed?

we are only concern with selecting the letters not arranging them

there are 3 cases formed

a) all letters are same(AAA,BBB,...) = 5C1 = 5

b) only 2 letters are same(AAB,AAC,ABB,...) = 5C1* 4C1 = 20

c) all letters are different (ABC,ABD,...) = 5C3 = 10

Total = 5 + 20 + 10 = 35

Alternative way to find this is using above formula= $\binom{5+3-1}{3}$ = 35

NOTE:

Suppose you also want to arrange the letters in the (2) question

a) all letters are same(AAA,BBB,...) = 5C1 = 5

they can be only arranged in 1 way = 5*1 = 5

b) only 2 letters are same(AAB,AAC,ABB,...) = 5C1* 4C1 = 20

they can be arranged in 3 ways[AAB,ABA,BAA] = 20 * 3 = 60

c) all letters are different (ABC,ABD,...) = 5C3 = 10

they can be arranged in 3! ways [ABC,ACB,BAC,BCA,CAB,CBA] = 10 *6 = 60

Total = 60+60+5= 125 which is same as the answer in (1)

Answer 3

For your 2., I'll recommend you read it as

$${(n-1)+k\choose k},$$

which means that you can use $n-1$ (identical) vertical bars to create $n$ regions, each of which represents a kind, then you put $k$ (identical) marks among these $n$ regions. To visualize it $$\begin{array}\\ A\ \color{blue}{\vert}\ B\ \color{blue}{\vert}\ C \\ V\ \color{blue}{\vert}\ VV\ \color{blue}{\vert}\ \cdot\ \ \ \ (1)\\ \cdot\ \color{blue}{\vert}\ VVV\ \color{blue}{\vert}\ \cdot\ \ \ (2),\\ \end{array}$$ which is to choose three objects among three kinds, $ABC$, and (1) represent a bag of one $A$ two $B$, while (2) of three $B$.

For your 1., it's actually comes from the observation $$\Large\underbrace{\_\ \_\ \_\ \_\ \_\ \dots\ \_}_{\textrm{a row of length}\ n.}\\ (\textrm{choose first})\cdot(\textrm{then second})\cdot(\textrm{third})\cdot\cdots\cdot(k\textrm{-th}), $$

since it's a row so the order matters, and for each position you have $k$ choice. Now ask yourself a password is permutation, or, combination? If your password is $123$ and I enter $321$ should I login into your account?

Answer 4

There are two things that matter. Can repetition (You can have two of the same item) only or not (every item must be different)? And whether the order matters (Is "ABC" a different word than "CAB"? Or are the trio of Tom, Dick, and Harry the same people as Harry, Tom and Dick?)

So there are four possible formulas:

1) Repetition is allowed and order does matter. So you can have the word "APPLE" and it different from "PEPLA".

In this case you have $k$ choices for the first letter, and $k$ choices for the second, and $k$ choices for the third.... and so on up to $k$ choices for the $n$th letter.

You multiply these choices together to get $k^n$ options.

This is very commonly used for choosing ways to make words or strings or, in your case, license plates. This the most fundamental combination there is.

2) You can not have repetition and order matters. You can not have "APPLE" but you can have "BREAK" which is different from "BRAKE".

In this case you have $k$ choices for the first item. Then you can choose anything for the second letter except what you chose for the first item. You can choose anything for the third item except what you chose for the first two. etc.

In the end you had $k*(k-1)*(k-2)*......*(k-(n-1))=k*(k-1)*(k-2)*.....*(k-n+1)=\frac{k*(k-1)*(k-1)*....*2*1}{(k-n)*(k-n-1)*....*2*1} = \frac {k!}{(k-n)!}$ ways of doing these.

An example where to do this might be appropriate is where you have $k$ items that most going into $n$ *specific positions. A classic a cliched example is you have $5$ people to hire for three positions. You have $5$ choices for the president, once you hire the president you are left with $4$ candidates for the treasurer, and one you hire the treasurer, you have $3$ candidates left for ear-wax recycler.

3) Repetition is not allowed and order does not matter.

This is the classic "pull $n$ items out of a bag of $k$ things". Obsviously you can't pull the same thing twice because once you pull it it's no longer an option. And it doesn't matter if you pull the rubber mouse and then the plush elephant or if you draw the plush elephant first and then the rubber mouse, because in the end you still have the same two things.

Another way of thinking of it: If you have a set of the letters $\{B,R,E,A,K\}$ this is the same set as the letters $\{B,R,A,K,E\}$. In other words... order does not matter.

This is called "choose $n$ from $k$" or "$k$ choose $n$" or ${k \choose n}$ and it is equal to $\frac {k!}{(k-n)!n!}$.

Why?

Well... If order did matter there would be $\frac {k!}{(k-n)!}$ ways to do this. But that means if you picked $A$ then $C$ than $B$ would be counted onece and then if you picked $C$ then $A$ then $B$ would be counted AGAIN. You would have counted the group $\{A,B,C\}$ a total of six times; you'd count it if you drew $A-B-C$, $A-C-B, B-A-C, B-C-A, C-A-B,C-B-A$.

So how many times did we count each option? Well, after we picked our $n$ items, how many ways are there to arrange them. If there are $M$ ways to order $n$ items We would have counted each of these $M$ ways when they should all be considered the same. So the number of ways is $\frac {k!}{(k-n)!M}$. So what is $M$?

Well of the $n$ letters there were $n$ we could have picked first. And after that there are $n-1$ we could have picked second. And so on. In the end there were $n*(n-1)*....*2*1 = n!$ choices.

So ${k\choose n} = \frac {k!}{(k-n)!n!}$.

4) Repetition is allowed and order does not matter.

If you have a bag of tiles. You pull a tile and the bag is replenished with another copy of the tile you pulled. You keep pulling and the bag is replenished. The you take you tiles and dump them onto the table. How many different sets of tiles might you have?

This one is the hardest to calculate.

.... and you know what.... астон вілла олоф мэллбэрг did a really good job in his/her answer in the stars and bars section.

No need for me to repeat it.