Outcomes, Events, and Counting — Probability Theory

Definition 1.1.1. An outcome is one particular possible result of an experiment. The sample space, usually denoted by $$\Omega$,$ is the nonempty set consisting of all possible outcomes. An event is a subset of the sample space. For example, if one die is rolled, the event that an even number appears is

\[A=\lbrace 2,4,6\rbrace \subseteq \Omega.\]

We say that event $$A$$ occurs if the actual outcome belongs to $$A$,$ that is, in set notation,

\[\omega_{\text{actual}}\in A.\]

Thus, if the actual outcome is $$4$,$ then $$A$$ occurs; if the actual outcome is $$5$,$ then $$A$$ does not occur. Accordingly, the statement “event $$A$$ can occur in $$m$$ ways” means that $$A$$ contains $$m$$ possible outcomes. In this case, we write

\[|A|=m.\]

For instance, the number of ways event $A=\lbrace 2,4,6\rbrace$ can occur is $$3$$ because there are three outcomes that make $$A$$ occur.

Definition 1.1.2. Let $\Omega$ be the sample space of an experiment and let $$A$$ and $$B$$ be events. The events $$A$$ and $$B$$ are said to be disjoint or mutually exclusive, if they cannot occur at the same time. In this case, we write

\[A\cap B=\varnothing.\]

The complement of $$A$,$ denoted by $$A^c$,$ is the event that occurs if and only if $$A$$ does not occur. The union of $$A$$ and $$B$,$ denoted by $$A\cup B$,$ is the event that occurs if and only if $$A$$ or $$B$$ occurs. For more than two events, we can also define their union: For $$n$$ events $$A_1,\ldots,A_n$,$ we define the union of them, denoted by

\[A_1\cup \cdots \cup A_n \quad \text{or} \quad \bigcup_{i=1}^n A_i,\]

to occur if and only if at least one of $A_1,\ldots,A_n$ occurs. The intersection of $$A$$ and $$B$,$ denoted by $$A\cap B$,$ is the event that occurs if and only if $$A$$ and $$B$$ occurs. Similarly, we define the intersection of $$n$$ events $$A_1,\ldots,A_n$,$ denoted by

\[A_1\cap \cdots \cap A_n \quad \text{or} \quad \bigcap_{i=1}^n A_i,\]

to occur if and only if all of $A_1,\ldots,A_n$ occur.

Theorem 1.1.3 (De Morgan’s laws). Let $\Omega$ be the sample space of an experiment and let $$A$$ and $$B$$ be events. Then we have

\[(A\cup B)^c = A^c\cap B^c\quad \text{and} \quad (A\cap B)^c = A^c\cup B^c.\]

Proof. The event $(A\cup B)^c$ occurs if and only it $A\cup B$ does not occur, which occurs if and only if $$A$$ or $$B$$ occur. Hence $(A\cup B)^c$ occurs if and only if both $$A$$ and $$B$$ do not occur, which is exactly what $A^c\cap B^c$ means. The event $(A\cap B)^c$ occurs if and only it $A\cap B$ does not occur, which occurs if and only if $$A$$ and $$B$$ occur. Hence $(A\cap B)^c$ occurs if and only if $$A$$ does not occur or $$B$$ does not occur, which is exactly what $A^c\cup B^c$ means. $\square$

Theorem 1.1.4 (Addition rule). Let $A,B\subseteq \Omega$ be disjoint and let $$|A|=m$$ and $$|B|=n$.$ Then

\[|A\cup B|=|A|+|B|=m+n.\]

The addition rule extends to any finite number of events. For pairwise disjoint $A_1,\ldots,A_k\subseteq \Omega$ with $$|A_i|=n_i$,$ we have

\[|A_1\cup \cdots \cup A_k| = n_1 + \cdots + n_k.\]

Definition 1.1.5. A process is an experiment that is completed in successive stages, whose outcome is called the complete outcome. We let $$A$$ be the event of the first stage and $$B$$ the event of the second stage, with $$|A|=m$$ and $$|B|=n$.$ Then the event “ $$A$$ occurs and then $$B$$ occurs” is denoted by $$A\times B$.$

Theorem 1.1.6 (Multiplication rule). Let $$A$$ be the event of the first stage and $$B$$ the event of the second stage, with $$|A|=m$$ and $$|B|=n$.$ Then we have

\[|A\times B|=|A||B|=mn.\]

The multiplication rule also extends to any finite number of stages. If a process consists of $$k$$ successive stages, and each event $$A_i$$ of the $$i$$ th stage has $$n_i$$ possible outcomes, and every tuple in $A_1\times\cdots\times A_k$ is admissible, then this event can occur in $n_1n_2\cdots n_k$ ways:

\[|A_1\times\cdots\times A_k| = n_1n_2\cdots n_k.\]

Definition 1.1.7. For a positive integer $$n$,$ the factorial of $$n$$ is defined by

\[n!=n(n-1)\cdots 2\cdot 1.\]

We also define $$0!=1$.$ To arrange $$n$$ distinct objects in a row, we have $$n$$ choices for the first position, $$n-1$$ choices for the second position, and so on. By the multiplication rule, the number of ways the process of arrangements can be completed is

\[n(n-1)\cdots 2\cdot 1=n!.\]

Definition 1.1.8. Let $$0\leq r\leq n$.$ An $$r$-$ permutation of $$n$$ distinct objects is a complete outcome of a process of selecting $$r$$ objects in order without repetition.

The first object can be chosen in $$n$$ ways, the second in $$n-1$$ ways, and the $$r$$ th in $$n-r+1$$ ways. Hence the number of $$r$-$ permutations is

\[{}_nP_r=n(n-1)\cdots(n-r+1)=\frac{n!}{(n-r)!}.\]

In particular, ${}_nP_n=n!$ and $${}_nP_0=1$.$

Definition 1.1.9. Let $$0\leq r\leq n$.$ An $$r$-$ combination of $$n$$ distinct objects is a complete outcome of a process of selecting $$r$$ objects without repetition in which the order of selection is irrelevant. The number of $$r$-$ combinations is denoted by

\[{}_nC_r \qquad\text{or}\qquad \binom nr.\]

Each $$r$-$ combination gives rise to $$r!$$ different $$r$-$ permutations by arranging its selected objects in every possible order. Therefore,

\[{}_nP_r={}_nC_r\,r!,\]

and consequently

\[{}_nC_r=\frac{ {}_nP_r}{r!}=\frac{n!}{r!(n-r)!}.\]

Since choosing $$r$$ objects to include is equivalent to choosing the remaining $$n-r$$ objects to exclude, we also have

\[{}_nC_r={}_nC_{n-r}.\]

Theorem 1.1.10 (Pascal’s identity). Let $$n$$ and $$r$$ be positive integers with $$r<n$.$ Then

\[\binom nr=\binom{n-1}{r-1}+\binom{n-1}r.\]

Proof. Let $$S$$ be a set of $$n$$ elements and fix an element $$a\in S$.$ The $$r$-$ combinations can be divided into two disjoint classes: those containing $$a$$ and those not containing $$a$.$ An $$r$-$ combination containing $$a$$ is obtained by choosing $$r-1$$ elements from the remaining $$n-1$$ elements, while an $$r$-$ combination not containing $$a$$ is obtained by choosing $$r$$ elements from them. Applying the addition rule, we get the Pascal’s identity. $\square$

Theorem 1.1.11 (Binomial theorem). Let $$n$$ be a nonnegative integer. For any real numbers $$x$$ and $$y$,$

\[(x+y)^n=\sum_{r=0}^n\binom nr x^{n-r}y^r.\]

Proof. Consider the raw expansion of

\[\underbrace{(x+y)(x+y)\cdots(x+y)}_{n\text{ factors}}.\]

From the point of view of the act of expansion, the $$2n$$ occurrences of $$x$$ and $$y$$ in the original expression can be distinguished from one another: each occurrence belongs to a particular original factor. Thus, if necessary, we may mentally label them as

\[(x_1+y_1)(x_2+y_2)\cdots(x_n+y_n),\]

where the subscripts merely record provenance. Now consider one raw term in the fully expanded expression. By the heuristic that multiplication preserves degree, the raw term consists of exactly $$n$$ letters. First, every factor of this raw term must be one of the summands already present in the original expression. Otherwise, some letter not present in the original expression would somehow have been created during expansion, which makes no sense. Second, two different factors of the raw term cannot both have come from the same original factor. If, for example, both $$x_i$$ and $$y_i$$ occurred in the same raw term as contributions from $$(x_i+y_i)$,$ then at some point in the expansion those two summands would have had to be multiplied by each other. But distributive expansion never multiplies the summands within a single factor against one another. Hence, every raw term receives at most one summand from each original factor. Since the raw term contains $$n$$ letters and there are exactly $$n$$ original factors, it follows that it receives exactly one summand from each original factor. We may therefore classify raw terms according to the number of occurrences of $$x$$ they contain. There are $$n+1$$ possible types, corresponding to $0,1,\ldots,n$ occurrences of $$x$.$ For example, consider raw terms containing exactly one $$x$.$ That $$x$$ must have come from one of the $$n$$ original factors. Suppose it came from the $$i$$ th factor. Since every original factor contributes exactly one summand, the $$i$$ th factor must contribute $$x_i$.$ Moreover, because the raw term contains no other $$x$,$ every other factor must contribute its $$y$-$ summand. Thus any such raw term must have the provenance

\[x_i\prod_{j\ne i}y_j.\]

At this point, however, we have shown only that there is a single possible composition for a raw term whose unique $$x$$ comes from the $$i$$ th factor. We have not yet shown that this composition cannot occur twice in the raw expansion. In principle, our previous heuristics alone do not rule out two distinct occurrences of exactly the same raw term. This reveals a further primitive heuristic about the act of distributive expansion: Expansion does not spontaneously duplicate a term occurrence. A given multiplication of two existing term occurrences produces its product occurrence once. Now suppose, for contradiction, that two raw terms with exactly the same provenance

\[x_i\prod_{j\ne i}y_j\]

occurred in the final raw expansion. Trace the two occurrences backward through the expansion. At the last multiplication step, either they came from two distinct identical partial terms, or a single multiplication event somehow produced the same product twice. The latter is ruled out by the no-spontaneous-duplication heuristic. Hence the corresponding partial term must already have occurred twice one stage earlier. Applying the same reasoning repeatedly, we are forced to trace the duplication all the way back to the original expression. Eventually, this would require the same summand occurrence in one of the original factors to have been present twice from the beginning. But each such occurrence appears only once in the original expression. Therefore, a fixed provenance can produce exactly one raw term occurrence. Consequently, for each $$i$,$ there is exactly one raw term containing a single $$x$$ whose $$x$$ comes from the $$i$$ th original factor. Hence there are exactly $$n$$ raw terms of type $$xy^{n-1}$.$ The same reasoning extends immediately. If a raw term is required to contain exactly $$r$$ occurrences of $$x$,$ then once we specify which $$r$$ original factors contribute their $$x$-$ summands, every remaining factor is forced to contribute its $$y$-$ summand. That specification determines one possible provenance, and the no-spontaneous-duplication heuristic guarantees that this provenance occurs exactly once. Thus, counting raw terms with exactly $$r$$ occurrences of $$x$$ reduces to counting the ways to specify which $$r$$ of the $$n$$ original factors contribute $$x$.$ That is, the number of the raw terms of type $x^ry^{n-r}$ is exactly the number of $$r$-$ combinations of $$n$$ distinct objects, $$\binom n r$.$ This proves the binomial theorem. $\square$

Corollary 1.1.12. Let $$n$$ and $$r$$ be positive integers with $$r<n$.$ Then

\[\sum_{r=0}^n\binom nr=2^n.\]

Since every subset of an $$n$-$ element set has a unique cardinality $$r$,$ the sum on the left counts all subsets of the set. Thus an $$n$-$ element set has $$2^n$$ subsets. Furthermore, setting $$x=1$$ and $$y=-1$$ gives

\[\sum_{r=0}^n(-1)^r\binom nr=0.\]