Counting

CS109

Fall 2026

Review

The Core Probability Toolkit

Review: Last Lecture

Mutually Exclusive Events

Independent Events

make AND easy:

make OR easy:

Story: Ultimate Probability

https://www.youtube.com/watch?v=H2IfTwGisOg

https://www.maikaisogawa.com/ultimate-frisbee-probability/

Practice: Lets do the Frisbee Problem.

• You flip two frisbees. For each frisbee, the probability that it lands “heads” is 0.6. The two frisbees are considered “even” if both frisbees are heads or both frisbees are tails.
• What is the probability that the frisbees are even?

6

End Review

Learning Goals for Today

Learning Goals and Outline

​

1. Step rule of counting
2. Permutations
3. Combinations
4. Probabilities with Equally Likely Outcomes

​

​

Announcements

Announcements

1. Tutorials start this week! You should receive an email from your Tutorial TA about where the first meeting will be. We will have rooms set up by the end of the week.
2. If you have OAE Accomodations, please upload them here: https://forms.gle/uPs1bQMpNAxpDDSu9
3. Pset 1 is due Monday October 5th at 11:00PM PDT
4. We have regular office hours – we are there to help!

Counting!

Counting operations on n distinct objects

Sort, order matters

{perms}

Choose k

{combinations}

Counting Rules

# calculate 20!

math.factorial(20)

# calculate 10 choose 5

math.comb(10, 5)

# give me each possible permutation

itertools.permutations([1,2,3,4])

​

# give me each possible combination

itertools.combinations([1,2,3,4,5], 3)

Counting with Steps

13

Counting with Steps

14

How Many Unique Images?

Each pixel can be one of 17 million distinct colors

(17 million)ⁿ

Sahami, Piech, Yan, Cain, Woodrow, Gregg

Sahami, Piech, Yan, Cain, Woodrow, Gregg

How Many Unique Images?

Each pixel can be one of 17 million distinct colors

(17 million)ⁿ

Sahami, Piech, Yan, Cain, Woodrow, Gregg

Orderings of Letters

• How many letter orderings are possible for the following string?�

CHRIS�

18

🤔

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Orderings of Letters

19

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Orderings of letters

20

Step 1:

Chose first letter

Step 2:

Chose 2nd letter

Step 3:

Chose 3rd letter

Step 4:

Chose 4th letter

Step 5:

Chose 5th letter

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Orderings of letters

21

Step 1:

Chose first letter

Step 2:

Chose 2nd letter

Step 3:

Chose 3rd letter

Step 4:

Chose 4th letter

Step 5:

Chose 5th letter

H

C

S

I

R

(5 options)

(4 options)

(3 options)

(2 options)

(1 option)

Sahami, Piech, Yang, Cain, Woodrow, Gregg

To the code!

22

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Permutations

23

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Unique 6-digit passcodes with six smudges

24

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Unique 6-digit passcodes with six smudges

25

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Summary of Combinatorics

26

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Summary of Combinatorics

27

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Unique Bit Strings

28

1, 0, 1, 0, 0

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Sort n distinct objects

29

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Sort n distinct objects

30

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Sort n distinct objects

31

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Sort n distinct objects

32

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Number of ways to sort coke cans

33

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Sort semi-distinct objects

34

Order 𝑛

distinct objects

n!

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Sort semi-distinct objects

35

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Sort semi-distinct objects

36

Sahami, Piech, Yang, Cain, Woodrow, Gregg

BOBA

37

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Strings

38

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Strings

39

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Strings

40

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Strings

41

Sahami, Piech, Yang, Cain, Woodrow, Gregg

To the code

42

Sahami, Piech, Yang, Cain, Woodrow, Gregg

To the code

43

Sahami, Piech, Yang, Cain, Woodrow, Gregg

General Approach to counting permutations

44

This is called “multiset permutations”

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Sort semi-distinct objects

45

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Sort semi-distinct objects

46

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Sort semi-distinct objects

47

Also:

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Strings

48

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Strings

49

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Summary of Combinatorics

50

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Combinations

Summary of Combinatorics

52

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Combinations with cake

53

Consider the following generative process…

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Combinations with cake

54

1

2

3

4

6

5

7

8

10

9

11

12

13

14

16

15

17

18

20

19

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Combinations with cake

55

1

2

3

4

6

5

7

8

10

9

11

12

13

14

16

15

17

18

19

20

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Combinations with cake

56

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Combinations with cake

57

3. Allow cake group to mingle

k! different permutations lead to the same mingle

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Combinations with cake

58

4. Allow non-cake group to mingle

6

7

8

10

9

11

12

13

14

15

16

17

18

20

19

3. Allow cake group to mingle

k! different permutations lead to the same mingle

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Combinations with cake

59

4. Allow non-cake group to mingle

3. Allow cake group to mingle

k! different permutations lead to the same mingle

(n-k)! different permutations lead to the same mingle

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Combinations

60

3. Overcounted:�any ordering of chosen group is same choice

4. Overcounted:�any ordering of unchosen group is same choice

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Combinations

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Probability textbooks

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Probability textbooks

Sahami, Piech, Yang, Cain, Woodrow, Gregg

How many unique hands of 5 cards are there in a 52 card deck?

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Probabilities with Equally Likely Outcomes

Redux from Day 1:

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Straight Poker Hand (equally likely outcomes)

Consider 5 card poker hands.

• A straight is 5 consecutive rank cards of any suit
• An ace can be the lowest card, and and ace can also the highest card (2 3 4 5 6 7 8 9 10 J Q K A)
• But, straights do not wrap around (e.g., Q K A 2 3 is not a straight)
• There is no inherent ordering, except that all cards must be consecutive (e.g., 2C 3S 4D 5C 6H is the same as 2C 4D 5C 3S 6H)

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Straight Poker Hand (equally likely outcomes)

• The sample space is the number of ways you can choose five cards from 52 (which we just did):

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Straight Poker Hand (equally likely outcomes)

• There are 10 numbered cards to start with (A, 2, 3, 4, 5, 6, 7, 8, 9, 10)
• (alternately, if you are going top to bottom, A, K, Q, J, 10, 9, 8, 7, 6, 5)
• Each of the five cards in the straight have four choices for the suit
• So, the number of events for a straight are:

• Remember, ordering does not matter! We are dealing with sets of cards.

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Straight Poker Hand (equally likely outcomes)

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Straight Poker Hand (equally likely outcomes)

• Poker aficionados will note that in poker there is a difference between a straight and a straight flush, which is a 5-card run in the same suit.
• If we want to just calculate the probability for non-straight flush straights, we have to remove the four possible straight flushes for each of the ten starting cards:

• The probability of getting a straight flush is vanishingly small!

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Calculating probabilities in a real Texas Hold 'Em match?

• If you ever watch Texas Hold 'Em poker on TV, you’ll see that they quickly calculate the odds on-screen to show the likely winners and losers.

• Most of the time (unless they are right at the end, when exact probabilities are simple), the calculations are simulated:
• Randomly deal the remaining cards thousands (or millions) of times
• Evaluate each simulated outcome
• Count wins/ties/losses
• Calculate wins / total simulations, like we did on day 1!

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Super Critical Problem!

To the Course Reader!!

74

Sahami, Piech, Yang, Cain, Woodrow, Gregg

Probability of Exactly k Heads in n Coin Flips

We flip the coin 10 times. Probability of heads is p.

We want to know the probability of getting 4 heads.

​

What is the probability of the outcome below?

Probability of Exactly k Heads in n Coin Flips

We flip the coin 10 times. Probability of heads is p.

We want to know the probability of getting 4 heads.

​

What is the probability of the outcome below?

Probability of Exactly k Heads in n Coin Flips

We flip the coin 10 times. Probability of heads is p.

We want to know the probability of getting 4 heads.

​

What is the probability of the outcome below?

All of the outcomes with exactly 4 heads have the same probability

Probability of Exactly k Heads in n Coin Flips

We flip the coin 10 times. Probability of heads is p.

We want to know the probability of getting 4 heads.

​

What is the probability of the outcome below?

Probability of Exactly k Heads in n Coin Flips

The probability of getting 4 heads,

in any ordering, is the “or” of all these mutually exclusive cases

Each outcome has probability

How many cases are there?

Probability of Exactly k Heads in n Coin Flips

The probability of getting 4 heads,

in any ordering, is the “or” of all these mutually exclusive cases

Each outcome has probability

How many cases are there?

Probability of Exactly k Heads in n Coin Flips

The probability of getting 4 heads,

in any ordering, is the “or” of all these mutually exclusive cases

Each outcome has probability

How many cases are there?

Chip Defect Detection

Chip Defect Detection

• Say the population of Stanford is 17,000 people
• You are friends with 80 people.
• Walk into a room, see 450 random people. Independently.
• What is the probability that you see someone you know?
• Assume you are equally likely to see each person at Stanford

​

​

Serendipity