Page Description Equation
3 factorial \begin{equation*} n! = \left\{ \begin{array}{ll} \mbox{undefined} & n \le 0 \\ 1 & n=0 \\ n \times (n-1)! & n \gt 0 \end{array} \right. \end{equation*}
6 binomial coefficient \[ \binom{n}{r} = \left\{ \begin{array}{ll} \dfrac{n!}{r!(n-r)!} & \mbox{if } 0 \le r \le n \\ 0 & \mbox{else} \end{array} \right. \]
10 multinomial coefficient, where $n=n_1+\cdots+n_r$ \[ \begin{eqnarray*} \binom{n}{n_1, \ldots, n_r} &=& (n_1, \ldots, n_r)! \\ &=& \dfrac{n_1 + \cdots + n_r}{n_1! \cdots n_r!} \\ &=& \dfrac{n}{n_1! \cdots n_r!} \end{eqnarray*} \]
3 ordered samples with replacement. number of strings of length $r$ from an alphabet of length $n.$ number of ways to put $n$ distinct objects in $r$ distinct groups. \[ n^r \]
3 ordered samples without replacement. number of permutations of $n$ objects taken $r$ at a time. \begin{multline*} P(n,r) =\ _nP_r = \dfrac{n!}{(n-r)!} = r! C(n,r) = r! \binom n r \end{multline*}
3 ordered samples without replacement. number of permutations of $n$ objects. \[ P(n,n) = n! \]
6 unordered samples without replacement. number of combinations of $n$ objects taken $r$ at a time. \[ C(n,r) =\ _nC_r = \binom n r = \dfrac{P(n,r)}{r!} \]
6 computational formula for binomial coefficient. Since $\binom{n}{r} = \binom{n}{n-r}$ and $n-r \gt \dfrac{n}{2}$ when $r \lt \dfrac{n}{2},$ then the second case is equivalent to the first case with $\binom{n}{n-r}$ on the l.h.s. \[ \binom{n}{r} = \left\{ \begin{array}{ll} \dfrac{n(n-1) \cdots (r+1)}{(n-r)!} & r \gt \dfrac{n}{2} \\ \dfrac{n(n-1)\cdots (n-r+1)}{(n-r)!} & r \lt \dfrac{n}{2} \end{array} \right. \]
6 combinatorial identity $0$ \[ 0 = P(n,r) = \binom{n}{r} \mbox{ if } r\lt 0 \mbox{ or } r \gt n \]
6 combinatorial identity $1$ \[ 1 = P(n,0) = \binom{n}{0} = \binom{n}{n} \]
6 combinatorial identity $n$ \[ n = P(n,1) = \binom{n}{1} \]
3 combinatorial identity $n!$ \[ n! = P(n,n) = P(n,n-1) \]
8 combinatorial identity $\mathrm{`}n-r\mbox{'}$ \[ \binom{n}{r} = \binom{n}{n-r} \]
8 combinatorial identity $\mathrm{`}n-1,r\mbox{'}$ \[ \binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r} \]
8 combinatorial identity $\mathrm{`}n,r-1\mbox{'}$ \[ \binom{n}{r} = \binom{n-1}{r-1} + \binom{n}{r-1} \]
8 binomial theorem \[ (x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k} \]
8 multinomial theorem \begin{multline*} (x_1 + \cdots + x_r)^n \\ = \sum_{ \substack{ (n_1, \ldots, n_r) : \\ n_1 + \cdots + n_r = n } } \binom{n}{n_1, \ldots, n_r} x_1^{n_1} \cdots x_r^{n_r} \end{multline*}
9 number of $k$-subsets of set size $n$ \[ \binom{n}{k} \]
9 number of subsets of set size $n$ \[\displaystyle \sum_{k=0}^n \binom{n}{k} = (1 + 1)^n = 2^n \]
13 number of ways to place $n$ identical objects into $r$ groups so that each group has at least one object. For example, the number of distinct positive integer-valued vectors $(x_1, \ldots, x_r)$ satisfying $x_1+\cdots+x_r = n$ \[ \binom{n-1}{r-1} \]
13 number of ways to place $n$ identical objects into $r$ groups where any group can be left empty. For example, the number of distinct non-negative integer-valued vectors $(x_1, \ldots, x_r)$ satisfying $x_1 + \cdots + x_r = n$ \[ \displaystyle \binom{n+r-1}{r-1} \]
Page Description
1 The mathematical theory of counting is formally known as combinatorial analysis .
2

Basic Principle of counting

Suppose that two experiments are to be performed. If the first can result in any of $m$ possible outcomes and if for each of those outcomes there are $n$ possible outcomes of the second experiment, then together there are $mn$ possible outcomes of the two experiments.

2

Basic Principle of Counting Generalized

If $r$ experiments are to be performed such that the first may result in any of $n_1$ possible outcomes, and if for each of these there are $n_2$ possible outcomes of the second experiment, and if for each of the possible outcomes of the first two experiments there are $n_3$ possible outcomes of the third experiment, and if $\ldots,$ then there is a total of $n_1\cdots n_r$ possible outcomes of the $r$ experiments.

2

Guevara Note Basic Principle of Counting, aka the Multiplication Principle.

If $S_i$ is the sample space of the $i\text{th}$ experiment out of $r$ experiments, $1\le i\le r,$ and $|S_i|=n_i,$ then \[ \abs{S_1\times\cdots\times S_r}=n_1\cdots n_r \]

12

Guevara Note Balls in Urns

The number of ways to put $n$ distinguishable balls in $r$ distinguishable urns, $r^n,$ is the same as the number of mappings $\alpha:A\rightarrow B,$ where $\abs{A}=n$ and $\abs{B}=r,$ and $A$ is the set of balls and $B$ urns. Since a ball cannot be in two urns, each ball is put in exactly one urn. When balls are distinguished, two mappings that assign different balls to different urns but the same number of balls to each urn are counted as distinct mappings.

In contrast, the number of ways to place $n$ indistinguishable balls in $r$ distinguishable urns is not given by $r^n,$ and is not the same as the number of mappings from balls to urns. A mapping necessarily distinguishes elements in its domain, so the domain of a mapping cannot be indistinguishable balls.