Connexions

You are here: Home » Content » Combinations and Permutations

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
• FETMaths

This module is included inLens: Siyavula: Mathematics (Gr. 10-12)
By: Siyavula

Review Status: In Review

Click the "FETMaths" link to see all content affiliated with them.

Click the tag icon to display tags associated with this content.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.

Combinations and Permutations

Introduction

Mathematics education began with counting. In the beginning, fingers, beans and buttons were used to help with counting, but these are only practical for small numbers. What happens when a large number of items must be counted?

This chapter focuses on how to use mathematical techniques to count combinations of items.

Counting

An important aspect of probability theory is the ability to determine the total number of possible outcomes when multiple events are considered.

For example, what is the total number of possible outcomes when a die is rolled and then a coin is tossed? The roll of a die has six possible outcomes (1, 2, 3, 4, 5 or 6) and the toss of a coin, 2 outcomes (head or tails). Counting the possible outcomes can be tedious.

Making a List

The simplest method of counting the total number of outcomes is by making a list:

1H, 1T, 2H, 2T, 3H, 3T, 4H, 4T, 5H, 5T, 6H, 6T

or drawing up a table:

 die coin 1 H 1 T 2 H 2 T 3 H 3 T 4 H 4 T 5 H 5 T 6 H 6 T

Both these methods result in 12 possible outcomes, but both these methods have a lot of repetition. Maybe there is a smarter way to write down the result?

Tree Diagrams

One method of eliminating some of the repetition is to use tree diagrams. Tree diagrams are a graphical method of listing all possible combinations of events from a random experiment.

Notation

The Factorial Notation

For an integer nn, the notation n!n! (read nn factorial) represents:

n × ( n - 1 ) × ( n - 2 ) × ... × 3 × 2 × 1 n × ( n - 1 ) × ( n - 2 ) × ... × 3 × 2 × 1
(1)

with the following definition: 0!=10!=1.

The factorial notation will be used often in this chapter.

The Fundamental Counting Principle

The use of lists, tables and tree diagrams is only feasible for events with a few outcomes. When the number of outcomes grows, it is not practical to list the different possibilities and the fundamental counting principle is used.

The fundamental counting principle describes how to determine the total number of outcomes of a series of events.

Suppose that two experiments take place. The first experiment has n1n1 possible outcomes, and the second has n2n2 possible outcomes. Therefore, the first experiment, followed by the second experiment, will have a total of n1×n2n1×n2 possible outcomes. This idea can be generalised to mm experiments as the total number of outcomes for mm experiments is:

n 1 × n 2 × n 3 × ... × n m = i = 1 m n i n 1 × n 2 × n 3 × ... × n m = i = 1 m n i
(2)

is the multiplication equivalent of .

Note: the order in which the experiments are done does not affect the total number of possible outcomes.

Exercise 1: Lunch Special

A take-away has a 4-piece lunch special which consists of a sandwich, soup, dessert and drink for R25.00. They offer the following choices for :

Sandwich: chicken mayonnaise, cheese and tomato, tuna, and ham and lettuce

Soup: tomato, chicken noodle, vegetable

Dessert: ice-cream, piece of cake

Drink: tea, coffee, coke, Fanta and Sprite.

How many possible meals are there?

Solution

1. Step 1. Determine how many parts to the meal there are :

There are 4 parts: sandwich, soup, dessert and drink.

2. Step 2. Identify how many choices there are for each part :
 Meal component Sandwich Soup Dessert Drink Number of choices 4 3 2 5
3. Step 3. Use the fundamental counting principle to determine how many different meals are possible :
4 × 3 × 2 × 5 = 120 4 × 3 × 2 × 5 = 120
(3)

So there are 120 possible meals.

Combinations

The fundamental counting principle describes how to calculate the total number of outcomes when multiple independent events are performed together.

A more complex problem is determining how many combinations there are of selecting a group of objects from a set. Mathematically, a combination is defined as an un-ordered collection of unique elements, or more formally, a subset of a set. For example, suppose you have fifty-two playing cards, and select five cards. The five cards would form a combination and would be a subset of the set of 52 cards.

In a set, the order of the elements in the set does not matter. These are represented usually with curly braces. For example {2,4,6}{2,4,6} is a subset of the set {1,2,3,4,5,6}{1,2,3,4,5,6}. Since the order of the elements does not matter, only the specific elements are of interest. Therefore,

{ 2 , 4 , 6 } = { 6 , 4 , 2 } { 2 , 4 , 6 } = { 6 , 4 , 2 }
(4)

and {1,1,1}{1,1,1} is the same as {1}{1} because in a set the elements don't usually appear more than once.

So in summary we can say the following: Given SS, the set of all possible unique elements, a combination is a subset of the elements of SS. The order of the elements in a combination is not important (two lists with the same elements in different orders are considered to be the same combination). Also, the elements cannot be repeated in a combination (every element appears once).

Counting Combinations

Calculating the number of ways that certain patterns can be formed is the beginning of combinatorics, the study of combinations. Let SS be a set with nn objects. Combinations of rr objects from this set SS are subsets of SS having rr elements each (where the order of listing the elements does not distinguish two subsets).

Combination without Repetition

When the order does not matter, but each object can be chosen only once, the number of combinations is:

n ! r ! ( n - r ) ! = n r n ! r ! ( n - r ) ! = n r
(5)

where nn is the number of objects from which you can choose and rr is the number to be chosen.

For example, if you have 10 numbers and wish to choose 5 you would have 10!/(5!(10 - 5)!) = 252 ways to choose.

For example how many possible 5 card hands are there in a deck of cards with 52 cards?

52! / (5!(52-5)!) = 25989602598960 combinations

Combination with Repetition

When the order does not matter and an object can be chosen more than once, then the number of combinations is:

( n + r - 1 ) ! r ! ( n - 1 ) ! = n + r - 1 r = n + r - 1 n - 1 ( n + r - 1 ) ! r ! ( n - 1 ) ! = n + r - 1 r = n + r - 1 n - 1
(6)

where nn is the number of objects from which you can choose and rr is the number to be chosen.

For example, if you have ten types of donuts to choose from and you want three donuts there are (10 + 3 - 1)! / 3!(10 - 1)! = 220 ways to choose.

Note that in this video permutations are mentioned, you will cover permutations in the next section.

Figure 2
Khan academy video on probability - 1

Combinatorics and Probability

Combinatorics is quite useful in the computation of probabilities of events, as it can be used to determine exactly how many outcomes are possible in a given experiment.

Exercise 2: Probability

At a school, learners each play 2 sports. They can choose from netball, basketball, soccer, athletics, swimming, or tennis. What is the probability that a learner plays soccer and either netball, basketball or tennis?

Solution
1. Step 1. Identify what events we are counting :

We count the events: soccer and netball, soccer and basketball, soccer and tennis. This gives three choices.

2. Step 2. Calculate the total number of choices :

There are 6 sports to choose from and we choose 2 sports. There are

62=6!/(2!(6-2)!)62=6!/(2!(6-2)!) = 15 choices.

3. Step 3. Calculate the probability :

The probability is the number of events we are counting, divided by the total number of choices.

Probability = 315315 = 1515 = 0,2

Permutations

The concept of a combination did not consider the order of the elements of the subset to be important. A permutation is a combination with the order of a selection from a group being important. For example, for the set {1,2,3,4,5,6}{1,2,3,4,5,6}, the combination {1,2,3}{1,2,3} would be identical to the combination {3,2,1}{3,2,1}, but these two combinations are different permutations, because the elements in the set are ordered differently.

More formally, a permutation is an ordered list without repetitions, perhaps missing some elements.

This means that {1,2,2,3,4,5,6}{1,2,2,3,4,5,6} and {1,2,4,5,5,6}{1,2,4,5,5,6} are not permutations of the set {1,2,3,4,5,6}{1,2,3,4,5,6}.

Now suppose you have these objects:

1, 2, 3

Here is a list of all permutations of all three objects:

1 2 3; 1 3 2; 2 1 3; 2 3 1; 3 1 2; 3 2 1.

Counting Permutations

Let SS be a set with nn objects. Permutations of rr objects from this set SS refer to sequences of rr different elements of SS (where two sequences are considered different if they contain the same elements but in a different order). Formulas for the number of permutations and combinations are readily available and important throughout combinatorics.

It is easy to count the number of permutations of size rr when chosen from a set of size nn (with rnrn).

1. Select the first member of the permutation out of nn choices, because there are nn distinct elements in the set.
2. Next, since one of the nn elements has already been used, the second member of the permutation has (n-1)(n-1) elements to choose from the remaining set.
3. The third member of the permutation can be filled in (n-2)(n-2) ways since 2 have been used already.
4. This pattern continues until there are rr members on the permutation. This means that the last member can be filled in (n-(r-1))=(n-r+1)(n-(r-1))=(n-r+1) ways.
5. Summarizing, we find that there is a total of
n(n-1)(n-2)...(n-r+1)n(n-1)(n-2)...(n-r+1)
(7)
different permutations of rr objects, taken from a pool of nn objects. This number is denoted by P(n,r)P(n,r) and can be written in factorial notation as:
P(n,r)=n!(n-r)!.P(n,r)=n!(n-r)!.
(8)

For example, if we have a total of 5 elements, the integers {1,2,3,4,5}{1,2,3,4,5}, how many ways are there for a permutation of three elements to be selected from this set? In this case, n=5n=5 and r=3r=3. Then, P(5,3)=5!/7!=60!P(5,3)=5!/7!=60!.

Figure 3
Khan academy video on probability - 2

Exercise 3: Permutations

Show that a collection of nn objects has n!n! permutations.

Solution
1. Step 1. Decide how to choose the objects positions :

Proof: Constructing an ordered sequence of nn objects is equivalent to choosing the position occupied by the first object, then choosing the position of the second object, and so on, until we have chosen the position of each of our nn objects.

2. Step 2. Decide how many ways there are to choose an objects position :

There are n ways to choose a position for the first object. Once its position is fixed, we can choose from (n-1)(n-1) possible positions for the second object. With the first two placed, there are (n-2)(n-2) remaining possible positions for the third object; and so on. There are only two positions to choose from for the penultimate object, and the nthnth object will occupy the last remaining position.

3. Step 3. Use the fundamental counting principle :

Therefore, according to the fundamental counting principle, there are

n ( n - 1 ) ( n - 2 ) . . . 2 × 1 = n ! n ( n - 1 ) ( n - 2 ) . . . 2 × 1 = n !
(9)

ways of constructing an ordered sequence of nn objects.

Permutation with Repetition

When order matters and an object can be chosen more than once then the number of

permutations is:

n r n r
(10)

where nn is the number of objects from which you can choose and rr is the number to be chosen.

For example, if you have the letters A, B, C, and D and you wish to discover the number of ways of arranging them in three letter patterns (trigrams) you find that there are 4343 or 64 ways. This is because for the first slot you can choose any of the four values, for the second slot you can choose any of the four, and for the final slot you can choose any of the four letters. Multiplying them together gives the total.

Applications

The Binomial Theorem

In mathematics, the binomial theorem is an important formula giving the expansion of powers of sums. Its simplest version reads

( x + y ) n = k = 0 n n k x k y n - k ( x + y ) n = k = 0 n n k x k y n - k
(11)

Whenever nn is a positive integer, the numbers

n k = n ! k ! ( n - k ) ! n k = n ! k ! ( n - k ) !
(12)

are the binomial coefficients (the coefficients in front of the powers).

For example, here are the cases n = 2, n = 3 and n = 4:

( x + y ) 2 = x 2 + 2 x y + y 2 ( x + y ) 3 = x 3 + 3 x 2 y + 3 x y 2 + y 3 ( x + y ) 4 = x 4 + 4 x 3 y + 6 x 2 y 2 + 4 x y 3 + y 4 ( x + y ) 2 = x 2 + 2 x y + y 2 ( x + y ) 3 = x 3 + 3 x 2 y + 3 x y 2 + y 3 ( x + y ) 4 = x 4 + 4 x 3 y + 6 x 2 y 2 + 4 x y 3 + y 4
(13)

The coefficients form a triangle, where each number is the sum of the two numbers above it:

This formula, and the triangular arrangement of the binomial coefficients, are often attributed to Blaise Pascal who described them in the 17th century. It was, however, known to the Chinese mathematician Yang Hui in the 13th century, the earlier Persian mathematician Omar KhayyÃ¡m in the 11th century, and the even earlier Indian mathematician Pingala in the 3rd century BC.

Exercise 4: Number Plates

The number plate on a car consists of any 3 letters of the alphabet (excluding the vowels and 'Q'), followed by any 3 digits (0 to 9). For a car chosen at random, what is the probability that the number plate starts with a 'Y' and ends with an odd digit?

Solution

1. Step 1. Identify what events are counted :

The number plate starts with a 'Y', so there is only 1 choice for the first letter, and ends with an even digit, so there are 5 choices for the last digit (1, 3, 5, 7, 9).

2. Step 2. Find the number of events :

Use the counting principle. For each of the other letters, there are 20 possible choices (26 in the alphabet, minus 5 vowels and 'Q') and 10 possible choices for each of the other digits.

Number of events = 1×20×20×10×10×5=2000001×20×20×10×10×5=200000

3. Step 3. Find the number of total number of possible number plates :

Use the counting principle. This time, the first letter and last digit can be anything.

Total number of choices = 20×20×20×10×10×10=800000020×20×20×10×10×10=8000000

4. Step 4. Calculate the probability :

The probability is the number of events we are counting, divided by the total number of choices.

Probability = 2000008000000=140=0,0252000008000000=140=0,025

Exercise 5: Factorial

Show that

n ! ( n - 1 ) ! = n n ! ( n - 1 ) ! = n
(14)

Solution

1. Step 1.

Method 1: Expand the factorial notation.

n ! ( n - 1 ) ! = n × ( n - 1 ) × ( n - 2 ) × . . . × 2 × 1 ( n - 1 ) × ( n - 2 ) × . . . × 2 × 1 n ! ( n - 1 ) ! = n × ( n - 1 ) × ( n - 2 ) × . . . × 2 × 1 ( n - 1 ) × ( n - 2 ) × . . . × 2 × 1
(15)

Cancelling the common factor of (n-1)×(n-2)×...×2×1(n-1)×(n-2)×...×2×1 on the top and bottom leaves nn.

So n!(n-1)!=nn!(n-1)!=n

2. Step 2.

Method 2: We know that P(n,r)=n!(n-r)!P(n,r)=n!(n-r)! is the number of permutations of rr objects, taken from a pool of nn objects. In this case, r=1r=1. To choose 1 object from nn objects, there are nn choices.

So n!(n-1)!=nn!(n-1)!=n

Exercises

1. Tshepo and Sally go to a restaurant, where the menu is:
 Starter Main Course Dessert Chicken wings Beef burger Chocolate ice cream Mushroom soup Chicken burger Strawberry ice cream Greek salad Chicken curry Apple crumble Lamb curry Chocolate mousse Vegetable lasagne
1. How many different combinations (of starter, main course, and dessert) can Tshepo have?
2. Sally doesn't like chicken. How many different combinations can she have?
2. Four coins are thrown, and the outcomes recorded. How many different ways are there of getting three heads? First write out the possibilities, and then use the formula for combinations.
3. The answers in a multiple choice test can be A, B, C, D, or E. In a test of 12 questions, how many different ways are there of answering the test?
4. A girl has 4 dresses, 2 necklaces, and 3 handbags.
1. How many different choices of outfit (dress, necklace and handbag) does she have?
2. She now buys two pairs of shoes. How many choices of outfit (dress, necklace, handbag and shoes) does she now have?
5. In a soccer tournament of 9 teams, every team plays every other team.
1. How many matches are there in the tournament?
2. If there are 5 boys' teams and 4 girls' teams, what is the probability that the first match will be played between 2 girls' teams?
6. The letters of the word 'BLUE' are rearranged randomly. How many new words (a word is any combination of letters) can be made?
7. The letters of the word 'CHEMISTRY' are arranged randomly to form a new word. What is the probability that the word will start and end with a vowel?
8. There are 2 History classes, 5 Accounting classes, and 4 Mathematics classes at school. Luke wants to do all three subjects. How many possible combinations of classes are there?
9. A school netball team has 8 members. How many ways are there to choose a captain, vice-captain, and reserve?
10. A class has 15 boys and 10 girls. A debating team of 4 boys and 6 girls must be chosen. How many ways can this be done?
11. A secret pin number is 3 characters long, and can use any digit (0 to 9) or any letter of the alphabet. Repeated characters are allowed. How many possible combinations are there?

Content actions

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks