Combinatorics · Chapter 2

Combinations

When order doesn't matter, count the ordered picks and divide out the repeats: that's choosing.

What's this chapter about?

2.1 Combinations Fundamentals
2.2 Binomial Identity
2.3 Tricky Combinations Examples
2.4 Practice Problems

You'll need

open on YouTube

2.10%

Combinations Fundamentals

In this section you will be able to count choices where order doesn't matter, by dividing the ordered picks by k!.

You grab 3 pencils from a box of 6 for a test. Grabbing the red one first and the blue one second gives the same 3 pencils as the other way round. So how many different handfuls are there?

In Chapter 1, order mattered. Now it doesn’t. The trick: count the ordered picks first, then divide by the number of ways to order each group. That’s $k!$ .

Look:Choosing 2 of 6 things to keep is the same as choosing 4 of them to leave behind.

Exploreplay first, formulas later

Try this: You are picking 3 of 5 balls in order. Press Spotlight a group. How many times does that same group of 3 show up?
Try this: Switch on "Order doesn't matter". How many piles are there, and how many ordered picks sit in each pile?
Try this: Set k to 2. Now how big is each pile? Predict the number of piles before you look.
Try this: Turn on Show the formula. Check that 60 ÷ 3! = 10.

Name it

Definition 2.1.1

A combination is a collection of items where the order of the items does not matter.

Remark 2.1.2

Usually, the words permute, order does matter, etc. imply a permutation, while the words choose, select, order doesn't matter, etc. imply a combination.

Theorem 2.1.3 · Combinations Formula

The number of ways to choose $k$ objects out of a total of $n$ objects is

\binom{n}{k} = \frac{n!}{k!\,(n-k)!} = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}.

Remark 2.1.4

Look:

\binom{n}{k} = \binom{n}{n-k}.

This is true because choosing the $k$ objects that are part of your selection (left-hand side) is the same as choosing the $n-k$ objects that are not part of your selection (right-hand side). For example,

\binom{6}{2} = \binom{6}{4}.

Watch itpredict, then reveal

Example 2.1

How many ways can I select 3 pencils from 6 different pencils?

pencils n6

pick k3

P1P2P3

P1P2P4

P1P2P5

P1P2P6

P1P3P2

P1P3P4

P1P3P5

P1P3P6

P1P4P2

P1P4P3

P1P4P5

P1P4P6

P1P5P2

P1P5P3

P1P5P4

P1P5P6

P1P6P2

P1P6P3

P1P6P4

P1P6P5

P2P1P3

P2P1P4

P2P1P5

P2P1P6

P2P3P1

P2P3P4

P2P3P5

P2P3P6

P2P4P1

P2P4P3

P2P4P5

P2P4P6

P2P5P1

P2P5P3

P2P5P4

P2P5P6

P2P6P1

P2P6P3

P2P6P4

P2P6P5

P3P1P2

P3P1P4

P3P1P5

P3P1P6

P3P2P1

P3P2P4

P3P2P5

P3P2P6

P3P4P1

P3P4P2

P3P4P5

P3P4P6

P3P5P1

P3P5P2

P3P5P4

P3P5P6

P3P6P1

P3P6P2

P3P6P4

P3P6P5

P4P1P2

P4P1P3

P4P1P5

P4P1P6

P4P2P1

P4P2P3

P4P2P5

P4P2P6

P4P3P1

P4P3P2

P4P3P5

P4P3P6

P4P5P1

P4P5P2

P4P5P3

P4P5P6

P4P6P1

P4P6P2

P4P6P3

P4P6P5

P5P1P2

P5P1P3

P5P1P4

P5P1P6

P5P2P1

P5P2P3

P5P2P4

P5P2P6

P5P3P1

P5P3P2

P5P3P4

P5P3P6

P5P4P1

P5P4P2

P5P4P3

P5P4P6

P5P6P1

P5P6P2

P5P6P3

P5P6P4

P6P1P2

P6P1P3

P6P1P4

P6P1P5

P6P2P1

P6P2P3

P6P2P4

P6P2P5

P6P3P1

P6P3P2

P6P3P4

P6P3P5

P6P4P1

P6P4P2

P6P4P3

P6P4P5

P6P5P1

P6P5P2

P6P5P3

P6P5P4

6 × 5 × 4 = 120 ordered picks

1
Let's first treat it like a permutation. How many choices for the 1st pencil, the 2nd pencil and the 3rd pencil, all multiplied together?

Predict first:
Your prediction

Example 2.2

How many ways are there to choose a committee of 3 people from 6 people?

people n6

pick k3

ABC

ABD

ABE

ABF

ACB

ACD

ACE

ACF

ADB

ADC

ADE

ADF

AEB

AEC

AED

AEF

AFB

AFC

AFD

AFE

BAC

BAD

BAE

BAF

BCA

BCD

BCE

BCF

BDA

BDC

BDE

BDF

BEA

BEC

BED

BEF

BFA

BFC

BFD

BFE

CAB

CAD

CAE

CAF

CBA

CBD

CBE

CBF

CDA

CDB

CDE

CDF

CEA

CEB

CED

CEF

CFA

CFB

CFD

CFE

DAB

DAC

DAE

DAF

DBA

DBC

DBE

DBF

DCA

DCB

DCE

DCF

DEA

DEB

DEC

DEF

DFA

DFB

DFC

DFE

EAB

EAC

EAD

EAF

EBA

EBC

EBD

EBF

ECA

ECB

ECD

ECF

EDA

EDB

EDC

EDF

EFA

EFB

EFC

EFD

FAB

FAC

FAD

FAE

FBA

FBC

FBD

FBE

FCA

FCB

FCD

FCE

FDA

FDB

FDC

FDE

FEA

FEB

FEC

FED

6 × 5 × 4 = 120 ordered picks

1
Does the order of the people in a committee matter?

Predict first:

open on YouTube

Example 2.3

Evaluate $\dbinom{6}{3}$

1
What are $n$ and $k$ here?

Predict first:
Your prediction: nYour prediction: k

Example 2.4

Omega Learn

You are working on the Mastering AMC 8 Book, and you must choose 7 of the 10 combinatorics chapters to work on. How many ways are there to do this?

1
Does the order of the 7 chapters matter?

Predict first:

open on YouTube

Example 2.5

Omega Learn

You are working on the Mastering AMC 8 Book, and you must choose 7 of the 10 combinatorics chapters to work on. However, the first 2 chapters are required to understand the remaining chapters so they must be chosen. How many ways are there to do this?

1
The first 2 chapters are already in. How many more chapters do you still need to choose?

Predict first:
Your prediction

open on YouTube

Try it

Problem 2.4.1

If you have Alice, Betty, Chase, and Dave and you need to choose two of them to be the leaders of the math club, how many ways are there to do this?

Problem 2.4.2

Evaluate $\dbinom{8}{4}$ and $\dbinom{9}{7}$

Problem 2.4.3

How many ways are there to select 3 fruits amongst 8 different fruits?

Problem 2.4.4

How many ways are there to choose 4 balls from a bag which contains 9 balls of different color?

Problem 2.4.5

Mrs. Jones is organizing a potluck and wants to serve 8 different dishes. Each family can bring 3 dishes. How many families can Mrs. Jones invite so that no two families bring the same combination of dishes?

Checkpoint for section 2.1

Get 2 of 3 right to master this section. One try each, no hints.

2.20%

Binomial Identity

In this section you will be able to count every possible collection of n things at once, using take-it-or-leave-it choices.

Nihir is packing a picnic basket. He can take any of his 5 fruits, or none of them. How many different baskets could he bring? Guess first!

Each row of Pascal’s triangle lists the ways to choose 0, 1, 2, … things from a group. Add up a whole row and you count every possible choice at once.

Look:For each item you have just 2 choices: take it or leave it. So n items give 2 × 2 × … × 2 = 2ⁿ collections.

Exploreplay first, formulas later

Try this: Click any number inside the triangle. Which two numbers above it add up to it?
Try this: Click the 15 in row 6. Turn on Mirror. Where is its twin, and why are they equal?
Try this: Turn on Row sums. Read the sums from the top: 1, 2, 4, 8, ... What comes next?

Name it

Theorem 2.2.1 · Binomial Identity

The binomial identity states that

\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n.

Remark 2.2.2

Both of the above methods (adding up $\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n}$ , or just computing $2^n$ ) can be used for calculating the number of ways of choosing any number of items from $n$ different items.

Watch itpredict, then reveal

Example 2.6

Nihir has an apple, orange, banana, pear, and raspberry. He wants to take a fruit basket to a picnic. How many different types of fruit baskets can he take using the fruits he has?

1
One way: list the baskets with 0 fruits, 1 fruit, 2 fruits, and so on. Is there an easier way to solve this question?

Example 2.7

You have 5 different pencils and 3 different erasers and must choose some of them to take to the AMC 8. How many ways are there to do this?

1
How many different things can you take or leave?

Predict first:
Your prediction

open on YouTube

Contest cornerreal contest problems

Problem 2.4.8

AMC 10

Henry's Hamburger Haven offers its hamburgers with the following condiments: ketchup, mustard, mayonnaise, tomato, lettuce, pickles, cheese, and onions. A customer can choose one, two, or three meat patties and any collection of condiments. How many different kinds of hamburgers can be ordered?

Checkpoint for section 2.2

Get 2 of 3 right to master this section. One try each, no hints.

2.30%

Tricky Combinations Examples

In this section you will be able to break a tricky choosing problem into stages, and multiply the stages together.

A company has 13 job applicants. It needs 2 managers and 4 more workers, and the managers must be experienced. Where do you even start?

Big choosing problems are easier in stages. Choose one group, then choose the next group from whoever is left. Every choice in one stage goes with every choice in the next, so you multiply.

Look:When the order is forced (like digits in increasing order), you only need to choose which items to use.

Exploreplay first, formulas later

experienced6

new7

committee size4

Rule on experienced:

Build one committee: tap 4 people.

0 of 4 picked

0 experienced + 4 newC(6,0) × C(7,4) = 1 × 35 = 35 ✓
1 experienced + 3 newC(6,1) × C(7,3) = 6 × 35 = 210 ✓
2 experienced + 2 newC(6,2) × C(7,2) = 15 × 21 = 315 ✓
3 experienced + 1 newC(6,3) × C(7,1) = 20 × 7 = 140 ✓
4 experienced + 0 newC(6,4) × C(7,0) = 15 × 1 = 15 ✓

35 + 210 + 315 + 140 + 15 = 715 committeesSame as choosing 4 of all 13: C(13,4) = 715

Try this: Tap 4 people to build one committee. Which row of the table does it belong to?
Try this: Add up the ways column. Does it match choosing 4 of all 13 people?
Try this: Choose Exactly and set it to 2. Why is the answer C(6,2) × C(7,2)?
Try this: Now try At least 1. Which row got crossed out? Count all committees, then subtract it.

Watch itpredict, then reveal

Example 2.8

Omega Learn

There are 6 experienced applicants and 7 inexperienced applicants applying for a job. Out of the experienced applicants, 2 managers are selected. Out of all of the other applicants who aren't selected for a manager (both experienced and inexperienced), 4 other employees are selected. How many ways are there to do this?

1
First, how many ways are there to select the 2 managers?

Predict first:
Your prediction

Example 2.9

Omega Learn

You have 12 different energy bars that you need to give to 3 people: Alice, Betty, and Chase. Alice needs 3 bars, Betty needs 4 bars, and Chase needs 5 bars. How many ways are there to distribute the 12 bars to satisfy their requirements?

1
Start with Alice. How many ways can you pick her 3 bars?

Predict first:
Your prediction

open on YouTube

Example 2.10

EMCC

How many ways are there to place 4 balls into a $4 \times 6$ grid such that no column or row has more than one ball in it? (Rotations and reflections are considered distinct.)

One possible placement.

1
There are 4 rows and 4 balls, with at most one ball per row. How many balls go in each row?

Predict first:
Your prediction

open on YouTube

Example 2.11

AIME

Robert has 4 indistinguishable gold coins and 4 indistinguishable silver coins. Each coin has an engraving of one face on one side, but not on the other. He wants to stack the eight coins on a table into a single stack so that no two adjacent coins are face to face. Find the number of possible distinguishable arrangements of the 8 coins.

1
First, deal with the colours. How many ways are there to arrange the 4 gold and 4 silver coins in the stack?

Predict first:
Your prediction

Contest cornerreal contest problems

Problem 2.4.7

AMC 10

A set of 25 square blocks is arranged into a $5 \times 5$ square. How many different combinations of 3 blocks can be selected from that set so that no two are in the same row or column?

Checkpoint for section 2.3

Get 2 of 3 right to master this section. One try each, no hints.

2.4

Practice Problems

In this section you will be able to mix every idea from this chapter on practice problems.

Time to mix it all up! These problems use combinations, symmetry, take-it-or-leave-it choices and stages. Every problem has three hints if you get stuck.

Want every problem from this chapter on one page? Open the problem set.

Mixed practice

Problem 2.4.6

There are 9 different flavors of ice cream at an ice cream shop. Joe wants to buy 2 or 3 scoops of different ice cream flavors. He doesn't like 2 of the flavors Mango and Chocolate together so won't buy them together. How many ways can he buy ice cream?