Interactive Lessons

Counting: combinations, Pascal’s triangle and routes

Lecture notes

Definition

A team: the order does not matter

A team is a choice of r members from n, and the order does not matter: the team A B C is the same team as C B A. A line-up (a permutation) is different: A B C and C B A are two different line-ups. Counting the teams is counting the combinations. In Pick a team you tap r of the tiles and the application lists all the teams.
Example
Take 3 of the 5 tiles A, B, C, D, E. The team A B C is one team, but it can be lined up in ways: A B C, A C B, B A C, B C A, C A B and C B A.
Rule

From line-ups to teams

To count the teams of r from n, count the line-ups first. There are of them, with r factors. A team is counted once for each of its r! line-ups, so divide by r!. That gives .
Example
Teams of 3 from 5 tiles. The line-ups are . One team has line-ups. So there are teams.
Rule

The formula with factorials

Write . Then . In practice you cancel: the first r factors of n! stay on top and r! goes below. Teams and line-ups shows the same thing with a team and its line-ups.
Example
. With factorials: 8! = 40 320, 3! = 6 and 5! = 120, so .
Rule

Who stays out?

Choosing the r members who join is the same as choosing the n − r members who stay out, so . Choosing nobody or everybody can be done in one way, so . To calculate, use the smaller of r and n − r. The tab Who stays out? shows it with the bars of one row of the triangle.
Example
. In row 9 of the triangle the same number stands at place 2 and at place 7.
11112113311464115101051161520156117213535217118285670562881193684126126843691
Definition

Pascal’s triangle

Pascal’s triangle starts with 1 at the top. Every number is the sum of the two numbers above it, and the two ends of each row are 1. The number in row n at place k (counting from 0) is C(n, k). Row n adds up to twice the row above, so it adds up to with n factors. In The triangle you pick a row and a place.
Example
Row 6 is 1, 6, 15, 20, 15, 6, 1. The 15 at place 2 is , the two numbers of row 5 above it, and it is C(6, 2). The row adds up to .
111121133114641151010511615201561
Definition

Routes on a map

On a road diagram you walk from S to E, only to the right or up. Write at every junction the number of routes that reach it. A route arrives from the left or from below, so the number is the number on the left plus the number below. Along the two edges every junction has 1. Routes on a map fills the numbers in diagonal by diagonal.
Example
A map 3 blocks to the right and 2 up. The junction left of E has 6 routes and the junction below it has 4, so E has routes.
1111231361410SE
Rule

A closed junction

Tap a junction in Routes on a map to close it. The routes that avoid it are all the routes minus the routes through it. The routes through it are the routes from S to the junction times the routes from the junction to E.
Example
Map of 4 blocks to the right and 3 up; close the junction 2 to the right and 1 up. All routes: 35. From S to the junction: 3. From the junction to E: 6. Through it there are routes. Avoiding it there are .
111112341371141112617SE
Rule

One number, three stories

The same number C(n, k) counts three things: the routes of n steps of which k go up, the teams of k chosen from n places, and the entry in row n at place k of the triangle. A route is a team: the team is the set of steps that go up. Same numbers, three stories shows the three stories side by side.
Example
. That is the number of routes of 5 steps with 2 up (the map of 3 blocks to the right and 2 up has 10), the number of teams of 2 chosen from 5 steps, and the entry 10 in row 5 at place 2.
11112113311464115101051
Rule

Which way of counting?

Ask three questions in this order. May an object be used again? Then with r factors. Are all the objects used, in a row? Then n!. Does the order matter? Then with r factors. If the order does not matter: C(n, r). Sort the situation leads you through the three questions for 20 situations.
Example
A padlock with 3 wheels of 6 colours: repeats allowed, . 6 books in a row: 6! = 720. The first 3 places of 8 runners: the order matters, . A team of 3 from 8: the order does not matter, .
Rule

Split or subtract

When the objects have two kinds, split the problem into cases or subtract. “Exactly j of the first kind” multiplies the choices of each kind. “At least one of the second kind” is all the ways minus the ways with none of it. Split or subtract shows the cases as bars that add up to all the ways.
Example
A bag has 4 red and 3 blue tiles and you take 3. Exactly 2 red gives . At least one blue gives . All the cases: 0, 1, 2 or 3 red are .
Tip

Choose the picture first

A tree diagram shows stages with new choices after each choice. A road diagram counts routes on a map. A grid pairs every row with every column. Look at the shape of the problem and choose the picture before you count; the question of the practice kind “Which picture shows the problem best?” asks exactly this.
Example
Coffee in 2 sizes, tea in 3 sizes and juice in 1 size: a tree, choices. A walk from home to school on a street map: a road diagram. Each of 4 players against each of 3 players: a grid, games.
Tip

The quiz and the class round

The quiz mixes the questions of the three applications in three levels, without end. The class round asks the whole class 5 questions at once: a definition, a rule, a true-or-myth statement and two questions with numbers (teams of r from n, routes on a map, the first places of a race). Every wrong option has a trap name that says what the pupil did.
Example
A club of 6 members chooses a team of 3: the right answer is . The answer counts the line-ups as well; the answer lets an object be used again.
Tip

Keys and privacy

Every tile, junction and button works by keyboard: Tab moves to the next one, Enter (or the space bar) presses it. Nothing you do in these applications is stored or sent anywhere. The situations and the numbers are original: we wrote them for these applications.
Example
In Pick a team press Tab to reach a tile and Enter to put it in the team; Enter again takes it out.

Exercises

You have 5 tiles A, B, C, D and E. How many different pairs can you take if the order does not matter? Easy
Show solution
List the pairs in order. The pairs with A: A B, A C, A D and A E: 4 pairs.
The new pairs with B (A B is in the list already): B C, B D and B E: 3 pairs. Then C D and C E: 2 pairs. Then D E: 1 pair.
Together that is .
10 pairs.
It is also , because counts every pair twice (A B and B A).
Row 5 of Pascal’s triangle is 1, 5, 10, 10, 5, 1. How many different teams of 2 can be chosen from 5 members, and what do the numbers of the row add up to? Easy
11112113311464115101051
Show solution
Count the places from 0: place 0 is 1, place 1 is 5 and place 2 is 10. The teams of 2 from 5 are .
The sum is .
10 teams; the row adds up to 32.
Also , because each row adds up to twice the row above.
On a map you walk from S to E, 2 blocks to the right and 2 up, only to the right or up. How many different routes are there? Easy
111123136SE
Show solution
Write 1 at every junction on the two edges: there is only one way along the street.
The middle junction is . The junction right of it is and the junction above it is .
At E you get .
6 routes.
It is also . Of the 4 steps, choose which 2 go up.
A club has 9 members. How many different teams of 3 can be chosen? Medium
Show solution
First the line-ups of 3 from 9. There are of them.
One team has line-ups, so divide by 6.
.
84 teams.
By the symmetry , and is the easier way to the same number.
On a map of 5 blocks to the right and 3 up you walk from S to E. The junction 2 to the right and 1 up is closed. How many routes avoid it? Medium
11111234137114111261713926SE
Show solution
There are routes in all.
From S to the closed junction (2 right, 1 up) there are 3 routes. From it to E (3 right, 2 up) there are routes.
Through it there are routes. Avoiding it there are routes.
26 routes.
Check: the numbers of the road diagram with the closed junction give 26 at E as well.
Which way of counting fits, and how many are there? (a) A code of 4 digits from 0 to 9, a digit may be used again. (b) 5 books in a row on a shelf. (c) A pair of 2 chosen from 9 pupils. Medium
Show solution
(a) May an object be used again? Yes, so every place has 10 choices and there are codes.
(b) No repeats and all the objects in a row, so 5! = .
(c) No repeats, not all the objects and the order does not matter, so .
(a) 10 000, (b) 120, (c) 36.
The three questions always come in this order: repeats, all the objects, order.
A club has 10 members and chooses a team of 4. (a) The captain must be in the team. How many teams are possible? (b) The captain must not be in the team. How many teams? Hard
Show solution
(a) The captain is in, so 3 places are left for the other 9 members. That is .
(b) The captain is out, so the team of 4 comes from the other 9 members. That is .
The two cases together are all the teams, and .
(a) 84 teams, (b) 126 teams.
Settle the special member first, then count what is left.
In a league of 8 teams every team plays every other team once. How many matches are played? Hard
Show solution
A match is a pair of teams, and the order of the two teams does not matter: it is a combination.
Every team plays 7 matches, which gives . But then every match is counted twice.
Dividing by 2 gives , which is C(8, 2).
28 matches.
By the symmetry , and the entry at place 2 in row 8 of the triangle is 28 too.
A bag holds 6 red and 4 blue tiles. You take 4 tiles at once. How many different sets have at least one blue tile? Hard
Show solution
All the sets of 4 from the 10 tiles number .
The sets with no blue tile have 4 red tiles, so there are of them.
At least one blue is all the sets minus the sets with none, so .
195 sets.
Counting the cases with 1, 2, 3 and 4 blue tiles one by one gives the same number, but it is much longer.

Interactive applications for this topic

Free applications open with a free student account. Teachers can use all applications in a live lesson.

About the free account and Plus

Are you a teacher?

Start live lessons with these applications for your whole class. Free to try for one month.

Try it free

Fits these school years

IB (MYP, Diploma): MYP 5, Diploma, year 1, Diploma, year 2

Cambridge International: AS Level, A Level

Netherlands: Vwo · Mathematics A, Vwo · Mathematics C, Vwo · Mathematics D, Havo · Mathematics A

Türkiye (MEB): Year 10 (MEB)

England (GCSE, A Level): Year 12 (A Level), Year 13 (A Level)

USA (Common Core): Algebra 2, Precalculus

What the applications of this topic teach 3 applications

Choose r of n: combinations

  • Picking r of n tiles: the number of teams is C(n, r)
  • Explaining why teams are line-ups divided by r factorial
  • Using C(n, r) = C(n, n − r) for the easier calculation
  • Telling a combination from a line-up

Pascal's triangle and routes

  • Reading Pascal's triangle
  • Counting routes on a road diagram junction by junction
  • Counting routes that avoid a closed junction
  • Seeing that routes, teams and Pascal's entries give C(n, k)

Which way of counting?

  • Deciding which way of counting fits: repeats, order, no order
  • Splitting a counting problem into cases
  • Choosing the picture that shows a counting problem best