• Counting



  • How many 3-bit strings?
    1. How would you make one sequence?
    2. How many different sequences of 3 bits from {0, 1}?
         0                 1
     /       \         /       \
    00       01       10       11
   /  \     /  \     /  \     /  \
 000  001 010  011 100  101 110  111

First Rule of Counting: Product Rule

Objects made by chosing from , then , …, then . Then number of objects if

First Rule Example

  • How many outcomes possible for coin tosses? –>
  • How many 10 digit numbers? –>
  • How many digit base numbers? –> , actually

Functions, Polynomials

How many functions mapping to ?

ways to choose for , ways to choose for

So, such functions

How many polynomials of degree modulo ?

  • ways to choose coefficients, so


How many 10 digits numbers without repeating a digit? Answer:

The number of possible choices for the second number is dependent on the first.

How many different samples of size from numbers without displacement?

Permutation of objects =

One-to-one Functions

How many one-to-one functions from to ?

Counting Without Order

How many poker hands? ?? Not really, because A, K, Q, 10, J of spades are the “same” as 10, J, Q, K, A of spades.

Second Rule of Counting

Second Rule of Counting: If order doesn’t matter, count ordered objects and then divide by number of orderings.

Number of ordering for a poker hand =

So, correct answer is

To choose out of :



How many orderings of “ANAGRAM”?

  • Ordered set: , except for “A”
  • A’s are the same. There’re 3 “A”s, so number of such repeated ones =
  • Answer =

How many orderings of “MISSISSIPPI”?

  • Ordered set:
  • 4 S’s, 4 I’s, 2 P’s, so ordered objects per unordered object


Sample items out of .

Without replacement:

  • If order matters,
  • If order doesn’t matter,

With replacement:

  • If order matters,
  • If order doesn’t matter: not so easy … depends on how many of each item we choose.
    • Different number of unordered elts map to each unordered elt.

Example: Splitting up some money …

How many ways can Bob and Alice split 5 dollars?

Attempt #1:

For each of the 5 dollars pick Bob or Alice, so and divide out order. Does this work??

  • Nope, doesn’t work. Second rule of counting isn’t the best here.

Let’s make the question harder… How many ways can Bob, Alice, and Eve split 5 dollars?

Attempt #2:

* * * * * –––– 5 stars are the 5 dollars

| | * * * * *
| * | * * * *
| * * | * * *

How many different 5 star and 2 bar diagrams? 7 positions in which to place the 2 bars. Answer:

Stars and Bars

Ways to add up numbers to sum to , or “ from with replacement where order doesn’t matter”.

In general, if we have stars and bars, there are positions from which to choose bar positions. i.e.


First rule: sampls with replacement from items: Samples without replacement:

Second rule: when order doesn’t matter

Balls in bins

balls in bins” samples from possibilities”. “indistinguishable balls” “order doesn’t matter” “only one ball in each bin” “without replacement”

Sum Rule

Sum rule: Can sum over disjoint sets

Example 1: Two indistinguishable jokers in 54-card deck. How many 5 card poker hands? No jokers: One joker: Two jokers: So, answer: + +

Example 2: Two distingiushable jokers in 54-card deck. No jokers: . One black/white joker: Both jokers: Answer is actually same as

Combinatorial Proofs

Theorem 1


Proof: Choosing what we choose is the same as choosing what we leave out.

Theorem 2 – Pascal’s Triangle

Pascal’s rule:

Proof: How many size subsets of ? Disjoint sets:

  • Contains first element: then
  • Doesn’t contain first element: then
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

Row : coefficients of

Foil (4 terms) on steroids: terms: choose or from each factor of

Simplify: collect all terms corresponding to . Coefficient of is : choose factors where is in product.

Theorem 3


Proof: Consider size subset where is the first element chosen:

  • Must choose elements from the remaining elements. => such subsets.
  • Add the up to get the total number of subsets

Theorem 4 – Binomial Theorem: x = 1


Proof: How many subsets of {1, …, }? Construct a subset with sequence of choices.

First rule of counting: subsets.

Sum over to get

Simple Inclusion/Exclusion

Sum Rule: For disjoint sets and ,

Inclusion/Exclusion Rule: For any and ,

Example: How many 10-digit phone numbers have 7 as their first or second digit?

= phone numbers with 7 as first digit.

= phone numbers with 7 as first digit.

Key Points

  • Uncertainty doesn’t mean “nothing is known”

Conditional Probability


For events , in the same probability space, such that , the conditional probability of given is:


Bayes Rule

Total Probability Rule

For disjoint sets ,

Hey, kudos for making it this far! Wanted to let you know that if you liked this, you might also like tmux Cheatsheet and Shortcuts.


I'm Bobby Yan, a programmer, music lover, researcher, and a third-year undergraduate student at UC Berkeley majoring in Electrical Engineering and Computer Science. I am currently doing research on robotics, planning, and systems for machine learning at RISELab. In the past, I built IB Notes, a website with useful and concise study guides and notes for IB, and Spanish Vocab Builder, an iOS app to help Spanish learners. See my résumé for more details.

If you enjoyed this article, you should follow me on Twitter or sign up to get an email whenever I write something new:

Share this article with your friends: