Counting 201-SN1-RE: revision sheet

The thread of the chapter

Counting starts by writing the sentence that says when two outcomes are the same: does order matter, can an object come back, can two objects be told apart? Then checking that each outcome is counted once and only once.

Topics covered

Multiplication principle
Addition principle
Factorial notation
Permutations
Permutations of identical objects
Arrangements
Combinations
Set operations
Inclusion-exclusion principle
Pascal's triangle
Binomial theorem
Probability by counting

The chapter at a glance

Choosing the formula with two questions

First write what ONE outcome is, then read the table from top to bottom: does order matter, can an object come back? The two answers point to a column, and the formula comes after.

Criterion	Sequence with repetition ordered places, an object can come back	Arrangement ordered places, distinct objects	Combination a group, order changes nothing	Identical objects all placed, some alike
Does order matter?	Yes	Yes	No	Yes, but swapping two identical objects changes nothing
Can an object come back?	Yes	No	No	Each object is placed once
Formula	$n^{k}$	$P(n,k)=\frac{n!}{(n-k)!}$	$\binom{n}{k}=\frac{n!}{k!\,(n-k)!}$	$\frac{n!}{n_{1}!\,n_{2}!\cdots n_{r}!}$
Example	Words of 3 bases over A, C, G, T: $4^{3}=64$	Leader, secretary and photographer out of 10: $10\times 9\times 8=720$	Team of 3 out of 10: $\binom{10}{3}=120$	Sequences with A, A, C, C, G: $\frac{5!}{2!\,2!}=30$
Words in the question	code, sequence, word, with replacement	ranking, distinct roles, numbered positions	team, group, mixture, simultaneous draw	anagram, sequence of given composition

Sequence with repetition ordered places, an object can come back

Does order matter?: Yes
Can an object come back?: Yes
Formula: $n^{k}$
Example: Words of 3 bases over A, C, G, T: $4^{3}=64$
Words in the question: code, sequence, word, with replacement

Arrangement ordered places, distinct objects

Does order matter?: Yes
Can an object come back?: No
Formula: $P(n,k)=\frac{n!}{(n-k)!}$
Example: Leader, secretary and photographer out of 10: $10\times 9\times 8=720$
Words in the question: ranking, distinct roles, numbered positions

Combination a group, order changes nothing

Does order matter?: No
Can an object come back?: No
Formula: $\binom{n}{k}=\frac{n!}{k!\,(n-k)!}$
Example: Team of 3 out of 10: $\binom{10}{3}=120$
Words in the question: team, group, mixture, simultaneous draw

Identical objects all placed, some alike

Does order matter?: Yes, but swapping two identical objects changes nothing
Can an object come back?: Each object is placed once
Formula: $\frac{n!}{n_{1}!\,n_{2}!\cdots n_{r}!}$
Example: Sequences with A, A, C, C, G: $\frac{5!}{2!\,2!}=30$
Words in the question: anagram, sequence of given composition

Legend: the words in the table

Order matters: Two outcomes made of the same objects placed in another order are DIFFERENT: 17-4 and 4-17 are two tickets.
Repetition: The same object can occupy several places, like a base that comes back in a codon.
Arrangement: An ordered list of k distinct objects taken from n (a k-permutation).
Combination: A set of k distinct objects taken from n, without order: a group, a team, a mixture.
Identical objects: Objects that cannot be told apart once placed: two A's of a sequence, two sterile controls.

Several groups of the same size WITHOUT names (teams with no sector): first count numbered groups, then divide by the number of ways to number the groups.

The essentials

Arrangement and combination: a single difference, the factor k!

• An arrangement is a combination THEN an order: choose WHICH objects, $\binom{n}{k}$ ways, then in WHAT ORDER to place them, $k!$ ways.
• Hence $P(n,k)=k!\binom{n}{k}$ , and $\binom{n}{k}=\dfrac{P(n,k)}{k!}$ .
• Example: $P(10,\,3)=720$ ordered lists, grouped in bundles of $3!=6$ that contain the same people, give $\binom{10}{3}=120$ groups.

A single group {A, B, C}, but six ordered lists: each combination of 3 objects is counted

3!=6

times among the arrangements.

The test that decides: are two outcomes that differ only by their order the same outcome? If so, divide by k!.

Multiply, add, subtract

• MULTIPLICATION PRINCIPLE: successive steps with $n_{1},n_{2},\dots$ choices give $n_{1}\times n_{2}\times\cdots$ outcomes, if the NUMBER of choices at a step does not depend on the earlier choices.
• ADDITION PRINCIPLE: DISJOINT families add up. Otherwise, $|A\cup B|=|A|+|B|-|A\cap B|$ .
• Three sets: $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$ .
• Complement and De Morgan: $|\overline{A}|=|\Omega|-|A|$ and $\overline{A\cup B}=\overline{A}\cap\overline{B}$ ; “at least one” is the complement of “none”.

Before adding, ask whether the same outcome can be in two families. If so, the intersection must be removed.

Pascal's triangle and the binomial theorem

• Pascal's identity: $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ for $1\le k\le n-1$ ; symmetry: $\binom{n}{k}=\binom{n}{n-k}$ .
• Binomial theorem: $(a+b)^{n}=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k}$ . The general term is computed with its signs and its coefficients: $\binom{n}{k}(\alpha x)^{n-k}\beta^{k}$ .
• With $a=b=1$ : $\sum_{k=0}^{n}\binom{n}{k}=2^{n}$ , the number of subsets of a set with $n$ elements.

Each number is the sum of the two numbers above it:

10+10=20

, that is

\binom{6}{3}=\binom{5}{2}+\binom{5}{3}

. Each row reads the same in both directions.

The mistakes that cost marks

These are the errors I correct most often in session. Each one costs marks on a paper, even when the reasoning behind it is right.

1. Counting a group like a ranking

the whole question

What not to write

“A team of 3 students out of 10: $10\times 9\times 8=720$ teams.”

What to write

“A team with no roles is a set; the order of choice does not matter: $\binom{10}{3}=\frac{720}{3!}=120$ teams.”

Why: The product 10 × 9 × 8 produces each team once per order of choice, that is six times. It would be right for three distinct roles.

2. Adding two sets that overlap

2 marks

What not to write

“40 plots have maples and 25 have birches: 65 plots have at least one of the two species.”

What to write

“9 plots have both species: $|A\cup B|=40+25-9=56$ .”

The red lens belongs to both circles: the sum

40+25

counts its 9 plots twice, and only one copy is removed.

Why: The addition principle requires disjoint families. The common plots are in both numbers: they are counted twice.

3. Counting “at least one” by designating “the” first one

2 to 3 marks

What not to write

“4 species out of 8, 3 of them endangered, with at least one endangered: I choose the endangered one, then 3 others, $3\times\binom{7}{3}=105$ .”

What to write

“Through the complement: $\binom{8}{4}-\binom{5}{4}=70-5=65$ choices.”

Why: A choice that contains two endangered species is produced twice, once per species designated as “the” endangered one. The complement, “no endangered species”, counts nothing twice.

4. Permuting identical objects as if they were distinct

2 marks

What not to write

“With the bases A, A, C, C, G, we write $5!=120$ sequences.”

What to write

“Swapping the two A's or the two C's changes nothing: $\frac{5!}{2!\,2!}=30$ sequences.”

With A, A, C: six orderings if the two A's are told apart, but only three sequences, since each sequence is obtained

2!=2

times.

Why: Each sequence is produced 2! × 2! = 4 times by the 120 arrangements. Divide by the swaps that change nothing.

5. Forgetting that the groups have no names

1 to 2 marks

What not to write

“12 students in 3 teams of 4 with no sector: $\binom{12}{4}\binom{8}{4}\binom{4}{4}=34{,}650$ splits.”

What to write

“This product numbers the teams; without names, divide by $3!$ : $\frac{34{,}650}{6}=5775$ splits.”

Why: The same split appears once for each of the 3! ways of numbering the teams. With three different sectors, 34,650 becomes right again.

6. Dividing by k! when the places are already told apart

the whole question

What not to write

“4 wells in 4 different rows and 4 different columns of a 4 × 6 plate: order does not matter, so $\frac{P(6,\,4)}{4!}=15$ .”

What to write

“One well per row; the column of A, then of B, of C, of D: $6\times 5\times 4\times 3=360$ choices.”

Why: You divide by k! only if each outcome was produced k! times. Here the row already names each well: each set is produced only once.

7. Losing the sign or the coefficient in the binomial theorem

1 mark

What not to write

“The coefficient of $x$ in $(3x-2)^{4}$ is $\binom{4}{3}\times 3\times 2^{3}=96$ .”

What to write

“The term is $\binom{4}{3}(3x)^{1}(-2)^{3}=4\times 3x\times(-8)=-96x$ : the coefficient is $-96$ .”

Why: The binomial theorem applies to a = 3x and b = −2 as wholes: the coefficient of x and the sign of b are raised to the power with them.

8. Dividing by the number of values instead of the number of equally likely cases

the whole question

What not to write

“The magnetization of 10 spins takes 11 values, so $P(M=0)=\frac{1}{11}$ .”

What to write

“It is the $2^{10}=1024$ configurations that are equally likely: $P(M=0)=\frac{\binom{10}{5}}{1024}=\frac{252}{1024}\approx 0.246$ .”

Why: The formula favourable cases over possible cases requires EQUALLY LIKELY cases. The 11 values are not: M = 0 groups 252 configurations, M = 10 a single one.

Which method to choose

Which formula? Decide on what an outcome is

Write a sentence that describes ONE outcome, then follow the first branch that applies.

If all the objects are placed and some are identical → $\frac{n!}{n_{1}!\cdots n_{r}!}$

Example: 12 bases, 4 A, 3 C, 3 G, 2 T: $\frac{12!}{4!\,3!\,3!\,2!}=277{,}200$
If ordered places, an object can come back → $n^{k}$

Example: 3-digit codes: $10^{3}=1000$
If ordered places, distinct objects → $P(n,k)=\frac{n!}{(n-k)!}$

Example: 4 positions of an autosampler, 6 vials: $P(6,\,4)=360$
If a group, order changes nothing → $\binom{n}{k}$

Example: 4 control wells out of 24: $\binom{24}{4}=10{,}626$
If several groups of the same size, without names → numbered groups, then divide by the number of numberings

Example: 3 teams of 4: $\frac{34{,}650}{3!}=5775$

If no branch applies, split the construction into steps and multiply; check that the number of choices at each step does not depend on the earlier choices.

The words in the question that change the operation

Spot the word that links the conditions.

If “and”, “then”, a sequence of steps → multiply

Example: a row, then 4 wells in that row: $4\times\binom{6}{4}=60$
If “or” between cases that do not overlap → add

Example: exactly 4 or exactly 5 right numbers: $8415+204$
If “or” between cases that overlap → inclusion-exclusion

Example: $10+6-3=13$ forbidden mixtures
If “at least one” → total minus “none”

Example: $\binom{24}{4}-\binom{18}{4}=7566$
If “exactly k” → choose the $k$ , then complete with the others

Example: $\binom{6}{4}\binom{34}{2}=8415$

“At least two”, “at most three”: count the complement if it has fewer cases than the event itself.

How the answer is expected to be written

A marker ticks steps. Here they are in order, with the concluding sentence expected word for word.

Writing up a count

When to use it: Any “how many ...” question, or any probability computed as favourable cases over possible cases.

1 Describe ONE outcome in a sentence: a list, a set, a split.
2 Say when two outcomes are the same: does order matter, can an object come back, can the objects be told apart?
3 Name the model (arrangement, combination, sequence, identical objects) or split into steps, naming the principle used.
4 Write the formula with its letters, then the numbers, then the result.
5 Check: small case, sum of the cases, order of magnitude.

Concluding sentence

“An outcome is a set of 4 wells; two choices that differ only by their order give the same set, so we count combinations: $\binom{24}{4}=10{,}626$ .”

The trap: Writing the number without the modelling sentence: a right answer without justification often loses half the marks.

Marking: Most often, the modelling is worth as much as the calculation.

Proving an identity by double counting

When to use it: “Show that” in front of an equality of binomial coefficients, such as $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ .

1 Choose a concrete set that the left-hand side counts: the configurations of $n$ spins with $k$ up.
2 Split it into families by a simple criterion, for example the orientation of the last spin.
3 Count each family, and justify that they are disjoint and that together they contain the whole set.
4 Conclude with the addition principle: two counts of the same set give the same number.

Concluding sentence

“The two families are disjoint and their union is the set of configurations with $k$ spins up, so $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ .”

The trap: Forgetting to justify “disjoint” and “contain everything”: that is exactly what turns the addition into a proof.

Check before you hand in

Five minutes of checking recover more marks than one more problem started in a hurry.

The small case by hand

Replace the data by tiny numbers and list everything: the formula must give the same count.

Groups of 2 out of {A, B, C, D}: AB, AC, AD, BC, BD, CD, that is 6, and $\binom{4}{2}=6$ . If your formula gives 12, it counts the order.
The sum of the cases gives back the total

When you split into disjoint cases, add them up: you must recover the total counted another way.

Teams of 4 out of 7 biologists and 5 technicians, sorted by number of technicians: $35+175+210+70+5=495=\binom{12}{4}$ .
Arrangements against combinations

Their ratio must be exactly $k!$ ; a ratio that is not a factorial betrays a modelling error.

$\frac{P(24,\,4)}{\binom{24}{4}}=\frac{255{,}024}{10{,}626}=24=4!$
The calculator

TI-83 and TI-84: MATH key, PRB menu, functions nPr and nCr. Casio: OPTN, then PROB. It confirms a calculation, not a model.

10 nCr 4 displays 210 and 10 nPr 4 displays 5040: the ratio $24=4!$ confirms that going from one to the other is indeed the order.

The typical problem, taken apart

A field team with at least one technician

An ecology laboratory has 7 biologists and 5 technicians. For a field mission, a team of 4 people is formed, which must include at least one technician.

a)How many teams can be formed?b)A leader is also designated among the 4 members of the team: how many choices of team with a leader are there?

Step 1

An outcome of a) is a team, that is a SET of 4 people out of 12: order does not matter. With no constraint: $\binom{12}{4}=495$ teams.

Why

The modelling sentence comes first: it chooses the combination and often earns half the marks.

Step 2

“At least one technician”: complement, “no technician”, that is 4 biologists out of 7, $\binom{7}{4}=35$ teams. So $495-35=460$ teams.

Why

The complement has only one case, the event has four (1, 2, 3 or 4 technicians): fewer calculations, fewer risks of counting twice.

Step 3

b) For each team, 4 choices of leader: multiplication principle, $460\times 4=1840$ choices.

Why

The leader creates a role: two identical teams with different leaders are two different outcomes.

Step 4

Check by cases: 1 technician $5\times\binom{7}{3}=175$ , 2 technicians $\binom{5}{2}\binom{7}{2}=210$ , 3 technicians $\binom{5}{3}\times 7=70$ , 4 technicians $\binom{5}{4}=5$ ; total $175+210+70+5=460$ .

Why

Two independent methods that give the same number: that is the safest check of a count.

The conclusion, written out

460 teams with at least one technician can be formed, and 1840 teams with a designated leader.

The classic mistake on this problem: Choosing “the” technician (5 ways), then 3 other people out of 11: $5\times\binom{11}{3}=825$ . Each team is counted as many times as it has technicians: $175+2\times 210+3\times 70+4\times 5=825$ .

Learn by heart

• $P(n,k)=k!\binom{n}{k}$ : choose WHICH objects, then in WHAT ORDER.
• Identical objects: divide $n!$ by the factorials of the groups of identical objects.
• “At least one” = total minus “none”.
• $|A\cup B|=|A|+|B|-|A\cap B|$ : add directly only DISJOINT families.
• $\binom{n}{k}=\binom{n}{n-k}$ , $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ , $\sum_{k=0}^{n}\binom{n}{k}=2^{n}$ , $0!=1$ .
• General term of the binomial theorem: $\binom{n}{k}a^{n-k}b^{k}$ , with $a$ and $b$ taken AS WHOLES, sign included.
• Probability by counting: favourable cases over possible cases, only if the possible cases are EQUALLY LIKELY.

Frequently asked questions

How do you know whether order matters in a counting problem?

Take two outcomes made of the same objects in a different order and ask whether they are the same thing in the situation. A team with no roles, a mixture, a set of marked numbers: same outcome, order does not matter. A ranking, numbered positions, distinct roles: different outcomes, order matters.

What is the difference between an arrangement and a combination?

An arrangement is an ordered list of distinct objects, a combination is a set without order. Each combination of k objects gives k factorial arrangements, one per possible order. The number of combinations is therefore obtained by dividing the number of arrangements by k factorial.

How do you count “at least one” in a counting problem?

Go through the complement: count the outcomes that contain none, then subtract them from the total. The direct calculation, which first designates one element and then completes, counts several times the outcomes that contain several: it is the most frequent error of the chapter.

How do you find a coefficient with the binomial theorem?

Write the general term: the binomial coefficient of n and k, times the first term to the power n minus k, times the second term to the power k, keeping each term whole with its coefficient and its sign. Find the value of k that gives the desired power of x, then compute. A minus sign raised to an odd power stays negative.

What is Pascal's triangle used for in CEGEP probability?

It gives all the binomial coefficients without factorials: each number is the sum of the two numbers above it. It shows the coefficients of the binomial theorem and the number of ways to choose k objects out of n, which is used next for the binomial distribution. Its symmetry and the sum of each row, a power of 2, are quick checks.

Mark this sheet as read or add it to your favourites: a free account, no password, keeps your read sheets and favourites from one visit to the next, tells you which chapter to tackle next and lets you ask for the method or exercise you are missing. Create your space, an email is enough.

Practise it

Corrected exercises: Counting, 201-SN1-RE

A method is proved on a paper, not on a sheet. The set for the same chapter takes each of these traps into a problem, with the solution written out step by step.

11 corrected exercises
110 points
150 minutes

Do the exercises

Something missing from this sheet? A method, a trap, an exercise to practise it, a mistake you spotted: tell me, I read every request.

Sending goes through your free space: that is how I can answer you and tell you when the exercise is added. An email is enough, no password. Create your space. Rather not create an account? Write to me directly.

Previous sheet Descriptive statistics Next sheet Probability and conditional probability

This chapter comes back in

The chapters that build on it, later in the year or in the years that follow.

Probability and conditional probability

© Ahmed Squalli Houssaini. Revision sheet published at www.letuteurscientifique.ca/en/fiches/cegep-sn1-counting. Free for personal and classroom use; republishing it elsewhere requires written permission (legal notice).

Revision sheet: counting (201-SN1-RE)

Choosing the formula with two questions

Legend: the words in the table

The essentials

Arrangement and combination: a single difference, the factor k!

Multiply, add, subtract

Pascal's triangle and the binomial theorem

The mistakes that cost marks

1. Counting a group like a ranking

2. Adding two sets that overlap

3. Counting “at least one” by designating “the” first one

4. Permuting identical objects as if they were distinct

5. Forgetting that the groups have no names

6. Dividing by k! when the places are already told apart

7. Losing the sign or the coefficient in the binomial theorem

8. Dividing by the number of values instead of the number of equally likely cases

Which method to choose

Which formula? Decide on what an outcome is

The words in the question that change the operation

How the answer is expected to be written

Writing up a count

Proving an identity by double counting

Check before you hand in

The typical problem, taken apart

A field team with at least one technician

Learn by heart

Frequently asked questions

How do you know whether order matters in a counting problem?

What is the difference between an arrangement and a combination?

How do you count “at least one” in a counting problem?

How do you find a coefficient with the binomial theorem?

What is Pascal's triangle used for in CEGEP probability?

Corrected exercises: Counting, 201-SN1-RE

This chapter comes back in

See also

Looking for a 201-SN1-RE tutor in Montreal?