Learn

In this exercise, we will explore how to enumerate elements of a multiset (a set that contains elements that are not necessarily distinct). Consider the problem of having to determine the number of permutations of the letters in the word CODE. From previous exercises, we know the number of permutations is 4!. What about the word CODEC? Claiming the answer is 5!, as you did for the word CODE, would be incorrect. This is because the letter C appears more than once. If we write the word like this C1ODEC2, the following permutation of the word exists: C2ODEC1 which is the same as the original word. Since both C’s are identical, it is irrelevant which one is in which position. Therefore we must scale the number of permutations down. To do this, we consider that the order of the two C’s, in whichever spot they appear, does not matter. Sounds familiar? That’s right, we scale down by 2!. So the number of permutations of the word CODEC is:

5!2!=60\frac{5!}{2!} = 60

If we were permuting a word with more than one repeated character, we would further scale down the permutations by the count of the other repeated letters. Generally speaking, the number of permutations of a multiset is:

P(n;r1,r2,,rk)=n!r1!r2!rk!P(n; r_1, r_2, \ldots, r_k) = \frac{n!}{r_1! r_2! \ldots r_k!}

Where n is the total size of the multiset and each of rk‘s represents the count of each element.

Another way of computing this is to “choose” a spot for each element. Consider the word GOOGLE, how many permutations of this word can we have? We “choose” two spots for the G’s, “and” we “choose” two of the remaining spots for the O’s, “and” we “choose” one remaining spot each for the L and the E:

P(6;2,2,1,1)=(62)(622)(421)(11)=180P(6;2,2,1,1)= \binom{6}{2} \binom{6-2}{2} \binom{4-2}{1} \binom{1}{1} = 180

Formally:

P(n;r1,r2,r3,rk)=(nr1)(nr1r2)(nr1rk1rk)P(n; r_1, r_2, r_3 \ldots, r_k)= \binom{n}{r_1} \binom{n-r_1}{r_2} \ldots \binom{n - r_1 - \ldots - r_{k-1}}{r_k}

Instructions

1.

If the repeated letters can be treated as distinct, how many permutations are there for the word COMBINATORICS? Store your answer in the permutation_1 variable.

2.

Can you correct the previous calculation to find the actual number of permutations of the word COMBINATORICS? Store your answer in the permutation_2 variable.

3.

Can you find the number of permutations for the word COMBINATORICS by using the formula for combination? Store your answer in the permutation_3 variable. Use the result to verify your answer to the previous question.

C(n,r)=n!r!(nr)!C(n,r) = \frac{n!}{r!(n-r)!}

Remember the following identities:

C(n,n)=1C(n,n) = 1
C(n,1)=nC(n,1) = n

Take this course for free

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?