Permutations and combinations

This is the second post in a series of posts on combinatorial analysis. The first post is on the multiplication principle. This post introduces permutations and combinations.

The starting point of the discussion on counting is the idea that if one event can occur in M ways and another event can occur, independent of the first event, in N ways, then the two events together can occur in M \times N ways. This idea is often called the multiplication principle and is introduced in this previous post.

___________________________________________________________________________

Factorial

Consider the eight letters A, B, C, D, E, F, G and H. How many ways can we order the 8 letters? The following shows two ordered arrangements.

    A-B-C-D-E-F-G-H

    C-B-F-A-D-G-H-E

The multiplication principle can help us determine the number of all arrangements of 8 letters. We are trying to fill 8 objects into 8 positions. There are 8 choices for the first position. After the first letter is fixed, there are 7 letters for the second position. Continue with this approach, there will be only one letter left for the eighth position. In total, there are 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40,320 ordered arrangements of 8 letters. A convenient notation for the answer is 8!, read 8 factorial. It is simply the product of the integers from 8 down to 1.

In general, if n is a positive integer, n!, read n factorial, is the product of all the integers from n down to 1.

n!=n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1

For the above definition of n! to make sense, n is a positive integer. We define 0! = 1 to make certain formulas easy to calculate.

According to the above example, there are 8! many different ordered arrangements of 8 distinct objects (objects that are distinguishable from one another). Any ordered arrangement such as C-B-F-A-D-G-H-E is called a permutation of the 8 letters. In general, a permutation is an ordered arrangement of a set of objects that are distinguishable from one another. From the above example of 8 letters, we have the following observation.

    The total number of permutations of n distinct objects is n!.

The G8 summit is an annual meeting between leaders from eight of the most powerful countries in the world. There would be 8! = 40,320 different ways to line up the 8 leaders for a group photo. A permutation can be viewed as ranking. In a soccer league of 8 teams, there would be 8! = 40,320 different possible rankings.

The factorial grows very rapidly. In ordering 9 objects, there are 9! = 362,880 permutations.

    10! = 3,628,800
    11! = 39,916,800
    12! = 479,001,600
    15! = 1,307,674,368,000
    17! = 355,687,428,096,000
    20! = 2,432,902,008,176,640,000

Thus the number of possible rankings of 12 job applicants is over 479 millions. The number of possible rankings of 20 job applicants would be a staggering number, over 2.4 quintillions! A quintillion is 10 raised to 18. In contrast, a trillion is 10 raised to 12.

Example 1
Suppose that you have 12 books with 4 of them being novels, 4 of them being math books, 3 of them being science books and one being a history book. You want to place the books on the same level in a bookshelf. If the books are put in any order, then there would be 12! = 479,001,600 different placements of books. In how many ways can the books be placed in the bookshelf if all books of the same subject are to be together?

The last question makes use of the multiplication principle in a subtle way. Consider the books arranged by subjects in this order: novel-math-science-history. By the multiplication principle, there are 4! x 4! x 3! x 1! = 24 x 24 x 6 x 1 = 3,456 many ordered arrangements. This is just for one specific way of the order of the 4 subjects – novel-math-science-history. There are 4! = 24 ways of order 4 subjects. Then the answer to the last question is 24 x 3,456 = 82,944. \square

___________________________________________________________________________

Permutation

Sometimes we do not order the entire set of n objects. We only order a subset of the n objects. Using the above example of 8 letters A, B, C, D, E, F, G and H, in how many ways can we arrange three letters from these 8 letters? The multiplication principle is at work here. We are attempting to fill 3 positions using 8 letters at our disposal. The first position has 8 choices. The second position has 7 choices and the third position has 6 choices. There are a total of 8 x 7 x 6 = 336 ordered arrangements. Three examples are A-B-C, G-A-H and E-B-F. Any one of these 336 ordered arranged is called 3-permutation of 8 letters. We can also call it a permutation of 8 letters taken 3 at a time.

Example 2
To put the 8 letters in a context, suppose that a math club has 8 students – Abby, Beth, Chloe, Diane, Edward, Frank, George and Henry. In how many ways can we choose 3 students to fill three positions of President, Vice President and Treasurer of the math club? Based on the preceding discussion, the answer is 8 x 7 x 6 = 336. The following is a presentation of the calculation that gives the hint for a formula.

    \displaystyle 8 \times 7 \times 6=\frac{8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{5 \times 4 \times 3 \times 2 \times 1}=\frac{8!}{5!}=\frac{8!}{(8-3)!}

In general, any ordered arrangement of k objects from a set of n objects is called a k-permutation of n objects. We can also call any such ordered arrangement a permutation of n objects taken k at a time. Here, we attempt to fill k positions with objects selected from n objects with k \le n. How many permutations of n objects taken k at a time? There are

    n \times (n-1) \times (n-2) \times \cdots \times (n-(k-1))

many different permutations of n objects taken k at a time. Some common notations for this number are P(n,k) or P_{n,k}. According to the hint in Example 2, the following is a formula for P(n,k).

\displaystyle P(n,k)=\frac{n!}{(n-k)!} is the number of permutations of n objects taken k at a time.

Note that P(n,n) is simply n!.

Example 3
In evaluating 20 job applicants, there are 20! many possible rankings, which is over 2 quintillions as discussed above. A more sensible goal is to narrow the list to the top 5 candidates. The number of permutations of 20 candidates taken 5 at a time is

    \displaystyle P(20,5)=\frac{20!}{15!}=20 \times 19 \times 18 \times 17 \times 16=\text{1,860,480}

Example 4
Suppose that the psychology club at a university has 12 members in the lower division (consisting of freshmen and sophomores), 10 members in the upper division (consisting of juniors and seniors). Four awards (achievements in terms of overall grade, leadership potential, volunteerism, and public speaking) are given to each group. What is the total number of different outcomes if

  • a student can receive more than one award,
  • a student can receive only one award.

If a student can be awarded more than once, then there are 12^4 ways of giving out awards in the lower division and 10^4 ways in the upper division, leading to the following answer.

    \displaystyle 12^4 \times 10^4 = \text{207,360,000}

If a student can only be awarded once, then the following is the answer.

    \displaystyle P(12,4) \times P(10,4) =(12 \times 11 \times 10 \times 9) \times (10 \times 9 \times 8 \times 7)= \text{59,875,200}

___________________________________________________________________________

When Some Objects are Indistinguishable

In calculating the number of permutations, the objects are assumed to be distinct. We now look at the situation where objects are separated into groups of indistinguishable objects. The goal is still finding the number of ordered arrangements. The number of permutations as calculated above would be an over count. The answer is obtained by dividing the inflated count by the amount of over counting.

Example 5
How many different letter arrangements can be formed from the letters in the word BANANA?

There are 6 letters in BANANA. Three of the letters are indistinguishable (A) and two of them are indistinguishable (N). If all the letters are distinguishable, then there are 6! permutations. But 6! = 720 over counts. By how many?

Pretend all the letters are distinguishable. Take the arrangement A_1 \ A_2 \ A_3 \ B \ N_1 \ N_2. Now permute the A’s and the N’s. Doing so should result in 3! x 2! = 12 permutations.

    A_1 \ A_2 \ A_3 \ B \ N_1 \ N_2
    A_1 \ A_3 \ A_2 \ B \ N_1 \ N_2
    A_2 \ A_1 \ A_3 \ B \ N_1 \ N_2
    A_2 \ A_3 \ A_1 \ B \ N_1 \ N_2
    A_3 \ A_1 \ A_2 \ B \ N_1 \ N_2
    A_3 \ A_2 \ A_1 \ B \ N_1 \ N_2

    A_1 \ A_2 \ A_3 \ B \ N_2 \ N_1
    A_1 \ A_3 \ A_2 \ B \ N_2 \ N_1
    A_2 \ A_1 \ A_3 \ B \ N_2 \ N_1
    A_2 \ A_3 \ A_1 \ B \ N_2 \ N_1
    A_3 \ A_1 \ A_2 \ B \ N_2 \ N_1
    A_3 \ A_2 \ A_1 \ B \ N_2 \ N_1

But in reality, all of the 12 permutations are the same: A \ A \ A \ B \ N \ N. So each unique permutation appears 12 times in the count 6!. Thus the correct count is

    \displaystyle \frac{6!}{3! \ 2! \ 1!}=60

In general, \displaystyle \frac{n!}{m_1! \ m_2! \ \cdots \ m_k!} is the number of permutations of n objects, of which m_1 are alike, m_2 are alike, …, m_k are alike, where m_1+\cdots+m_k=n.

___________________________________________________________________________

Combination

In all the above instances of counting, the focus is to find all ordered arrangements (or permutations) of a set of objects. We now focus on the different subsets of k elements that can be chosen from a set of n objects. In this setting, the goal is not to count ordered arrangements. The goal is to count the number of subsets of a certain size. For example, let’s say you want to buy a 2-scoop ice cream cone of different flavors chosen from 3 flavors – Chocolate (C), Strawberry (S) and Vanilla (V). Suppose you do not care which flavor is on top and which one is at the bottom. The different subsets of size 2 would be: CS, CV, and SV. Here, CS is not an ordered arrangement. It just means that the two chosen flavors are chocolate and strawberry. If order matters, then there would be six outcomes – CS, SC, CV, VC, SV, and VS. So the approach is to find the number of permutations (an over count) and then divide the amount of over count.

Example 6
Suppose that a math club has 8 students – Abby, Beth, Chloe, Diane, Edward, Frank, George and Henry. In how many ways can we choose three students to form a committee of three?

The number of permutations of three students is 8 x 7 x 6 = 336. This count is inflated since there are many repeats reflected in this count. For example, if the chosen students are Abby, Beth and Chloe, then there are 3! = 6 ways to order these three students – ABC, ACB, BAC, BCA, CAB and CBA. So each set of three students is reflected 6 times in the inflated count of 336. So the answer is 336 / 6 = 56. Thus there are 56 possible groups of three students when three students are chosen from 8 students. The following calculation makes the formula clear.

    \displaystyle \frac{8 \times 7 \times 6}{3!}=\frac{8 \times 7 \times 6 \times 5!}{3! \ 5!}=\frac{8!}{3! \ 5!}

In general, \displaystyle \binom{n}{k}=\frac{n!}{k! \ (n-k)!} is the number of different groups of size k that could be chosen from a set of n distinct objects where k=0,1,2,\cdots,n.

The number \binom{n}{k} is called a binomial coefficient and is pronounced “n choose k.” Other notations for \binom{n}{k} are _nC_k, C_{n,k} and C(n,k).

Example 7
A committee of five is to be chosen from a group of 11 people consisting of 5 men and 6 women.

  • How many different committees of five people can be formed?
  • How many different committees consisting of 2 men and 3 women can be formed?
  • How many different committees of five consisting of either 2 men or 2 women?

The number of possible committees of five would be \binom{11}{5}=462. For the second problem, note that there are \binom{5}{2}=10 possible groups of 2 men and there are \binom{6}{3}=20 groups of 3 women. By the multiplication principle, there are 10 x 20 = 200 different groups of 5 people consisting of 2 men and 3 women.

For the third problem, there are two cases: a committee of 2 men and 3 women or a committee of 2 women and 3 men. The answer is the sum of these two cases. Thus the answer is

    \displaystyle \binom{5}{2} \times \binom{6}{3}+\binom{5}{3} \times \binom{6}{2}=10 \times 20+10 \times 15=350

___________________________________________________________________________

More Examples

We present a few more examples to demonstrate the ideas discussed here. Exercises are given at the end.

Example 8
A child plays with a set of 12 blocks, 4 of which are red, 4 of which are black, 3 of which are white and one of which is yellow. In how many ways can these blocks be arranged in a row? In how many ways can these blocks be arranged in a row in such a way that all blocks of the same color are together?

Note the similarity with Example 1. Both problems concern with a collection of 12 objects that can be separated into 4 sub groups. In Example 1, the objects in each sub group are distinguishable while the objects in this example are indistinguishable in each sub group. As a result, the formula discussed in the section “When Some Objects are Indistinguishable” would apply. Here’s the number of different ways to order the blocks.

    \displaystyle \frac{12!}{4! \ 4! \ 3! \ 1!}=\text{138,600}

For the second question, the answer would be 4! = 24. Unlike Example 1, we do not need to order the blocks within the same color since they are indistinguishable. \square

Example 9
The tennis team in School A has 12 players and the tennis team in School B has 14 players. If 5 players are selected from each team and then paired off for a tennis game, how many results are possible?

There are \binom{12}{5}=792 ways of choosing 5 players from Team A. There are \binom{14}{5}=2002 ways of choosing 5 players from Team B. There are 5! = 120 ways in pairing off the two teams of 5 players. Thus there are 792 x 2002 x 120 = 190,270,080 ways of choosing two teams and then pairing them off for a tennis game. \square

Example 10
A company is made up of 3 departments with the one department consisting of 8 employees, the second department consisting of 10 employees and the third department consisting of 5 employees. The owner of the company decides to promote two employees chosen from the 23 employees. Suppose that the two employees are selected at random. How many ways can the two employees be selected if

  • both promotions are from the same department?
  • both promotions are from different departments?

The problem does not mention the positions for the promotion. Thus we assume that the two positions are identical. The first question has three cases based on the departments. The following is the sum of the three cases.

    \displaystyle \binom{8}{2}+\binom{10}{2}+\binom{5}{2}=28+45+10=83

For the second question, there are \binom{3}{2}=3 cases, based on pairs of departments. The following is the sum of the 3 cases.

    \displaystyle \binom{8}{1} \times \binom{10}{1}+\binom{8}{1} \times \binom{5}{1}+\binom{10}{1} \times \binom{5}{1}=80+40+50=170

Example 11
The problem is the same as Example 10 except that the two promotions are for President and Vice President.

Now that the two promotions are different, order matters. Thus use permutations to perform the calculations. the answer to the first question is:

    \displaystyle \frac{8!}{(8-2)!}+\frac{10!}{(1-2)!}+\frac{5!}{(5-2)!}=56+90+20=166

In the second question, we still pick one person from each department, but it needs to be multiplied by two since the positions are different.

    \displaystyle 2 \times 8 \times 10+2 \times 8 \times 5+2 \times 10 \times 5=160+80+100=340

___________________________________________________________________________

Exercises

Exercise 1
How many different letter arrangements can be formed from the letters in the word MISSISSIPPI?

Exercise 2
In how many ways can a manager assigns 3 different jobs at random to 11 available workers?

Exercise 3
Suppose that the license plates for a certain state consist of three numbers and three letters. How many different license plates are possible if

  1. the letters must come before the numbers?
  2. all letters must appear together and all numbers must appear together?
  3. only the letters must appear together?
  4. there is no restriction on the positions of the letters and numbers?

Exercise 4
In ordering a pizza, cheese and tomato sauce come with the pizza. The customer can also choose to add toppings from the following lists:

    Meat items: ham, sausage, pepperoni, salami, chicken.
    Vegetable items: pineapple, olive, mushroom, onion, bell peppers.

  1. How many distinct pizzas are possible?
  2. Suppose that a customer does not like salami and sausage in the meat list and onion and olive in the vegetable list and thus will not add these toppings. How many different pizzas are possible?
  3. Suppose that a customer would like to add two meat items and three vegetable items as toppings. How many different pizzas are possible?
  4. Suppose that a customer would like to add exactly 5 toppings. How many different pizzas are possible?
  5. Suppose that a customer would like to add at most 5 toppings. How many different pizzas are possible?

Exercise 5

  1. Twelve workers are randomly assigned to work in four factories with 3 workers assigned to each factory as assembly line workers. How many ways can the workers be assigned to the factories?
  2. Twelve workers are randomly assigned to work in four factories with 3 workers assigned to each factory as manager, assistant manager and assembly line worker. How many ways can the workers be assigned to the factories?

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

Answers

Exercise 1

    34,650

Exercise 2

    990

Exercise 3

  1. 17,576,000
  2. 35,152,000
  3. 70,304,000
  4. 351,520,000

Exercise 4

  1. 1024
  2. 64
  3. 100
  4. 252
  5. 638

Exercise 5

  1. 369,600
  2. 479,001,600

___________________________________________________________________________
\copyright \ 2017 \text{ by Dan Ma}

Advertisements

4 thoughts on “Permutations and combinations

  1. Pingback: Binomial coefficients | All Math Considered

  2. Pingback: Multinomial coefficients | All Math Considered

  3. Pingback: How to calculate winning odds in Powerball | All Math Considered

  4. Pingback: The probabilities of poker hands | All Math Considered

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s