Permutations: When Objects Repeat

Monday's blog entry (10/22/2012), Factorials and Arrangements of Unique Objects dealt with permutations of arranging a group of objects where all the objects are unique. Today's blog entry looks at three situations where objects can be repeated.

All the Choices are Available all the Time

This is where you make permutations in which all the objects are available for each slot. For example, let's take a five digit zip code. There are five slots and for each slot the 10 digits are available: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.

For the first slot there are 10 choices. For each of the 10 choices, the second slot presents another 10 choices. For each of those 10 choices, the third slot presents another 10 choices. And so on.

The number of arrangements is: 10 × 10 × 10 × 10 × 10 = 100,000. There are 100,000 five-digit zip codes possible, 00000 to 99999.

Remember when calculating permutations, order matters. For our example, 11110, 11101, 11011, 10111, and 01111 are five different arrangements. The general rule is presented below.

---

Permutations where all the choices are available all the time = n^k

where
n = number of objects
k = number of slots

---

Objects Can Repeat, but with Some Restrictions

This is similar to the first situation in the way of calculating the number of permutations (arrangements).

Let's say we are on a very famous game show. One of it's mini games is played for a car valued anywhere from $20,000 to $59,999. We want to know how many possible prices for this game are possible.

Looking at the range from $20,000 to $59,999: we can see the choices for each of the five digits. The first digit must be a 2, 3, 4, or 5. The other four digits can be anything 0 through 9 (10 choices each).

The number of prices possible are 4 × 10 × 10 × 10 × 10 = 40,000.

So using a random guess, the contestant has a 1 in 40,000 choice in getting the price exactly right.

Another mini-game offers cars from $11,111 to $36,666 where the first digit is given to the contestant (1, 2, or 3) and the contestant tries to roll the other four digits using a single die. The die contains the numbers 1, 2, 3, 4, 5, and 6. Our task to find out how many prices are possible.

There are 3 choices for the first digit, and 6 choices for the other four digits.

The number of prices possible are 3 × 6 × 6 × 6 × 6 = 3,888.

This mini-game can be played up to 3,888 times before a price repeats.

---

Permutations where:
1) Different slots can have restrictions
2) Each choice is independent

P = (number of choices for slot 1) × (number of choices for slot 2) × ... × (number of choices for slot k)

---

Rearranging a Group of Objects where some of the Objects Repeat

In this situation we are finding the number of permutations of a group of objects, except some of the objects repeat.

Let's try to find the number of ways to arrange the letters in the word PHYSICS, removing any restriction that the arrangement has to make a sensible word (HYSSICP would count as arrangement).

In the word PHYSICS, there is 1 "P", 1 "H", 1 "Y", 2 "S"s, 1 "I", and 1 "C", for a total of 7 letters. PHYSICS counts as one permutation, regardless which "S" is used in each slot. We still have 7 letters, which can be arranged 7! = 5,040 ways, but have to account for the 2 "S"s.

The true number of ways to arrange the letters in the word PHYSICS is 2,520 ways.

7! / 2! = 5,040/2 = 2,520

Coincidentally, the calculation is really 7! / (1! × 1! × 1! × 2! × 1! × 1!). However, 1! = 1. Hence, 1! × 1! × 1! × 2! × 1! × 1! = 2!.

Let's take another example. Find the number of ways to arrange the letters in the "word" AAABB. In this example, there are 3 "A"s and 2 "B"s for a total of 5 letters.

If all the letters were unique, the number of ways is 5!. But we have to account for the repeats. Divide by 3! for the "A"s and 2! for the "B"s. The result is:

5! / (3! × 2!) = 120 / (6 × 2) = 10

There are only 10 ways to arrange the letters of the "word" AAABB. The ten are:

AAABB
AABAB
AABBA
ABABA
ABBAA

BABAA
BBAAA
ABBAA
AABBA
BAAAB

---

Finding the Number of Arrangements of Objects Where Some Objects Repeat

n! / ( (k_1)! × (k_2)! × ... × (k_m)! )

where:
n = the total number of objects, including repeated objects
m = the number of unique objects
k_1 = number of "k_1" objects
k_2 = number of "k_2" objects
and so on until...
k_m = number of "k_m" objects

The expression above is known as a multinomial coefficient.

---

I hope this day is well for each of you. Thank you for your comments and suggestions. Take care,

Eddie


Source:
Marcus, Daniel A. "Combinatorics: A Problem Orientated Approach" Mathematical Association of America, Washington DC. 1998.


This blog is property of Edward Shore, 2012.