Counting Choices

When is a choice made uniformly at random?

If every outcome is equally likely

What is the probability of an event E?

P(E) = (no. of outcomes for which E occurs)/(total no. of outcomes)

What tells us how many ways there are to choose 1 item from a collection of sets?

The sum rule or the inclusion-exclusion formulae

What tells us how many ways there are to choose 1 item from a set?

The product rule

What is the method of counting choices to find the size of a finite non-empty set X?

• Describe how elements of X can be formed by a sequence of r choices, where

• For each 0 \< i \< r, the number of distinct options available to select from at choice i is precisely a_i and,

• For each x in X, there is precisely one sequence of options which, if selected, result in us forming x

• Having done this, we have |X| = a₁a₂…a_r

• Moreover, if at each of the r choices we select one of the a_i options uniformly at random and independently of the selections made at previous choices, then the element of X formed by these choices is a uniformly random element of X

Let r, n >/ 0 be integers and let S be a set of size n. How many possible ways are there to make r successive choices from S if the order of choices matters and repetition is allowed?

n^r

Let r, n >/ 0 be integers, let S be a set of size n, the order of choices matters and repetition is allowed. What is the probability of each outcome if each choice is made uniformly at random regardless of the outcomes of previous choices?

Each outcome has equal probability of 1/(n^r)

Let r, n >/ 0 be integers and let S be a set of size n. How many possible ways are there to make r successive choices from S if the order of choices matters and repetition is NOT allowed?

For r \< n, there are n!/(n - r)! possible ways

Let r, n >/ 0 be integers, let S be a set of size n, the order of choices matters and repetition is NOT allowed. What is the probability of each outcome if each choice is made uniformly at random from the elements of S which have not yet been chosen?

(n - r)!/n!

Let r, n >/ 0 be integers and let S be a set of size n. How many possible ways are there to make r successive choices from S if r > n and repetition is NOT allowed?

It is not possible to make r successive choices from S

What is a permutation?

A permutation fo a set S of size n is an ordered n-tuple in which each element of S appears once. In other words, the permutations of a set S are the ways to put the elements of S in order (e.g. the permutations of {1, 2, 3} are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 2, 1), (3, 1, 2))

How many permutations does a set S of n elements have?

n!

What are some key identities for counting choices?

(ⁿ_r) = (ⁿ_n-r)

(ⁿ_n) = 1

(ⁿ_n-1) = n

(ⁿ_n-2) = n(n - 1)/2

Let 0 \< r \< n be integers and let S be a set of size n. How many subsets R ⊆ S of size r are there?

(ⁿ_r)

Let 0 \< r \< n be integers and let S be a set of size n. How many possible ways are there to make r successive choices from S if the order of each choice is NOT relevant and repetition is NOT allowed?

(ⁿ_r)

Let r0 \< r \< n be integers, let S be a set of size n, the order of choices does NOT matter and repetition is NOT allowed. What is the probability of each outcome if each choice is made uniformly at random from the elements of S that have not yet been chosen?

Equal probability of 1/(ⁿ_r)

Let 0 \< r \< n be integers and let S be a set of size n. How many possible ways are there to make r successive choices from S if the order of each choice is NOT relevant and repetition is allowed?

(^n+r-1_r)

For natural numbers r and n, what is the number of non-negative integer solutions of X₁ + X₂ + … + X_n = r?

(^n+r-1_r)

Summarise counting results for with order, without order, repetition allowed, repetition not allowed.

• Repetition allowed, order matters: n^r

• Repetition allowed, order doesn’t matter: (^n+r-1_r)

• Repetition not allowed, order matters: n!/(n - r)!

• Repetition not allowed, order doesn’t matter: (ⁿ_r)