Probability & Counting
This guide will introduce some techniques and examples of probability and counting problems that are common in competition math, up to some of the most advanced concepts for high school level. I'm assuming you already have a working knowledge of probability basics.
Sets
Probability can be represented using sets of desired outcomes and total outcomes, and several concepts are derived from this representation.
\subsection{Set Properties}
When the complement 
of an event 
is easier to calculate, it is helpful to use this property to find it instead and subtract from 1 to get )
.
 = 1 - P(\overline{A}) )
Note that the complement or negation of A can be written several ways: 
, etc.\\
These properties can be used to simplify calculating probability:
\paragraph{De Morgan's laws}
} = \overline{A} \cup \overline{B} )
} = \overline{A} \cap \overline{B} )
\paragraph{Distributive laws}
 = (A \cap B) \cup (A \cap C) )
 = (A \cup B) \cap (A \cup C) )
\subsection{Principle of Inclusion-Exclusion}
Two events often have overlap, for example when finding the probability that a drawn card is a heart or a king, one must be sure not to count the king of hearts twice. The Principal of Inclusion-Exclusion is used to account for the overlap.
 = P(A) + P(B) - P(A \cap B) )
This is illustrated by Vinn diagrams. It can also be extended for more than two events. For three events:
 = P(A) + P(B) + P(C) - P(A \cap B) - P(A \cap C) - P(B \cap C) + P(A \cap B \cap C) )
And so on, alternating between addition and subtraction when permutating an increasing number of events.
\subsection{Terminology}
\begin{enumerate}
\item Sample space: the set of all possible outcomes. For rolling two dice, the sample space of the possible sums is {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} . So the size of the sample space is 11, not 36, because some of the outcomes overlap.
\item Disjoint or mutually exclusive: Two events are mutually exclusive if  = 0 )
. In other words, by the Principal of Inclusion-Exclusion,  = P(A) + P(B))
, or in a Vinn diagram, the two events are non-overlapping.
\item Independent: Two events are independent if  = P(A)*P(B))
. This is typically the case unless event A increases or decreases the chances of event B or vice versa. For example the probability of getting a cat is 1/5, and the probability of getting a dog is 1/10; however, the probability of getting both is less than 1/50 because your parents think they will fight. Thus the events are dependent.
\end{enumerate}
\subsection{Subsets}
A quick bit about subsets. A subset 
of set that does not include every element of is called a proper subset and is denoted by 
, whereas if may include all elements of it is denoted by 
and when it does include all elements, it is called the improper subset. \\
The total number of all subsets of a set with a cardinality (number of elements) of 
is 
. This is because each element has two possible states: included in the set or not included. This also illustrates the fact that 
if we were to break down each of the subsets into the number of elements it contains.\\
(MA
Alpha Probability 2005)
Problem A random subset of the 9 smallest natural numbers is chosen. What is the probability that the chosen subset contains the number 5?
\\
Solution Total subsets is
. In subsets containing 5, the state of 5 is determined and each of the remaining elements has two possible states (included or not included), so that's
.
.
Tools
\subsection{Combinations and Permutations}
Problem Three cards are drawn without replacement from a standard deck of playing cards. What is the probability of drawing exactly two aces?
\\
When first doing probability most people are tempted to approach problems like this by dealing with one case at a time and multiplying and adding the results.\\
Probability of drawing ace-ace-not ace: 
Probability of drawing ace-not ace-ace: 
Probability of drawing not ace-ace-ace: 
Probability of drawing ace-ace-not ace or ace-not ace-ace or not ace-ace-ace: 
Combinations and permutations greatly simplify this process. For this problem we will focus on combinations. Instead of doing case work, we will count everything we need and put it in one fraction.
(\textrm{Ways to draw one other card})}{\textrm{Ways to draw three cards}} )
Each represents one combination.\\
Solution Ways to draw two aces: choose two out of four aces,
.
Ways to draw one other card: choose one out of 48 other cards, 
.
Ways to draw three cards: choose three out of 52 cards, 
.
The key is first setting up the problem,and then knowing that choosing 
out of items has a total of 
possibilities. Using the same technique, it isn't much harder to solve much more complex problems.\\
Combinations are used on a set of elements when order doesn't matter or when one specific order must be maintained. Permutations work similarly but they additionally count the number of ways to arrange the elements.
\subsection{Bijection}
Bijection is just a fancy name for a simple concept. If two sets are isomorphic (each unique element in set A can be mapped to a unique element in set B), then counting one set is equivalent to counting another. So you can get really good at counting one type of set, and bijection is what allows you to apply it to all isomorphic sets. In particular, you will learn how to apply the `balls-in-urns' method to many types of problems.
\subsection{Balls-in-urns Formula}
The number of ways to place 
indistinguishable balls into 
distinguishable urns is given by the balls-in-urns formula:
The applications of this formula are numerous. Here are a few examples to illustrate how the formula can be applied.\\
\begin{enumerate}
\item
Problem How many triples
)
of nonnegative integers
,
, and
exist such that
?
\\
Solution Let's imagine we have three urns:
,
, and
. If I have six indistinguishable balls and place them each into one of the three urns, then assigning the number of the balls in each urn to
,
, and
, then the condition
will always be met. This is an example of an isomorphism that is counted using bijection. Now it is a simple use of the formula, with
= 3 and
= 6:
So 28 solutions of triples.
\\
\item What if it asked for positive integers , , and ? Since each urn must have at least one ball, we can immediately place one in each, leaving three balls left over. The remaining three can then be placed in any urn. So 
and 
:
\item (MA Probability and Statistics 1992)
Problem Fifteen chairs are placed in a row. Five people sit in five different randomly chosen chairs. What is the probability that no two people are seated in adjacent chairs?
\\
Solution Let a seated person be represented by
and an empty chair by
. We can start by building up the desired outcome. There must be an empty chair between each of the five seated people:
Now we can stick the remaining six chairs in any location before or after everyone, or between any two people. There are six such locations. The locations are distinguishable because different numbers of empty chairs create unique outcomes, and chairs are indistinguishable. So we have
The total possible outcomes are given by choosing five of the fifteen chairs. So our probability is
\end{enumerate}
\subsection{Conditional Probability}
Conditional probability is given by the formula
 = \frac{P(A \cap B)}{P(B)} )
which is read: the probability of A given B equals the probability of A and B divided by the probability of B. Let's jump right into a problem to show how this works. \\
\begin{enumerate}
\item (MA Theta Probability and Statistics 1996)
Problem There are three boxes. Box 1 contains one red ball and three white balls. Box 2 contains two red balls and two white balls. Box 3 contains three red balls and one white ball. A box is selected at random, then a ball is chosen at random from the selected box. Determine the conditional probability that box 1 was selected, given that a red ball is chosen.
\\
A common approach this type of problem is drawing out a tree for each cases and combining the relevant problems. That's good for learning how it works, and it works the same way. We'll just make this quick by using the formula.\\
Solution is the probability that box 1 was selected.
)
is the probability that a red ball is chosen.
)
is the probability that box 1 is selected and a red ball is chosen.
 = \frac{1}{3} * \frac{1}{4} = \frac{1}{12})
 = \frac{1}{3} * \frac{1}{4} + \frac{1}{3} * \frac{1}{2} + \frac{1}{3} * \frac{3}{4} = \frac{1}{2} )
}{P(B)} = \frac{1}{6} )
\item (MA
Theta Probability 2001)
Problem The probability of event
occurring if event
occurs is
. The probability event
occurs if event
occurs is
. The probability of both events occurring is
. What is the probability of neither event occurring?
\\
This is just our formula mixed up plus some of the set properties from earlier. Note that `the probability of event
occurring if event
occurs' is the same as `the probability of
given
.'
\begin{eqnarray*}
P(\overline{A} \cap \overline{B}) &=& P\overline{(A \cup B)} \\
&=& 1 - P(A \cup B) \\
&=& 1 - (P(A) + P(B) - P(A \cap B)) \\
&=& 1 - (\frac{5}{12} + \frac{7}{12} - \frac{1}{3}) \\
&=& \frac{1}{3}
\end{eqnarray*}
\end{enumerate}
\subsection{Geometric Probability}
This is a problem type that occurs frequently with very little variation.\\
(MA Probability and Statistics 1992)
Problem A taxi arrives at an airport at some time between 1:00 and 1:10. The taxi waits for exactly one minute, then leaves. A man arrives at the airport at some time between 1:00 and 1:10 and waits for 2 minutes for the taxi, then gets on the bus if the taxi does not arrive. What is the probability that the man takes the taxi?
\\
Since this deals with an infinite number of cases (each infinitesimal unit of time) our traditional approaches to probability won't work. A bit of analytic geometry, however, can take care of it.\\
Solution Let
be the man's arrival time and
be the taxi's. If the man arrives first,
, then the taxi must arrive within 2 minutes, so
. Otherwise, the man must arrive within 1 minute of the taxi, so
. When this is graphed it looks like this:
\includegraphics*[viewport=0 0 296 294]{geomprob1}
The shaded region is the time in which the man and the taxi meet, so our probability is that area over the total area of the square.
That's almost exactly how you'll see geometric probability 90\% of the time.
\subsection{Recursion}
Many difficult-sounding probability or counting problems are simple cases of recursion. Recursive sequences give their value in terms of the value of other terms of the same sequence. The Fibonacci sequence is defined recursively: 
. (In fact, many problems have recursive functions that resemble the Fibonacci sequence. A fact to note is that the ratio of consecutive Fibonacci terms, 
, approaches 
as approaches infinity.)\\
Some examples:
\begin{enumerate}
\item (Mathew Crawford)
Problem When Jon Stewart walks up stairs he takes one or two steps at a time. His stepping sequence is not necessarily regular. He might step up one step, then two, then two again, then one, then one, and then two in order to climb up a total of 9 steps. In how many ways can Jon walk up a 14 step stairwell?
\\
Solution Jon will get to an
th step by taking either one or two steps. In other words, he is coming from the (
)th step or the (
)th step. The ways to get to the
th step is just the sum of the ways to get to those steps. Therefore we can define a recursive sequence:
. We also know that there is one way to get to
and two ways (one step at a time twice or two steps at a time once) to get to
. We must set two terms of the sequence explicitly or else it will never take on a numerical value.\\
This is just the 14th term of the Fibonacci sequence: 610.
\item (ARML Team 2006)
Problem An empty down elevator opens its doors on the 6 floor. It will stop at every floor unless it gets stuck. At each of the floors 6 though 2, if there is no one in the elevator, the people waiting flip a coin. If it is heads, one person gets on; if it is tails, no one gets on. At each of the floors 5 through 2, if there are 1 or 2 people in the elevator, the people waiting flip a coin. If it is heads, one person gets on and no one gets off; if it is tails, one person on the elevator gets off and no one gets on. If there are three people in the elevator at any given time, it gets stuck. Compute the probability that the elevator gets stuck before reaching the first floor.
\\
Solution We can create a recursive sequence that's based on both the floor and the number of people in the elevator. Let's call this sequence
)
for the probability of
people being on the elevator after it opens on the
th floor. We are looking for
)
for any
.
 = \frac{1}{2} P(2,f+1))
 = \frac{1}{2} P(1,f+1))
 = \frac{1}{2} P(0,f+1) + \frac{1}{2} P(2,f+1))
 = \frac{1}{2} P(0,f+1) + \frac{1}{2} P(1,f+1))
 = \frac{1}{2})
 = \frac{1}{2})
 = 0)
The elevator can't have 3 people until after opening on floor 4, so we can start there, using the definitions above.
\begin{eqnarray*}
P(3,4) &=& \frac{1}{2} * P(2,5) \\
&=& \frac{1}{2} * \frac{1}{2} * P(1,6) \\
&=& \frac{1}{2} * \frac{1}{2} * \frac{1}{2} \\
&=& \frac{1}{8}
\end{eqnarray*}
\begin{eqnarray*}
P(3,3) &=& \frac{1}{2} * P(2,4) \\
&=& \frac{1}{2} * \frac{1}{2} * P(1,5) \\
&=& \frac{1}{2} * \frac{1}{2} * \left(\frac{1}{2} * P(0,6) + \frac{1}{2} * P(2,6) \right) \\
&=& \frac{1}{2} * \frac{1}{2} * \left(\frac{1}{2} * \frac{1}{2} + \frac{1}{2} * 0 \right)\\
&=& \frac{1}{16}
\end{eqnarray*}
\begin{eqnarray*}
P(3,2) &=& \frac{1}{2} * P(2,3) \\
&=& \frac{1}{2} * \frac{1}{2} * P(1,4) \\
&=& \frac{1}{2} * \frac{1}{2} * \left(\frac{1}{2} * P(0,5) + \frac{1}{2} * P(2,5) \right) \\
&=& \frac{1}{2} * \frac{1}{2} * \left[ \frac{1}{2} * \left(\frac{1}{2} * P(0,6) + \frac{1}{2} * P(1,6) \right) + \frac{1}{2} * \frac{1}{2} * P(1,6) \right]\\
&=& \frac{1}{2} * \frac{1}{2} * \left[\frac{1}{2} \left(\frac{1}{2} *\frac{1}{2} + \frac{1}{2} * \frac{1}{2} \right) + \frac{1}{2} * \frac{1}{2} * \frac{1}{2} \right] \\
&=& \frac{3}{32}
\end{eqnarray*}
The total probability is 
.
\end{enumerate}
Additional Problem Examples
\subsection{}
(MA Theta Individual 2004)
Problem When Mrs. Hiller takes pictures, they turn out with probability 1/5. She wants to take enough pictures so that the probability of at least one turning out is at least 3/4. How few pictures can she take to accomplish this?
\\
Solution The sample space for the probability of
pictures turning out is
Instead of finding P(
) we can simply find 1 - P(
). The probability that a picture does not turn out is 4/5, and the probability that
pictures do not turn out is
^n)
. Therefore we want to find
such that
^n \ge 3/4 \Leftrightarrow (4/5)^n \le 1/4)
.
is the first case where this is true.
\subsection{}
Problem How many five digits numbers are formed with five distinct digits in increasing order?
\\
Solution Imagine the number 123456789, which has all 9 digits in increasing order. Any time we choose 5 digits from this number and keep them in order, it will satisfy the conditions of the problem. For example 12345 or 13579 or 24689. The number of ways to choose 5 of the 9 digits gives the answer.
.
\subsection{}
(MA Theta Probability 2001)
Problem Three points are on vertices of an 8x8 grid of unit squares. Point
is in the upper left corner, point
is three units below and five units to the right of
, and point
is in the lower right corner (eight units below and eight units to the right of point
). If a path is drawn from
to
along the gridlines and can only be drawn going down or to the right, what is the probability it passes through point
?
\\
Conclusion
You are now equipped to tackle just about any competition probability problem. The more difficult problems will involve looking for patterns, trying simpler cases, applying these tools in creative ways, and crossing over into other areas of math (frequently number theory and geometry); it's up to you. Good luck!