Mathematics for Computer Science 201-N11 • CEGEP, Montreal

Revision sheet: counting and probability (201-N11)

Counting is the one chapter where the error happens BEFORE the calculation: once the wrong model is chosen, everything that follows is flawless and wrong. This sheet therefore deals with the two questions that fix the model, then with the probability confusions that cost the most.

It is written for CEGEP students in computer science programs in Montreal and for anyone who meets probability from the side of algorithms. The corrected exercise set on the same chapter then puts each reflex to the test.

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.

The thread of the chapter

Before any calculation, two questions: does the ORDER matter, and can we repeat? They decide the model. After that, a single confusion costs marks everywhere, the one between $P(A\mid B)$ and $P(B\mid A)$ .

This chapter is part of 201-N11, Mathematics for Computer Science

What is on this sheet

1. The essentials
2. The mistakes that cost marks
3. Which method to choose
4. How the answer is expected to be written
5. Check before you hand in
6. The typical problem, taken apart
7. Learn by heart
8. Frequently asked questions

Topics covered

Multiplication principle
Permutation
Permutation of all the objects
Combination
Binomial coefficient
Pascal's triangle
Pigeonhole principle
Conditional probability
Law of total probability
Bayes' theorem
Independence
Expected value

The essentials

The four selections, and the two questions that separate them

• MULTIPLICATION PRINCIPLE: $k$ steps offering $n_{1},\ldots,n_{k}$ choices give $n_{1}\times\cdots\times n_{k}$ outcomes, provided that the NUMBER of choices at each step does not depend on the previous ones.
• Selecting $k$ objects out of $n$ , ORDERED WITHOUT replacement: $\frac{n!}{(n-k)!}$ , which is called a permutation.
• ORDERED WITH replacement: $n^{k}$ . UNORDERED WITHOUT replacement: $\binom{n}{k}=\frac{n!}{k!\,(n-k)!}$ . UNORDERED WITH replacement: $\binom{n+k-1}{k}$ .
• The deciding test: if two results differ only in their order, are they the SAME result? If so, it is a combination.

Two questions and a single cell: does the order matter, and can we repeat? The deciding test is this one: if two results differ only in their order, are they the same result?

The multiplication principle breaks down as soon as the number of choices changes depending on what came before. “A four-letter word with distinct letters” stays multiplicative, $26\times 25\times 24\times 23$ ; “a word whose letters are in increasing order” no longer is.

Binomial coefficients: three useful identities and the pigeonhole principle

• PASCAL: $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ , which builds the triangle row by row.
• SYMMETRY: $\binom{n}{k}=\binom{n}{n-k}$ . Choosing $k$ objects means leaving out $n-k$ .
• SUM OF A ROW: $\sum_{k=0}^{n}\binom{n}{k}=2^{n}$ , which is the number of SUBSETS of an $n$ -element set.
• PIGEONHOLE PRINCIPLE: $m$ objects in $n$ pigeonholes put at least $\left\lceil\frac{m}{n}\right\rceil$ objects in the same pigeonhole.

Each number is the sum of the two above it:

\binom{3}{1}+\binom{3}{2}=\binom{4}{2}

3+3=6

; row

n

sums to

2^{n}

The pigeonhole principle is an EXISTENCE statement: it says neither which pigeonhole, nor how many pigeonholes are loaded. A conclusion that names the pigeonhole is false.

Conditional probability, total probability and Bayes

• $P(A\mid B)=\frac{P(A\cap B)}{P(B)}$ , defined only if $P(B)\neq 0$ .
• LAW OF TOTAL PROBABILITY: if the $B_{i}$ form a partition, $P(A)=\sum_{i}P(A\mid B_{i})P(B_{i})$ .
• BAYES: $P(B\mid A)=\frac{P(A\mid B)P(B)}{P(A)}$ , obtained by writing $P(A\cap B)$ in both ways.
• $P(A\mid B)$ and $P(B\mid A)$ have NO reason to be close: on a screening test, the gap runs from $99\%$ to $17\%$ .

The first branch is the cause, the second the observation: the two “positive” paths weigh

0.0099

and

0.0495

, and only the first is a sick person.

On a screening, spam or intrusion-test question, the weighted tree is safer than the formula: two levels, four branches, and you read the counts directly.

Independence, expected value and the collision threshold

• INDEPENDENCE: $P(A\cap B)=P(A)P(B)$ . Two events of nonzero probability cannot be both independent and MUTUALLY EXCLUSIVE.
• EXPECTED VALUE: $E(X)=\sum_{i}x_{i}p_{i}$ . Successful linear search: $\frac{n+1}{2}$ comparisons on average. Waiting for a success of probability $p$ : $\frac{1}{p}$ trials.
• For an “at least one” event, go through the COMPLEMENT: $P(\text{at least one})=1-P(\text{none})$ .
• BIRTHDAYS: the $50\%$ collision threshold among $N$ values is reached at about $1.18\sqrt{N}$ draws.

Rank of the first six: each bar is

\left(\frac{5}{6}\right)^{k-1}\times\frac{1}{6}

, and the average wait is

\frac{1}{p}=6

rolls.

Direct consequence in computing: an $n$ -bit hash resists collisions only up to about $2^{n/2}$ attempts, not $2^{n}$ . This is why a $128$ -bit hash is considered insufficient today.

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. Choosing the model without asking the two questions

the whole question

What not to write

“A committee of $3$ people out of $10$ : $10\times 9\times 8=720$ committees.”

What to write

“A committee is not ordered: two results that differ only in their order are the same committee. So $\binom{10}{3}=\frac{720}{6}=120$ .”

The

3!=6

orderings of one trio are six lists but a single committee:

\binom{10}{3}=\frac{720}{6}=120

Why: The factor $k!$ is exactly the number of possible orderings of the same $k$ elements. Forgetting to divide amounts to counting each committee six times when $k=3$ .

2. Reading a conditional probability backwards

the whole question, and a dangerous conclusion

What not to write

“The test is $99\%$ reliable, so a positive is sick with $99\%$ probability.”

What to write

“ $99\%$ is $P(\text{positive}\mid\text{sick})$ . What we want is $P(\text{sick}\mid\text{positive})$ , which here is $\frac{9.9}{59.4}\approx 17\%$ .”

Out of

1000

people,

10

are sick, of whom

9.9

test positive, and

990

are healthy, of whom

49.5

test positive: among the

59.4

positives, only

17\%

are sick, even though the test is

99\%

reliable.

Why: The two conditional probabilities are about different populations: one relates the positives to the sick, the other the sick to the positives. When the disease is rare, the false positives swamp the true ones.

3. Applying the uniform formula to outcomes that are not equally likely

the whole question

What not to write

“The sum of two dice runs from $2$ to $12$ , that is $11$ outcomes, so $P(7)=\frac{1}{11}$ .”

What to write

“The $11$ sums are not equally likely. Out of the $36$ equally likely pairs, six give $7$ , so $P(7)=\frac{6}{36}=\frac{1}{6}$ .”

The

36

pairs are equally likely, the

11

sums are not: six cells give

7

(green),

P(7)=\frac{6}{36}=\frac{1}{6}

Why: The formula “favourable over possible” holds only on an EQUALLY LIKELY sample space. The right sample space is the one of pairs of dice, not the one of sums.

4. Adding the probabilities of events that overlap

1 to 2 marks, and sometimes a probability greater than

1

What not to write

“ $P(A\cup B)=P(A)+P(B)$ .”

What to write

“ $P(A\cup B)=P(A)+P(B)-P(A\cap B)$ , and you subtract nothing only if $A$ and $B$ are MUTUALLY EXCLUSIVE.”

P(A)+P(B)

counts the intersection twice (red): you subtract it once, unless

A

and

B

are disjoint.

Why: Without the subtraction, the intersection is counted twice. The check is immediate: a result greater than $1$ always signals this mistake.

5. Confusing independent and mutually exclusive

2 marks, and a reversed argument

What not to write

“ $A$ and $B$ are mutually exclusive, so they are independent.”

What to write

“Mutually exclusive means $P(A\cap B)=0$ ; independent means $P(A\cap B)=P(A)P(B)$ . If both probabilities are nonzero, the two properties EXCLUDE each other.”

Disjoint,

A

and

B

exclude each other: knowing

A

makes

B

impossible, so they are DEPENDENT. Independence can only be tested on overlapping events.

Why: Two mutually exclusive events are, on the contrary, strongly linked: knowing that $A$ occurred gives maximal information about $B$ , since $B$ can no longer happen.

6. Handling “at least one” head on

the whole question

What not to write

“At least one six in four rolls: $\frac{1}{6}+\frac{1}{6}+\frac{1}{6}+\frac{1}{6}=\frac{2}{3}$ .”

What to write

“Go through the complement: $P(\text{no six})=\left(\frac{5}{6}\right)^{4}$ , so $P(\text{at least one})=1-\left(\frac{5}{6}\right)^{4}\approx 0.518$ .”

Adding

\frac{1}{6}

per roll (red) exceeds

1

from

7

rolls on; the complement gives

1-\left(\frac{5}{6}\right)^{n}

(green),

0.518

for

4

rolls.

Why: Adding the probabilities of each roll counts several times the outcomes with two sixes or more. The opposite of “at least one” is “none”, and it is computed with a single product.

7. Making the pigeonhole principle say more than it says

1 to 2 marks

What not to write

“Thirteen people, twelve months: January therefore contains at least two birthdays.”

What to write

“There EXISTS a month containing at least two birthdays. The principle does not say which one, nor how many months are in that case.”

Thirteen people, twelve months: the thirteenth lands in a month already taken, but nothing says which. The principle asserts EXISTENCE, never the pigeonhole.

Why: It is a pure existence statement, obtained by contradiction: if every pigeonhole contained at most one object, there would be at most $n$ objects. Nothing in this argument singles out a pigeonhole.

8. Overestimating a hash's resistance to collisions

the whole question, and a false security conclusion

What not to write

“A $128$ -bit hash takes $2^{128}$ attempts to find a collision.”

What to write

“ $2^{128}$ is the cost of a PREIMAGE. For a collision, the birthday paradox brings the cost down to about $2^{64}$ attempts, which is attainable today.”

Why: Looking for a collision means looking for ONE pair among all the possible pairs: their number grows like the square of the number of attempts, which halves the exponent.

Which method to choose

Which counting model, depending on the shape of the result

First describe ONE possible result, then ask whether the order changes it and whether repetitions are allowed. The model follows.

If the steps are independent and the number of choices does not change → multiplication principle, product of the numbers of choices

Example: a plate with $3$ letters and $4$ digits: $26^{3}\times 10^{4}$
If a result is a SEQUENCE, and you cannot repeat → permutation $\frac{n!}{(n-k)!}$

Example: podium of $3$ out of $10$ runners: $10\times 9\times 8=720$
If a result is a SEQUENCE, and you can repeat → $n^{k}$

Example: a password of $8$ characters out of $95$ : $95^{8}$
If a result is a SET, without repetition → combination $\binom{n}{k}$

Example: committee of $3$ out of $10$ : $\binom{10}{3}=120$

The test: if you swap two elements of the result and get the same object, it is a combination.
If a result is a set with repetitions allowed → $\binom{n+k-1}{k}$

Example: $5$ identical balls in $3$ boxes: $\binom{7}{5}=21$
If the number of choices DEPENDS on the previous steps → the multiplication principle fails: split into disjoint cases, or count the complement

Example: words whose letters are in strictly increasing order

When no model is obvious, describe a concrete result on scratch paper, then write a second one that should or should not be counted separately. This comparison settles it in ten seconds.

Which probability formula, depending on the question

The problems of the chapter come down to six forms, recognizable by a word or by a given piece of data.

If finite sample space and visibly equally likely outcomes → $P(A)=\frac{\text{favourable outcomes}}{\text{possible outcomes}}$ , after choosing the right sample space

Example: the $36$ pairs of two dice, not the $11$ sums
If the statement says “at least one” → go through the COMPLEMENT, “none”, which is a simple product

Example: $1-\left(\frac{5}{6}\right)^{4}$
If the statement says “given that”, “among those who” → conditional probability $P(A\mid B)=\frac{P(A\cap B)}{P(B)}$

Example: “among the positives, what proportion is sick”
If the statement gives probabilities according to several exhaustive cases → law of total probability, or a two-level weighted tree

Example: $P(\text{positive})=0.99\times 0.01+0.05\times 0.99$
If the statement gives $P(A\mid B)$ and asks for $P(B\mid A)$ → Bayes, or more safely a weighted tree filled in with COUNTS

Example: from $99\%$ reliability to $17\%$ sick among the positives

Reasoning on $1000$ or $10{,}000$ imaginary individuals avoids every formula error and is just as acceptable to write up.
If the statement asks “on average”, “how many trials” → expected value $E(X)=\sum x_{i}p_{i}$ , or $\frac{1}{p}$ for the wait for a first success

Example: $\frac{n+1}{2}$ comparisons for a successful linear search

Before concluding, check that the result lies between $0$ and $1$ , and that the probabilities of the cases of a partition do add up to $1$ . These two checks catch most of the mistakes of this chapter.

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 counting problem

When to use it: Any question that asks “how many”, and therefore any uniform probability calculation too.

1 Describe ONE possible result concretely: “A committee is a set of $3$ people chosen from the $10$ .”
2 Answer the two questions in writing: “The order does not matter, and you cannot choose the same person twice.”
3 Name the model and apply it: “This is therefore a combination: $\binom{10}{3}$ .”
4 Compute, showing the simplification: “ $\binom{10}{3}=\frac{10\times 9\times 8}{3\times 2\times 1}=120$ .”
5 Check on a tiny case if the model leaves any doubt: “With $3$ people and committees of $2$ , the formula gives $3$ , and you do list $3$ committees.”

Concluding sentence

Since the order does not matter and repetitions are excluded, the number of committees is $\binom{10}{3}=120$ .

The trap: Writing the formula directly without saying why. The marker grades the CHOICE of model more than the calculation, and a correct formula with no justification loses the reasoning mark.

Marking: Usually 1 mark for describing a result, 1 mark for the named and justified model, 1 mark for the calculation.

Writing up a Bayes calculation with counts

When to use it: The statement gives a reliability, a false positive rate and a prevalence, and asks for a “given that” probability.

1 Choose a round imaginary population and ANNOUNCE it: “Let us reason on $1000$ people.”
2 Split according to the first partition: “ $1\%$ are sick, that is $10$ sick people and $990$ healthy people.”
3 Apply the rates to each branch: “ $99\%$ of the $10$ sick are positive, that is $9.9$ ; $5\%$ of the $990$ healthy are too, that is $49.5$ .”
4 Add to get the denominator: “In all, $9.9+49.5=59.4$ people are positive.”
5 Form the requested ratio and interpret it: “Among them, $9.9$ are sick, about $17\%$ .”

Concluding sentence

The probability of being sick given a positive test is $\frac{9.9}{59.4}\approx 0.167$ , about $17\%$ , even though the test is $99\%$ reliable.

The trap: Giving $99\%$ and thinking you have answered. The given datum is $P(\text{positive}\mid\text{sick})$ , the question is about $P(\text{sick}\mid\text{positive})$ : these are two different ratios on two different populations.

Marking: 1 mark for the reference population, 1 mark per correctly weighted branch, 1 mark for the final interpreted ratio.

Check before you hand in

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

Check that the probability is between $0$ and $1$

Reread every probability you wrote. A number above $1$ or a negative one is wrong, and almost always signals a union added without subtracting the intersection.

$P(A)+P(B)=0.6+0.5=1.1$ : impossible. You should have written $0.6+0.5-0.3=0.8$ .
Check a count on a tiny case

Replace $n$ and $k$ by $3$ and $2$ , apply the formula, then LIST by hand. The two numbers must agree.

$\binom{3}{2}=3$ , and you do list $\{a,b\}$ , $\{a,c\}$ , $\{b,c\}$ . A permutation would give $6$ , which counts $\{a,b\}$ and $\{b,a\}$ separately.
Use symmetry and the Pascal sum

Check $\binom{n}{k}=\binom{n}{n-k}$ , and that the sum of a row of the triangle is $2^{n}$ . These two checks catch a factorial error in three seconds.

$\binom{10}{3}=120=\binom{10}{7}$ , and the sum of row $4$ is $1+4+6+4+1=16=2^{4}$ .
Check the consistency of a Bayes result

Compare the probability you obtained with the starting prevalence: the test must RAISE it, without ever pushing it past the announced reliability.

A prevalence of $1\%$ that becomes $17\%$ after a positive test is consistent: it goes up without reaching $99\%$ . A result below $1\%$ or equal to $99\%$ would betray an inversion.

The typical problem, taken apart

The birthday paradox, all the way to hash collisions

In a group of $n$ people, we look for the probability that at least two share a birthday. Ignore leap years and assume the $365$ dates are equally likely.

1. Find the smallest $n$ for which this probability exceeds $\frac{1}{2}$ .

2. Deduce the cost of finding a collision on a $128$ -bit hash.

Five people already form

\binom{5}{2}=10

pairs, each of which may coincide: the number of pairs grows like the square of the number of people.

Step 1

The event “at least two people share a date” has as its opposite “the $n$ dates are all distinct”. We compute the opposite.

Why

“At least two” would split the calculation into a sum of overlapping cases. The opposite, on the other hand, is a single count, and it is the reflex move of the whole chapter.

Step 2

Possible outcomes: each person has $365$ dates, that is $365^{n}$ lists, an ORDERED selection WITH replacement. Outcomes favourable to the opposite: $365\times 364\times\cdots\times(365-n+1)$ , an ordered selection WITHOUT replacement.

Why

Both counts are about the same ordered sample space, which is essential for the quotient to make sense. Mixing an unordered numerator with an ordered denominator is the classic error here.

Step 3

Hence $P(\text{all distinct})=\dfrac{365}{365}\times\dfrac{364}{365}\times\cdots\times\dfrac{365-n+1}{365}$ , a product of $n$ factors.

Why

Writing it as a product of fractions can be computed directly on a calculator and avoids the factorials of $365$ , which overflow any machine.

Step 4

For $n=22$ : $P(\text{all distinct})\approx 0.5243$ , so $P(\text{collision})\approx 0.4757<\frac{1}{2}$ . For $n=23$ : $\approx 0.4927$ , so $P(\text{collision})\approx 0.5073>\frac{1}{2}$ .

Why

You bracket the threshold by testing the two neighbouring values. Giving only $n=23$ without showing that $22$ does not work leaves half of the proof hanging.

Step 5

Interpretation: with $23$ people there are $\binom{23}{2}=253$ PAIRS, and it is this number that decides, not the number of people.

Why

This is the sentence that makes the result non-paradoxical, and it is often the one the statement asks you to explain. The number of pairs grows like the square of the number of people.

Step 6

Generalization: the $50\%$ threshold among $N$ values is reached at about $1.18\sqrt{N}$ draws. Here $1.18\sqrt{365}\approx 22.5$ , consistent with the exact calculation.

Why

The approximate formula serves as a check on the exact calculation, then as a bridge to the next question: it alone carries over to $N=2^{128}$ .

Step 7

For a $128$ -bit hash, $N=2^{128}$ and the threshold is about $\sqrt{2^{128}}=2^{64}$ attempts, not $2^{128}$ .

Why

This factor of two on the exponent is the whole difference between a safe hash and a broken one. It explains why modern hash functions aim for at least $256$ bits.

The conclusion, written out

It takes only $23$ people for the probability of a shared birthday to exceed $\frac{1}{2}$ , because it is the $253$ pairs that count; by the same argument, a $128$ -bit hash resists collisions only up to about $2^{64}$ attempts.

The classic mistake on this problem: Answering $183$ , half of $365$ . That is the answer to another question, the probability that a GIVEN person shares a birthday with someone else. The switch from people to pairs is exactly what the problem tests.

Learn by heart

• Two questions before any calculation: does the ORDER matter, and can we repeat?
• Ordered without replacement $\frac{n!}{(n-k)!}$ ; with replacement $n^{k}$ ; unordered without replacement $\binom{n}{k}$ ; with replacement $\binom{n+k-1}{k}$ .
• $\binom{n}{k}=\binom{n}{n-k}$ and $\sum_{k}\binom{n}{k}=2^{n}$ , which is the number of subsets.
• “At least one” is ALWAYS computed through the complement, “none”.
• $P(A\cup B)=P(A)+P(B)-P(A\cap B)$ : you subtract nothing only if the events are mutually exclusive.
• $P(A\mid B)$ and $P(B\mid A)$ are two different numbers; on a screening test, $99\%$ against $17\%$ .
• Independent is not mutually exclusive: two events of nonzero probability cannot be both.
• Collision threshold among $N$ values: about $1.18\sqrt{N}$ , so $2^{n/2}$ for an $n$ -bit hash.

Frequently asked questions

How do I know whether I need a combination or a permutation?

Describe one result, then swap two of its elements. If you get the same object, the order does not matter and it is a combination; if you get a different object, it is a permutation. A committee is a combination, a podium is a permutation, and the ratio between the two is the number of possible orderings.

Why does a 99 percent reliable test give so many false positives?

Because the disease is rare. Out of a thousand people of whom ten are sick, the test detects nine point nine true positives, but it also declares positive five percent of the nine hundred and ninety healthy people, that is forty-nine point five. Among all the positives, only seventeen percent are therefore really sick.

How do I compute the probability of at least one success?

Go through the complementary event, that of having no success at all, which is computed with a single product. The probability you want is then one minus that product. Adding the probabilities of each trial is wrong, because it counts several times the outcomes that give two successes or more.

Are two mutually exclusive events independent?

No, it is even the opposite. Mutually exclusive means that their intersection is empty, hence of zero probability; independent means that the probability of the intersection is the product of the probabilities. If both probabilities are nonzero, that product cannot be zero: the two properties exclude each other.

Why are twenty-three people enough for a shared birthday?

Because it is not the people that count but the pairs of people, and twenty-three people already form two hundred and fifty-three pairs. The number of pairs grows like the square of the number of people, which makes a collision far more likely than intuition suggests.

Practise it

Corrected exercises: Counting and probability, 201-N11

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 Introduction to graphs and matrices

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

Looking for a 201-N11 tutor in Montreal?

Get in touch for a first session. We work through counting and probability at the level of real assessments, from choosing the right formula all the way to Bayes' theorem.

Book a session WhatsApp

Site by Studio Squalli

Revision sheet: counting and probability (201-N11)

The essentials

The four selections, and the two questions that separate them

Binomial coefficients: three useful identities and the pigeonhole principle

Conditional probability, total probability and Bayes

Independence, expected value and the collision threshold

The mistakes that cost marks

1. Choosing the model without asking the two questions

2. Reading a conditional probability backwards

3. Applying the uniform formula to outcomes that are not equally likely

4. Adding the probabilities of events that overlap

5. Confusing independent and mutually exclusive

6. Handling “at least one” head on

7. Making the pigeonhole principle say more than it says

8. Overestimating a hash's resistance to collisions

Which method to choose

Which counting model, depending on the shape of the result

Which probability formula, depending on the question

How the answer is expected to be written

Writing up a counting problem

Writing up a Bayes calculation with counts

Check before you hand in

The typical problem, taken apart

The birthday paradox, all the way to hash collisions

Learn by heart

Frequently asked questions

How do I know whether I need a combination or a permutation?

Why does a 99 percent reliable test give so many false positives?

How do I compute the probability of at least one success?

Are two mutually exclusive events independent?

Why are twenty-three people enough for a shared birthday?

Corrected exercises: Counting and probability, 201-N11

See also

Looking for a 201-N11 tutor in Montreal?