Handbook · Chapter 3

Counting and Probability

Factorials, permutations and combinations, counting strategies, stars and bars, binomial identities, probability, expected value and inclusion-exclusion.

Book pages 46–59 · 54 entries

3.1 Basic Definitions

open on YouTube

Definition 3.1.1

A factorial is the product of all positive integers less than or equal to a given positive integer. In other words,

n! = n \times (n-1) \times (n-2) \times \cdots \times 1.

Learn it:Definition 1.1.1 · Factorial Section 1.1 Factorials

Book p. 46

Theorem 3.1.2 · Factorials in Combinatorics

The number of ways of arranging $n$ objects in a line is $n!$ .

The number of ways of arranging $n$ objects in a circle, where rotations of the same arrangement aren't considered distinct, is $(n-1)!$ .

The number of ways of arranging $n$ objects in a circle, where rotations and reflections of the same arrangement aren't considered distinct, is

\frac{(n-1)!}{2} \quad (n \ge 3).

Learn it:Theorem 1.2.2 · Number of Orderings of Objects Remark 1.2.3

Book p. 46Checked numerically

Definition 3.1.3

A combination is a possible arrangement in a collection of items where the order of the selection does not matter.

Learn it:Definition 1.5.1 · Combination Section 1.5 Combinations

Book p. 47

Theorem 3.1.4 · Combinations Formula

The number of ways to choose $k$ objects out of a total of $n$ objects is

\binom{n}{k} = \frac{n!}{k! \cdot (n-k)!} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k!}.

Learn it:Theorem 1.5.3 · Combinations Formula

Book p. 47Checked numerically

Remark 3.1.5

The second way of evaluating choosing expressions, $\frac{n(n-1)\cdots(n-k+1)}{k!}$ , is faster for math contests.

Learn it:Theorem 1.5.3 · Combinations Formula

Book p. 47

Remark 3.1.6

Notice that

\binom{n}{k} = \binom{n}{n-k}.

This is true because choosing the $k$ objects you take (left side) is the same as choosing the $n-k$ objects that will not be selected (right side).

Learn it:Remark 1.5.4 Theorem 6.1.1 · Symmetry

Book p. 47Checked numerically

Definition 3.1.7

A permutation is a possible arrangement of objects in a set where the order of the objects matters.

Learn it:Definition 1.2.1 · Permutation Section 1.2 Permutations Basics

Book p. 47

Theorem 3.1.8 · Permutations Formula

The number of ways to order $k$ objects out of $n$ total objects is

{}^{n}P_{k} = \frac{n!}{(n-k)!}.

Learn it:Theorem 1.2.4 · Permutations Formula

Book p. 47Checked numerically

Remark 3.1.9

Usually, the words "permute", "order does matter", etc. imply a permutation, while the words "choose", "select", "order does not matter", etc. imply a combination.

Learn it:Remark 1.5.2

Book p. 48

Theorem 3.1.10

The number of subsets of a set of size $n$ is $2^n$ .

Learn it:Theorem 1.6.1 · Number of Subsets Section 1.6 Subsets

Book p. 48Checked numerically

Remark 3.1.11

We have 2 choices for each element in the set: whether to include or not include the element in our subset. This means that one of our subsets is the empty subset, where we decide not to include any of the elements. If a problem asks you to count subsets, make sure to check whether the empty subset should count.

Learn it:Remark 1.6.2

Book p. 48

3.2 Combinatoric Strategies

open on YouTube

Remark 3.2.1

Complementary counting: count the opposite of what we want and subtract that from the total number of cases. The keyword "at least" signals that complementary counting may help.
Overcounting: count more than what you need, then systematically subtract the parts that do not belong.
Casework: divide the problem into several cases, count the arrangements (or find the probability) in each case, then add them up.

Casework can be a very useful strategy for combinatorics problems, especially when there is no other obvious approach.

Learn it:Concept 3.1.1 · Keep the Cases Few Remark 3.1.2 Section 3.1 Casework

Book p. 49

Remark 3.2.2

Oftentimes, we have to use casework in conjunction with other techniques like complementary counting.

Learn it:Remark 4.0.5 Section 3.1 Casework

Book p. 49

3.3 Advanced Concepts

open on YouTube

Theorem 3.3.1 · Word Rearrangements

The number of ways to order a word is

\frac{n!}{d_1! \times d_2! \times d_3! \times \cdots}

where $n$ is the number of letters and $d_1, d_2, d_3, \ldots$ are the number of times each letter that occurs more than once appears in the word.

Learn it:Theorem 1.4.1 · Word Rearrangements Section 1.4 Word Rearrangements

Book p. 49Checked numerically

Remark 3.3.2

This is not only true for words! The number of ways of arranging objects (or anything else) with repeats is given by the same formula.

Learn it:Remark 1.4.2

Book p. 50

Theorem 3.3.3

The number of rectangles of all sizes in a rectangular grid of size $m \times n$ is

\binom{m+1}{2} \times \binom{n+1}{2}.

Learn it:Theorem 7.2.1 · Rectangles in a Grid Section 7.2 Rectangle Counting

Book p. 50Checked numerically

Remark 3.3.4

Each combination of two horizontal lines and two vertical lines creates a unique rectangle. An $m \times n$ grid has $m+1$ lines one way and $n+1$ lines the other, so we have $\binom{m+1}{2}$ ways to choose two horizontal lines and $\binom{n+1}{2}$ ways to choose two vertical lines.

Learn it:Remark 7.2.2

Book p. 50Checked numerically

Remark 3.3.5

A similar application of combinatorics is the classic problem of how many intersection points the diagonals of a (convex) $n$ -gon have, assuming no three diagonals pass through one interior point. An intersection point is created by 2 diagonals, and each diagonal is determined by 2 vertices, so every intersection point comes from exactly 4 vertices. The number of intersection points is therefore the number of ways to choose 4 points out of $n$ :

\binom{n}{4}.

Learn it:Section 7.1 Triangle Counting

Book p. 51Checked numerically

Theorem 3.3.6 · Stars and Bars

The number of ways to place $n$ identical objects into $k$ distinguishable bins is

\binom{n+k-1}{n}.

Learn it:Theorem 5.1.1 · Stars and Bars Section 5.1 Stars and Bars Fundamentals

Book p. 51Checked numerically

Remark 3.3.7

The reason this is true is that we can think of placing $k-1$ bars among the $n$ objects (stars), which can be arranged in

\binom{n+k-1}{n}

ways. It's important to understand this, because problems may modify stars and bars a little.

Learn it:Section 5.1 Stars and Bars Fundamentals

Book p. 51Checked numerically

Remark 3.3.8

Stars and Bars is extremely useful, and can often be adapted based on situations. For example, if each bin has to have at least 1 object in it, we assign each bin 1 object to start off with and apply our formula with $n-k$ objects and $k$ distinguishable bins.

Learn it:Remark 5.1.2 Concept 5.2.1 · Give the Minimums First Section 5.2 Stars and Bars With Constraints

Book p. 51Checked numerically

Theorem 3.3.9 · Binomial Theorem

For non-negative $n$ ,

(x+y)^n = \binom{n}{0}x^n y^0 + \binom{n}{1}x^{n-1}y + \binom{n}{2}x^{n-2}y^2 + \cdots + \binom{n}{n}x^0 y^n.

Learn it:Theorem 24.0.10 · Binomial Theorem Section 12.1 Binomial Expansions Section 6.1 Basic Identities

Book p. 52Checked numerically

Remark 3.3.10

The binomial theorem has many powerful applications. It's useful for expanding expressions like

(x+y)^n.

Also, if we want to find the value of an expression like

(x+y)^n \pmod{x^k}

(for integers $x$ and $y$ ), we can just expand the last $k$ terms of the binomial expansion: every other term contains $x^k$ or a higher power of $x$ .

Correction

The book prints the modulus as $n^k$ ; it must be $x^k$ (a power of one of the two terms). Modulo $x^k$ the terms with $x^k, x^{k+1}, \ldots$ vanish, leaving the last $k$ terms. Modulo $n^k$ this fails: for $x = 2$ , $y = 1$ , $n = 3$ , $k = 1$ , $(2+1)^3 = 27 \equiv 0 \pmod 3$ , but the last term is $1$ .

Learn it:Theorem 24.0.10 · Binomial Theorem Section 24.0b Euler, Fermat, Wilson and the Binomial Theorem

Book p. 52Checked numerically

Theorem 3.3.11 · Binomial Identity

The binomial identity states that

\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n.

Learn it:Theorem 6.1.2 · Binomial Identity Theorem 1.6.1 · Number of Subsets

Book p. 52Checked numerically

Theorem 3.3.12 · Vandermonde’s Identity

Vandermonde's Identity states that

\binom{n}{0}\binom{m}{m} + \binom{n}{1}\binom{m}{m-1} + \cdots + \binom{n}{m}\binom{m}{0} = \binom{m+n}{n}.

Learn it:Theorem 6.2.1 · Vandermonde's Identity Remark 6.2.2 Section 6.2 Vandermonde's Identity

Book p. 52Checked numerically

Theorem 3.3.13 · Special Case of Vandermonde’s Identity

\sum_{i=0}^{k} \binom{k}{i}^2 = \binom{2k}{k}

Learn it:Theorem 6.2.3 · Special Case of Vandermonde's Identity

Book p. 53Checked numerically

Concept 3.3.14 · Pascal’s Triangle

Pascal's triangle is pictured below (rows $0$ to $10$ ):

\scriptsize\begin{array}{c} 1 \\ 1 \; 1 \\ 1 \; 2 \; 1 \\ 1 \; 3 \; 3 \; 1 \\ 1 \; 4 \; 6 \; 4 \; 1 \\ 1 \; 5 \; 10 \; 10 \; 5 \; 1 \\ 1 \; 6 \; 15 \; 20 \; 15 \; 6 \; 1 \\ 1 \; 7 \; 21 \; 35 \; 35 \; 21 \; 7 \; 1 \\ 1 \; 8 \; 28 \; 56 \; 70 \; 56 \; 28 \; 8 \; 1 \\ 1 \; 9 \; 36 \; 84 \; 126 \; 126 \; 84 \; 36 \; 9 \; 1 \\ 1 \; 10 \; 45 \; 120 \; 210 \; 252 \; 210 \; 120 \; 45 \; 10 \; 1 \end{array}

It can be represented in terms of combinations: row $n$ holds $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$ .

\begin{array}{c} \tbinom{0}{0} \\[4pt] \tbinom{1}{0} \;\, \tbinom{1}{1} \\[4pt] \tbinom{2}{0} \;\, \tbinom{2}{1} \;\, \tbinom{2}{2} \\[4pt] \tbinom{3}{0} \;\, \tbinom{3}{1} \;\, \tbinom{3}{2} \;\, \tbinom{3}{3} \\[4pt] \tbinom{4}{0} \;\, \tbinom{4}{1} \;\, \tbinom{4}{2} \;\, \tbinom{4}{3} \;\, \tbinom{4}{4} \\[4pt] \tbinom{5}{0} \;\, \tbinom{5}{1} \;\, \tbinom{5}{2} \;\, \tbinom{5}{3} \;\, \tbinom{5}{4} \;\, \tbinom{5}{5} \end{array}

Learn it:Concept 6.3.1 · Pascal's Triangle Section 6.3 Pascal's and Hockey Stick Identity

Book p. 53

Theorem 3.3.15 · Pascal’s Identity

Pascal's identity states that

\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}.

Learn it:Theorem 6.3.2 · Pascal's Identity

Book p. 53Checked numerically

Theorem 3.3.16 · Hockey Stick Identity

The Hockey Stick Identity states

\binom{k}{k} + \binom{k+1}{k} + \cdots + \binom{n}{k} = \binom{n+1}{k+1}.

Learn it:Theorem 6.3.3 · Hockey Stick Identity Remark 6.3.6

Book p. 54Checked numerically

Theorem 3.3.17 · Hockey Stick Identity Generalization

\binom{j}{k} + \binom{j+1}{k} + \cdots + \binom{n}{k} = \binom{n+1}{k+1} - \binom{j}{k+1}

Learn it:Theorem 6.3.4 · Hockey Stick Identity Generalization Remark 6.3.5

Book p. 54Checked numerically

Theorem 3.3.18 · Choosing Odd Even Identity

This identity states (for $n \ge 1$ )

\sum_{k=0}^{m} (-1)^k \binom{n}{k} = (-1)^m \binom{n-1}{m}.

Learn it:Theorem 6.1.3 · Choosing Odd Even Identity

Book p. 54Checked numerically

Remark 3.3.19

These identities can be helpful in combinatorics problems, but their applications may not always be straightforward, so a good approach to many combinatorics problems may be to just manipulate expressions.

Learn it:Remark 6.3.7

Book p. 54

Theorem 3.3.20 · Generalized Pigeonhole Principle

If you have at least $nk + 1$ objects to distribute into $k$ groups, at least 1 group will have at least $n + 1$ objects.

Book p. 55Checked numerically

3.4 Probability and Expected Value

open on YouTube

Definition 3.4.1

Probability is the chance something occurs.

Learn it:Definition 2.1.1 · Probability Section 2.1 Probability Basics

Book p. 55

Theorem 3.4.2 · Probability

When all outcomes are equally likely,

\text{probability} = \frac{\text{Total number of Desired Outcomes}}{\text{Total Outcomes}}.

Learn it:Theorem 2.1.2 · Probability

Book p. 55

Definition 3.4.3

Expected value is the weighted average of outcomes.

Learn it:Definition 9.0.1 · Expected Value Section 9.0 Expected Value and Linearity

Book p. 55

Theorem 3.4.4 · Expected Value

The expected value of some event $X$ is

\sum x_i \cdot P(x_i)

where the $x_i$ are the possible values of $X$ and $P(x_i)$ is the probability they occur.

Basically, the expected value is just the sum of the probability of each event happening times the number or amount of that event.

Learn it:Theorem 9.0.2 · Expected Value

Book p. 55

Remark 3.4.5

Oftentimes, in finding the expected value, we can just look for symmetry instead of summing each individual probability times number. For example, to calculate the expected value of a dice roll, rather than evaluating

\frac16 \cdot 1 + \frac16 \cdot 2 + \frac16 \cdot 3 + \frac16 \cdot 4 + \frac16 \cdot 5 + \frac16 \cdot 6 = 3.5

we can see that since all rolls from 1 to 6 are equally likely, the expected value is just the average roll, which is the average of the 2 middle terms, $3.5$ . (See the arithmetic sequences section.)

Learn it:Remark 9.0.3

Book p. 55Checked numerically

Theorem 3.4.6 · Linearity of Expectation

For independent or dependent events,

E(x_1 + x_2 + \cdots + x_n) = E(x_1) + E(x_2) + \cdots + E(x_n).

Basically, the total expected value of $n$ events is just the sum of the expected values of each individual event.

Learn it:Theorem 9.0.4 · Linearity of Expectation

Book p. 56Checked numerically

Remark 3.4.7

This theorem is powerful as it allows us to find the expected value of the individual events rather than of the whole thing at once.

Learn it:Remark 9.0.5

Book p. 56

Definition 3.4.8

Geometric probability is a way to calculate probability by measuring the number of outcomes geometrically, in terms of length, area, or volume. The key to solving geometric probability is to:

Try a few examples for the different cases; make sure to always mark the extreme cases.
Try to figure out the region the shape maps out.
Use geometry to find the area of this region.

Learn it:Definition 8.0.1 · Geometric Probability Section 8.0 Probability as Area Section 8.1 Geometric Probability in 3D

Book p. 56

Remark 3.4.9

Geometric probability can be useful when the number of possible outcomes is infinite.

Learn it:Remark 8.0.2

Book p. 57

Definition 3.4.10

The principle of inclusion and exclusion (PIE) is a counting technique that computes the number of elements that satisfy at least one of several properties while guaranteeing that elements satisfying more than one property are not counted twice.

Learn it:Definition 4.0.1 · Principle of Inclusion and Exclusion Section 4.0 Inclusion and Exclusion

Book p. 57

Definition 3.4.11 · Union Symbol

$|A \cup B|$ is the number of elements in the union of $A$ and $B$ : everything in $A$ or in $B$ (duplicates are only counted once).

Learn it:Definition 4.0.2 · Union Symbol

Book p. 57

Definition 3.4.12 · Intersection Symbol

$|A \cap B|$ is the number of elements in the intersection of $A$ and $B$ (only those elements which are in both sets).

Learn it:Definition 4.0.3 · Intersection Symbol

Book p. 57

Theorem 3.4.13 · Principle of Inclusion Exclusion for 2 Sets

Given two sets $A_1$ and $A_2$ ,

|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|.

Basically, we count the number of possibilities in the 2 "things" and subtract the duplicates.

Learn it:Theorem 4.0.4 · Principle of Inclusion Exclusion for 2 Sets

Book p. 57Checked numerically

Theorem 3.4.14 · Principle of Inclusion Exclusion for 3 Sets

Given three sets $A_1$ , $A_2$ , $A_3$ ,

\begin{aligned}&|A_1 \cup A_2 \cup A_3| \\ &\quad = |A_1| + |A_2| + |A_3| \\ &\qquad - |A_1 \cap A_2| - |A_1 \cap A_3| \\ &\qquad - |A_2 \cap A_3| \\ &\qquad + |A_1 \cap A_2 \cap A_3|.\end{aligned}

In this formula, we count the number of possibilities in the 3 "things", subtract the duplicates in all 3 pairs of sets, and add back the number of elements in all 3 sets.

Learn it:Theorem 4.0.6 · Principle of Inclusion Exclusion for 3 Sets

Book p. 57Checked numerically

Theorem 3.4.15 · Principle of Inclusion Exclusion Generalized

If $A_1, A_2, \ldots, A_n$ are finite sets, then

\begin{aligned}\left|\bigcup_{i=1}^{n} A_i\right| ={}& \sum_{i=1}^{n} |A_i| - \sum_{i<j} |A_i \cap A_j| \\ &+ \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots \\ &+ (-1)^{n-1} |A_1 \cap \cdots \cap A_n|.\end{aligned}

Learn it:Theorem 4.0.7 · Principle of Inclusion Exclusion Generalized

Book p. 58Checked numerically

Concept 3.4.16

A bijection is a one-to-one correspondence between the elements of two sets. Bijections can be useful because they allow you to convert difficult problems into ones that can be more easily calculated. When approaching a difficult problem that may involve bijections, start by trying examples and looking for patterns.

Learn it:Remark 7.4.2

Book p. 58

Concept 3.4.17 · Recursion

Recursion is the process of solving the problem for small values and writing a recurrence equation to iteratively calculate the values for larger values.

Steps to solve recursion problems:

Base cases: manually find the values for small values of $n$ .
Recursion equation: look at the different cases for any general value of $n$ $n$ (for example, whether the last digit is 0 or 1).
- If you are stuck, try a few small cases and look for a pattern.
Iteratively calculate higher values of $n$ until you reach your answer.

Learn it:Definition 10.1.1 · Recursion Concept 10.2.1 · The recursion method Section 10.1 Recursion Fundamentals

Book p. 58

Remark 3.4.18

Note that you can get the answer to many recursion problems by using engineering induction (see the meta-solving section).

Learn it:Remark 10.1.3 · Engineering induction

Book p. 58

Concept 3.4.19 · States

We use states in problems when we are trying to find the probability of "a win" from different positions or turns. When encountering states problems, we use the following steps:

Assign variables to the probabilities of winning from the different positions.
Write equations for the probability of winning from each of these positions in terms of the other states.
Solve your system of equations.

Learn it:Concept 11.0.1 · States Section 11.0 States

Book p. 59

Remark 3.4.20 · Symmetry in States

Always be on the lookout for symmetry in states problems (positions you have an equal probability of winning from) to help simplify your equations.

Learn it:Concept 11.0.2 · Symmetry in States

Book p. 59

Remark 3.4.21

Oftentimes in states problems with a lot of states, you may have to write a state recursion equation.

Learn it:Remark 11.0.3 Concept 11.1.1 · State Tables Section 11.1 States with Recursion

Book p. 59