Probability answers the following question. How frequently should we expect one outcome or another to occur if we repeat some procedure many times? First let’s introduce some terminologies that are frequently used in studying probability:

• Trial: a repeatable procedure such as tossing a coin or drawing a marble from a jar
• Experiment: a sequence of individual trials
• Sample space (of a trial): the set of all possible outcomes
• An event: any set of outcomes, so it is a subset of sample space

Example. Rolling a die is a trial. It’s sample space is the set $\{1,2,3,4,5,6\}$. The subset $\{2,4,6\}$ is an event.

A sample space in general can be an infinite set but we consider only finite sample space here. Let $S$ be a sample space. A probability function $P_r: \wp(S)\longrightarrow\mathbb{R}$ assigns probabilities to events. Any probability function must satisfy the axioms of finite probability:

1. $0\leq P_r(A)\leq 1$ for any event $A$.
2. $P_r(\emptyset)=0$ and $P_r(S)=1$.
3. For any events $A$ and $B$ with $A\cap B=\emptyset$, $$P_r(A\cup B)=P_r(A)+P_r(B)$$

Remark. Because of axiom 1, the codomain of a probability function $P_r$ can be restricted to the unit interval $[0,1]$, i.e. $P_r:\wp(S)\longrightarrow[0,1]$.

Theorem. The probability of an event $A$ not happening is $$P_r(A^c)=1-P_r(A)$$

Proof. It follows from $S=A\dot\cup A^c$ and axiom 3. Here, $\dot\cup$ means disjoint union.

Theorem. Let $A$ and $B$ be events such that $A\subseteq B$. Then $P_r(A)\leq P_r(B)$.

Proof. The set $B$ cam be written as $B=A\dot\cup(B-A)$, thus by axiom 3 $$P_r(B)=P_r(A)+P_r(B-A)\geq P_r(A)$$

This theorem is extended to

Theorem. Let $A_1,A_2,\cdots,A_n$ be events such that $A_i\cap A_j=\emptyset$ for $i\ne j$. Then $$P_r\left(\bigcup A_i\right)=\sum P_r(A_i)$$

Let $A$ and $B$ be two events and assume that $A$ and $B$ are not necessarily disjoint. How do we calculate $P_r(A\cup B)$, i.e. the probability of the event $A$ or $B$ happening? The following theorem answers that.

Theorem. (Inclusion-Exclusion Principle) Let $A$ and $B$ be two events (not necessarily disjoint). Then $$P_r(A\cup B)=P_r(A)+P_r(B)-P_r(A\cap B)$$

Proof. \begin{align*}A&=(A-B)\dot\cup(A\cap B)\\B&=(B-A)\dot\cup(A\cap B)\end{align*} Hence by axiom 3, we have \begin{align*}P_r(A-B)&=P_r(A)-P_r(A\cap B)\\P_r(B-A)&=P_r(B)-P_r(A\cap B)\end{align*} Also $A-B$, $B-A$ and $A\cap B$ are mutually disjoint, so by the previous theorem we have \begin{align*}P_r(A\cup B)&=P_r(A-B)+P_r(B-A)+P(A\cap B)\\&=P_r(A)+P_r(B)-P_r(A\cap B)\end{align*}

Consider a trial with $n$ possible outcomes. Assume that the outcomes are equally likely. Examples of trials with equally likely outcomes include coin tossing, rolling a die, drawing marbles from a jar, etc. Let $S$ be the sample space of a trial with equally likely outcomes. Define a function $P_r: \wp(S)\longrightarrow[0,1]$ by $$P_r(E)=\frac{|E|}{|S|}$$ for event $E$. Then it is straightforward to show that $P_r$ satiesfies axioms 1-3, i.e. it is a probability function.

Example. If a fair coin is flipped 4 times, what is the probability that exactly 2 of the flip’s land heads up?

Solution. $|S|=2^4=16$. Let $E$ be the set of outcomes that contain exactly 2 heads. Then $|E|=\begin{pmatrix}4\\2\end{pmatrix}=6$. Hence, $P_r(E)=\frac{6}{16}=\frac{3}{8}$.

Example. The Gambler’s Fallacy. Let $n$ be a large number. If a coin is flipped $n$ times and comes up heads the first $n-1$ times, what is the probability that the $n$th flip comes up head?

Solution. Although your intuition might tell you that the coin is due to come up tail, the coin doesn’t remember the history of previous outcomes. The probability is still $\frac{1}{2}$.

When the knowledge of whether an event $A$ occurred gives no information about whether another event $B$ occurred, $A$ and $B$ are said to be independent. Mathematically, the events $A$ and $B$ are independent if and only if $$P_r(A\cap B)=P_r(A)P_r(B)$$

Example. Let us consider $n=4$ case in the previous example. Let $A$ be the event that a coin is flipped 4 times and comes up heads first three times. Let $B$ be the event that a coin is flipped 4 times and comes up head last time. We show that $A$ and $B$ are independent events. Then \begin{align*}A&=\{HHHH,HHHT\}\\B&=\{HHHH,HHTH,HTHH,THHH,THTH,TTHH,TTTH\}\end{align*} Hence, \begin{align*}P_r(A\cap B)&=\frac{|A\cap B|}{|S|}=\frac{1}{16}\\P_r(A)P_r(B)&=\frac{|A|}{|S|}\frac{|B|}{|S|}=\frac{2}{16}\frac{8}{16}=\frac{1}{16}\end{align*} Since $P_r(A\cap B)=P_r(A)P_r(B)$, $A$ and $B$ are independent.

Example. Suppose three marbles are drawn from a jar containing six red marbles and four blue marbles. Let us consider the following events.

• $A$: The three marbles are not all the same color.
• $B$: The first marble drawn is red.

Are $A$ and $B$ independent?

Solution. The number of ways of drawing 3 marbles of the same color is $$\begin{pmatrix}6\\3\end{pmatrix}+\begin{pmatrix}4\\3\end{pmatrix}=24$$ So the number of ways of choosing 3 marbles that are not all the same color, i.e. $|A|=\begin{pmatrix}10\\3\end{pmatrix}-24=120-24=96$. Hence, $P_r(A)=\frac{96}{120}=\frac{4}{5}$. The probability that the first marble drawn is red is just $P_r(B)=\frac{6}{10}=\frac{3}{5}$. To calculate $P_r(A\cap B)$, since first marble is drawn red, the remaining two marbles drawn must contain at least one blue marble. There are $\begin{pmatrix}5\\2\end{pmatrix}=10$ ways of getting 2 more red marbles and so there are $\begin{pmatrix}9\\2\end{pmatrix}-10=36-10=26$ ways of drawing at least one blue marble. Therefore, $P_r(A\cap B)=\frac{6}{10}\frac{26}{36}=\frac{13}{30}$. On the other hand, $P_r(A)P_r(B)=\frac{4}{5}\frac{3}{5}=\frac{12}{25}$. Since $P_r(A\cap B)\ne P_r(A)P_r(B)$, the events $A$ and $B$ are not independent.

References.

[1] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019

Let us begin with an example.

Example 1. A jar contains 11 marbles. In how many ways can they be placed in four boxes, with 3 marbles in the first box, 4 marbles in the second box, 2 marbles in the third box, and the 2 remaining marbles in the fourth box?

Solution. The total number of outcomes is $$\begin{pmatrix}11\\3\end{pmatrix}\cdot \begin{pmatrix}8\\4\end{pmatrix}\cdot \begin{pmatrix}4\\2\end{pmatrix}\cdot \begin{pmatrix}2\\2\end{pmatrix}=\frac{11!}{3!8!}\cdot\frac{8!}{4!4!}\cdot\frac{4!}{2!2!}\cdot\frac{2!}{2!0!}=\frac{11!}{3!4!2!2!}=69,300$$

This example can be generalized to the following question. A set of $n$ distinct items is to be divided into $r$ distinct groups of respective sizes $n_1, n_2, \cdots, n_r$ such that $\sum_{i=1}^r n_i=n$. How many different divisions are possible? There are $\begin{pmatrix}n\\n_1\end{pmatrix}$ possible choices for the first group, there are $\begin{pmatrix}n-n_1\\n_2\end{pmatrix}$ possible choices for the second group, there are $\begin{pmatrix}n-n_1-n_2\\n_3\end{pmatrix}$ possible choices for the third group, …, there are $\begin{pmatrix}n-n_1-n_2-\cdots-n_{r-1}\\n_r\end{pmatrix}$ possible choices for the $r$-th group. Therefore the total number of coutcomes is \begin{align*}\begin{pmatrix}n\\n_1\end{pmatrix}\begin{pmatrix}n-n_1\\n_2\end{pmatrix}\begin{pmatrix}n-n_1-n_2\\n_3\end{pmatrix}\cdots\begin{pmatrix}n-n_1-n_2-\cdots -n_{r-1}\\n_r\end{pmatrix}\\=\frac{n!}{(n-n_1)!n_1!}\frac{(n-n_1)!}{(n-n_1-n_2)!n_2!}\cdots\frac{(n-n_1-n_2\cdots-n_{r-1})!}{0!n_r!}\\=\frac{n!}{n_1!n_2!\cdots n_r!}\end{align*}

The number of divisions of $n$ distinct items into $r$ distinct groups of respective sizes $n_1,n_2,\cdots,n_r$ is denoted by $\begin{pmatrix}n\\n_1,n_2,\cdots,n_r\end{pmatrix}$. That is, \begin{equation}\label{eq:multcoeff}\begin{pmatrix}n\\n_1,n_2,\cdots,n_r\end{pmatrix}=\frac{n!}{n_1!n_2!\cdots n_r!}\end{equation} where $n=n_1+n_2+\cdots+n_r$.

Example 2. A police department in a small city consists of 10 officers. If the department policy is to have 5 of the officers patrolling the streets, 2 of the officers working full time at the station, and 3 of the officers on reserve at the station, how many different divisions of the 10 offices into the 3 groups are possible?

Solution. $\frac{10!}{5!2!3!}=2,520$.

Example 3. Ten children are to be divided into an A team and a B team of 5 each. The A team and a B team of 5 each. The A team will play in one league and the B team in another. How many different divisions are possible?

Solution. $\frac{10!}{5!5!}=252$.

Example 4. In order to play a game of basketball, 10 children at a playground divide themselves into two teams of 5 each. How many different divisions are possible?

Solution. Compare Example 4 with Example 3. In this example, the order of the two teams is irrelevant. Hence, the answer is $\frac{\frac{10!}{5!5!}}{2!}=126$.

Let us consider more about the cases like Example 4. In Example 1, it was implicitly indicated that the four boxes are distinguishable as they are specified as the first box, the second box, and so on so forth. For example, if we assume that the marbles were labeled 1 through 11, the following two would be two different outcomes: \begin{align*}\{1,2,3\},\{4,5,6,7\},\{8,9\},\{10,11\}\\\{1,2,3\},\{4,5,6,7\},\{10,11\},\{8,9\}\end{align*} because the marbles placed in the third and the fourth boxed are swapped in the second row. But what if these boxes were indistinguishable? Then the two outcomes would’ve been regarded as the same.

Example. A jar contains 11 marbles. In how many ways can they be placed in 4 unmarked boxes, with 1 box containing 3 marbles, 1 box containing 4 marbles, and 2 boxes containing 2 marbles each?

Solution. We first choose the marbles for each box as in the case boxes are ordered just like Example 1: $$\begin{pmatrix}11\\3\end{pmatrix}\cdot\begin{pmatrix}8\\4\end{pmatrix}\cdot\begin{pmatrix}4\\2\end{pmatrix}\cdot\begin{pmatrix}2\\2\end{pmatrix}=\frac{11!}{3!4!2!2!}$$ Now, any boxes that have the same number of marbles can be swapped with each other. So we will have to divide the above total by $1!1!2!$ to get the final result: $$\frac{\frac{11!}{3!4!2!2!}}{1!1!2!}=34,650$$

The formula in \eqref{eq:multcoeff} is called multinomial coefficient as it is related to the Multinomial Theorem.

Theorem. \begin{equation}\label{eq:multinomial}(x_1+x_2+\cdots+x_r)^n=\sum_{(n_1,\cdots,n_r)\\n_1+n_2+\cdots+n_r=n}\begin{pmatrix}n\\n_1,n_2,\cdots,n_r\end{pmatrix}x_1^{n_1}x_2^{n_2}\cdots x_r^{n_r}\end{equation}

Example. Expand $(x_1+x_2+x_3)^2$.

Solution. There are 6 partitions of 2: \begin{align*}2&=2+0+0=0+2+0=0+0+2\\&=1+1+0=1+0+1=0+1+1\end{align*} Thus, \begin{align*}(x_1+x_2+x_3)^2&=\begin{pmatrix}2\\2,0,0\end{pmatrix}x_1^2x_2^0x_3^0+\begin{pmatrix}2\\0,2,0\end{pmatrix}x_1^0x_2^2x_3^0+\begin{pmatrix}2\\0,0,2\end{pmatrix}x_1^0x_2^0x_3^2\\&+\begin{pmatrix}2\\1,1,0\end{pmatrix}x_1^1x_2^1x_3^0+\begin{pmatrix}2\\1,0,1\end{pmatrix}x_1^1x_2^0x_3^1+\begin{pmatrix}2\\0,1,1\end{pmatrix}x_1^0x_2^1x_3^1\\&=x^1_2+x_2^2+x_3^2+2x_1x_2+2x_1x_3+2x_2x_3\end{align*}

By the basic principle of counting, there are $r^n$ possible outcomes when $n$ distinguishable balls are to be distributed into $r$ distinguishable urns. What is the balls are indistinguishable? Let us consider a vector $(x_1,x_2,\cdots,x_r)$, where $x_i$ represents the number of balls that are distributed into the $i$-th urn. Then the problem boils down to counting the number of vectors $(x_1,x_2,\cdots,x_r)$ such that the $x_i$’s are nonnegative, integer-valued and $x_1+x_2+\cdots+x_r=n$. First let us consider the number of such vectors with the $x_i$’s being all positive integer-valued. Imagine that we lined up $n$ balls and divide them into $r$ nonempty groups. For $n=8$ and $r=3$, the following is an example of the divisions: ooo|ooo|oo. There are 7 spaces between 8 balls so the number of all possible 3 such divisions is $\begin{pmatrix}7\\2\end{pmatrix}$. By a similar arugument, we obtain:

Proposition 1. There are $\begin{pmatrix}n-1\\r-1\end{pmatrix}$ distinct vectors $(x_1,\cdots,x_r)$ such that the $x_i$’s are all positive, integer-valued and $x_1+\cdots+x_r=n$.

Now suppose that the $x_i$’s are nonnegative (positive or zero). Let $y_i=x_i+1$. Then $y_i>0$ and $y_1+y_2+\cdots+y_r=n+r$. It follows from the above proposition that:

Proposition 2. There are $\begin{pmatrix}n+r-1\\r-1\end{pmatrix}$ distinct vectors $(x_1,\cdots,x_r)$ such that the $x_i$’s are nonnegative, integer-valued and $x_1+\cdots+x_r=n$.

Example. How many distinct solutions of $x_1+x_2=3$, where $x_1$ and $x_2$ are nonnegative and integer-valued, are possible?

Solution. $\begin{pmatrix}3+2-1\\2-1\end{pmatrix}=4$. In fact, they are $(0,3)$, $(1,2)$, $(2,1)$, $(3,0)$.

Example. An investor has \$20,000 to invest among 4 possible investments. Each investment must be in units of a thousand dollars. If the total $20,000 is to be invested, how many different investment strategies are possible? What if not all the money need to be invested?

Solution. Let $x_i$ denote the number of thousands in dollars invested in ivestment number $i$. Then $$x_1+x_2+x_3+x_4=20,\ x_i\geq 0$$ and there are $\begin{pmatrix}20+4-1\\4-1\end{pmatrix}=1,771$ possible investment strategies. If not all the money need to be invested, let $x_5$ denote the amount kept in reserve. Now, a strategy is a vector $(x_1,x_2,x_3,x_4,x_5)$ such that the $x_i$’s are nonnegative, integer-valued and $x_1+x_2+x_3+x_4+x_5=20$. Hence, there are $\begin{pmatrix}20+5-1\\5-1\end{pmatrix}=10,626$ possible strategies.

Remark. Using proposition 2, we can also answer how many terms there are in the multinomial expansion of $(x_1+x_2+\cdots+x_r)^n$. In the multinomial expansion formula \eqref{eq:multinomial}, $n_1+n_2+\cdots+n_r=n$. Hence there are $\begin{pmatrix}n+r-1\\r-1\end{pmatrix}$ terms.

References: Not in particular order.

[1] Applied Discrete Structures, Al Doerr and Ken Levasseur. This book is available for free under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.

[2] A First Course in Probability, Sheldon Ross, 5th Edition, Prentice-Hall, 1998

[3] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019

In my previous note here, I mentioned that a combination is an arrangement of things with no order. To further discuss combinations let us begin with the following example.

Example. How many different ways are there to permute three letters from $A=\{a,b,c,d\}$?

Solution. $P(4.3)=\frac{4!}{(4-3)!}=4!=24$.

Example. How many ways can we select three letters from $A=\{a,b,c,d\}$?

Solution. Note that with this question we are not interested in the order of arranging three letters but are only interested in selecting three letters. For each choice of a group of three letters, there are $3!$ permutations among the letters we won’t distinguish. Hence, the answer is $$\frac{P(4,3)}{3!}=\frac{4!}{3!(4-3)!}=4$$ Those four selections are \begin{array}{c}abc\\abd\\acd\\bcd\end{array}

The number of selecting $r$ elements from a set of $n$ elements, $0\leq r\leq n$ is denoted by $\begin{pmatrix}n\\r\end{pmatrix}$, $C(n,r)$ or ${}_nC_r$ and by using a similar argument to the one we made in the above example, we obtain \begin{equation}\label{eq:comb}\begin{pmatrix}n\\r\end{pmatrix}=\frac{n!}{r!(n-r)!}\end{equation} $\begin{pmatrix}n\\r\end{pmatrix}$ is called binomial coefficient for a good reason which will be mentioned later. The sage command for calculating $\begin{pmatrix}n\\r\end{pmatrix}$ is binomial(n,r).

Note that the formula \eqref{eq:comb} is symmetrical, meaning the number of selecting $r$ elements from $n$ elements or the number of selecting $n-r$ elements from $n$ elements are the same: $$\begin{pmatrix}n\\r\end{pmatrix}=\frac{n!}{r!(n-r)!}=\frac{n!}{(n-r)!r!}=\frac{n!}{(n-r)!(n-(n-r))!}=\begin{pmatrix}n\\n-r\end{pmatrix}$$ This can be easily understood without working through the algebra above: the number of selecting $r$ elements from $n$ elements is the same as the number of not selecting $n-r$ elements from $n$ elements.

Example. A committee of 3 is to be formed from a club of 20 people. How many different committees are possible?

Solution. $\begin{pmatrix}20\\3\end{pmatrix}=\frac{20!}{3!17!}=\frac{20\cdot 19\cdot 18}{3\cdot 2\cdot 1}=1140$.

Example. In the above example, if the treasurer must be on the committee, the answer changes to $\begin{pmatrix}19\\2\end{pmatrix}=171$. If we further require that a chairperson other than the treasurer be selected, then there are $\begin{pmatrix}19\\2\end{pmatrix}\cdot 2=342$ different committees. If the treasure can be a chairperson, there are $\begin{pmatrix}19\\2\end{pmatrix}\cdot 3=513$ different committees.

Example. Assume that a coin is tossed 5 times. In how many ways can three heads be obtained?

Solution. $\begin{pmatrix}5\\3\end{pmatrix}=\frac{5!}{2!3!}=10$.

Example. When a fair coin is tossed 5 times, how many ways can we possibly observe?

Solution. There are 6 different cases: when we observe 5 heads, 4 heads, 3 heads, 2 heads, 1 head, or 0 head (i.e. all 5 tails). Hence there are $$\begin{pmatrix}5\\5\end{pmatrix}+\begin{pmatrix}5\\4\end{pmatrix}+\begin{pmatrix}5\\3\end{pmatrix}+\begin{pmatrix}5\\2\end{pmatrix}+\begin{pmatrix}5\\1\end{pmatrix}+\begin{pmatrix}5\\0\end{pmatrix}=1+5+10+10+5+1=32$$ Or more simply, for each coin toss, there are two possible outcomes (head or tail). So by the basic principle of counting there are $2^5=32$ possible outcomes from 5 coin tosses.

Example. From a group of 5 women and 7 men, how many different committees consisting of 2 women and 3 men can be formed? What if 2 of the men are feuding and refused to serve on the committee together?

Solution. There can be $\begin{pmatrix}5\\2\end{pmatrix}\begin{pmatrix}7\\3\end{pmatrix}=350$ different committees consisting of 2 women and 3 men. If two men refuse to serve on the committee together, we can either include only one of the two men in the committee or neither of the two men in the committee. Hence, in this case we have $\begin{pmatrix}2\\0\end{pmatrix}\begin{pmatrix}5\\3\end{pmatrix}+\begin{pmatrix}2\\1\end{pmatrix}\begin{pmatrix}5\\2\end{pmatrix}=30$ different groups of men not containing both of the two feuding men. Since there are $\begin{pmatrix}5\\2\end{pmatrix}$ different ways to choose the two women, it follows that there are $30\begin{pmatrix}5\\2\end{pmatrix}=300$ possible committees.

Example. Consider a set of $n$ antennas of which $m$ are defective and $n-m$ are functional. Assume that the functional and the defective antennas are not distinguishable. How many linear orderings are there in which no two defectives are consecutive?

Solution. Imagine that the $n-m$ functional antennas are lined up. Since no two defective antennas are consecutive, the spaces between functional antennas must contains at most one defective antennas. There are $n-m+1$ possible positions for defective antennas. Hence, there are $\begin{pmatrix}n-m+1\\m\end{pmatrix}$ possible linear orderings.

Lemma. \begin{equation}\label{eq:combidentity}\begin{pmatrix}n\\r\end{pmatrix}=\begin{pmatrix}n-1\\r-1\end{pmatrix}+\begin{pmatrix}n-1\\r\end{pmatrix}\end{equation} where $1\leq r\leq n$.

Proof. Consider a group of $n$ objects and fix attention on a particular object. Let us call it object 1. There are then $\begin{pmatrix}n-1\\r-1\end{pmatrix}$ groups of size $r$ that contain object 1. There are also $\begin{pmatrix}n-1\\r\end{pmatrix}$ groups of size $r$ that do not contain object 1. Hence we obtain the identity in \eqref{eq:combidentity}.

Theorem. (The Binomial Theorem) \begin{equation}\label{eq:binomthm}(x+y)^n=\sum_{r=0}^n\begin{pmatrix}n\\r\end{pmatrix}x^ry^{n-r}\end{equation}

The binomial theorem \eqref{eq:binomthm} can be proved by mathematical induction along with the identity in \eqref{eq:combidentity}. I will leave details of proof for readers.

Example. Expand $(x+y)^3$.

Solution. \begin{align*}(x+y)^3&=\begin{pmatrix}3\\0\end{pmatrix}x^0y^3+\begin{pmatrix}3\\1\end{pmatrix}x^1y^2+\begin{pmatrix}3\\2\end{pmatrix}x^2y^1+\begin{pmatrix}3\\3\end{pmatrix}x^3y^0\\&=y^3+3xy^2+3x^2y+x^3\end{align*}

The example below gives an alternative proof to Power Set Cardinality Theorem we discussed here.

Example. How many subsets are there of a set consisting of $n$ elements?

Solution. There are $\begin{pmatrix}n\\r\end{pmatrix}$ subsets of size $r$, so the answer is \begin{equation}\label{eq:binom}\sum_{r=0}^n\begin{pmatrix}n\\r\end{pmatrix}=(1+1)^n=2^n\end{equation}

References: Not in particular order.

[1] Applied Discrete Structures, Al Doerr and Ken Levasseur. This book is available for free under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.

[2] A First Course in Probability, Sheldon Ross, 5th Edition, Prentice-Hall, 1998

[3] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019

There are two particular types of counting of interest in combinatorics. One is a permutation and the other is a combination. A permutation is ordering things without repeats. A combination is arranging things without order. In this note, we study permutations and we will discuss combinations in the following note. Let us begin with an example.

Example. How many different ways can we order the three different elements of $A=\{a,b,c\}$?

Solution. We have three choices for position 1. We have two choices for position 2. And we have 1 choice for position 3. Hence, by the basic principle of counting there are $3\cdot 2\cdot 1=6$ different ways of ordering the three letters. In fact, they are \begin{array}{cc}abc & acb\\bca & bac\\cab & cba\end{array}

The above example can be generalized to ordering elements from a set of $n$ elements. By a similar account, there are $n$ choices for position 1, there are $n-1$ choices for position 2, there are $n-2$ choices for position 3, …, there is one choice for position $n$. Hence, there are $$n!:=n(n-1)(n-2)\cdots3\cdot 2\cdot 1$$ different permutations on the set of $n$ elements. The symbol $n!$ is called $n$ factorial. We define $0!=1$ for an obvious reason which will be mentioned later. Note that $n!$ is also the number of bijective (one-to-one and onto) maps from $\{1,2,\cdots,n\}$ to itself. The sage command for calculating $n!$ is factorial(n).

Example. A class in probability theory consists of 6 men and 4 women. An exam is given and students are ranked according to their performance. Assume that no students received the same score.

1. How many different rankings are possible?
2. If the men are ranked just among themselves and the women among themselves, how many different rankings are possible?

Solution.

1. $10!=3,628,800$.
2. $6!4!=(720)(24)=17280$.

Example. Mark has 10 books that he is going to put on his bookshelf. Of these, 4 are math books, 3 are physics books, 2 are computer science books, and 1 is a language book. Mark wants to arrange his books so that all the books dealing with the same subject are placed together on the shelf. How many different arrangements are possible?

Solution. There are $4!3!2!1!$ different arrangements in the order of math, physics, computer science and language. There are then $4!$ different ways to arranging the 4 subjects. Therefore, the final answer is $4!4!3!2!1!=6912$.

Example. How many different letter arrangements can be formed using the letters PEPPER?

Solution. Suppose that the 3 P’s and 2 E’s are distinguished as $P_1E_1P_2P_3E_2R$. Then there would be $6!$ permutations. Now there are $3!$ permutations among the 3P’s and $2!$ permutations among the 2 E’s. Hence, there are all $3!2!$ permutations of the form PPEPER. Therefore, there are $\frac{6!}{3!2!}=60$ possible letter arrangements of the letters PEPPER.

By a similar account, we see that there are $$\frac{n!}{n_1!n_2!\cdots n_r!}$$ different permutations of $n$ objects, of which $n_1$ are alike, $n_2$ are alike, …, $n_r$ are alike.

Example. A chess tournament has 10 competitors of which 4 are Russians, 3 are from the United States, 2 from Great Britain, and 1 from Brazil. If the tournament result lists just the nationalities of the prayers in the order in which they are placed, how may outcomes are possible?

Solution. $\frac{10!}{4!3!2!1!}=12,600$.

What if we want to arrange not all elements but only some elements from a set? Here is an example.

Example. A club of 25 members is holding an election for president, secretary and treasurer in that order. Assume that a person can hold only one position. How many different ways of choosing these officers are there?

Solution. $25\cdot 24\cdot 23$ by the basic principle of counting.

Definition. An ordered arrangement of $r$ elements selected from $n$ elements, $0\leq r\leq n$, where no two elements of the arrangement are the same, is called a permutation of $n$ objects taken $r$ at a time.The total number of such permutations is denoted by $P(n,r)$ or ${}_nP_r$.

By the basic principle of counting we find that \begin{equation}\label{eq:perm}P(n,r)=\prod_{j=0}^{r-1}(n-j)=n(n-1)(n-2)\cdots(n-r+1)\end{equation}

The expression in \eqref{eq:perm} can be written as \begin{equation}\label{eq:perm2}P(n,r)=\frac{n!}{(n-r)!}\end{equation} The sage command for calculating $P(n,r)$ is falling_factorial(n,r). Obviously, $P(n,n)=n!$. On the other hand, we have $P(n,n)=\frac{n!}{0!}$ from \eqref{eq:perm2}. Therefore, it is defined that $0!=1$.

Using the formula \eqref{eq:perm2} the answer to the question in the above example is simply $$P(25,3)=\frac{25!}{(5-3)!}=25\cdot 24\cdot 23$$

Example. Consider the digits 1, 2, 3, 4, 5.

1. How many three-digit numbers can be formed if no repetition of digits can occur?
2. How many three-digit numbers can be formed if repetition is allowed?
3. How many three-digit numbers can be formed if only non-consecutive repetition of digits are allowed?

Solution.

1. $P(5,3)=\frac{5!}{(5-3)!}=5\cdot 4\cdot 3=60$.
2. $5\cdot 5\cdot 5=125$.
3. $5\cdot 4\cdot 4=80$.

References: Not in particular order.

[1] Applied Discrete Structures, Al Doerr and Ken Levasseur. This book is available for free under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.

[2] A First Course in Probability, Sheldon Ross, 5th Edition, Prentice-Hall, 1998

What is combinatorics? It can be simply characterized as:

Combinatorics = The Art of counting

Combinatorics begins with

The Basic Principle of Counting: Suppose that two operations are to be performed. If operation 1 results in any one of $m$ possible outcomes and if for each outcome of operation 1 there are $n$ possible outcomes of operation 2, then together there are $mn$ possible outcomes of the two operations.

The Basic Principle of Counting is also called the Rule of Products. The principle assumes that the choice for operation 2 does not depend on the choice of operation 1.

Example. A lunch bar serves 5 different sandwiches and 3 different drinks. How many different lunches can a person order?

Solution. For each choice of a sandwich, there are three different choices of a drink. Hence there are $5\cdot 3=15$ possible orders.

Example. Let $A$ and $B$ be finite sets. Prove that $|A\times B|=|A|\cdot|B|$ where $|A|$ denotes the cardinality (i.e. the number of elements) of the set $A$.

Proof. Let $|A|=m$ and $|B|=n$. For each choice of elements in $A$ there are $n$ possible choices for the elements in $B$ to pair with. Since there are $m$ possible choices for the elements in $A$, the total number of all possible ordered pairs is $mn$, i.e. $|A\times B|=mn=|A|\cdot|B|$.

Example. A small community consists of 10 women, each of whom has 3 children. If one woman and one of her children are to be chosen as mother and child of the year, how many different choices are possible?

Solution. There are $10\times 3=30$ possible choices.

If more than two operations are to be performed, the basic principle can be generalized as follows.

The Generalized Basic Principle of Counting

If $r$ operations are to be performed in such a way that operation 1 results in $n_1$ possible outcomes, operation 2 results in $n_2$ possible outcomes, …, operation $r$ results in $n_r$ possible outcomes, then there is a total of $n_1\cdot n_2\cdots n_r$ possible outcomes of the $r$ operations.

Example. A person is to complete a true-false questionnaire. How many different ways are there to answer the questionnaire?

Solution. $\stackrel{10\ \mathrm{fold}}{\overbrace{2\cdot 2\cdots 2}}=2^{10}=1024$.

Example. A questionnaire contains 4 questions that have 2 possible answers and three questions with 5 possible answers. How many different answers are possible?

Solution. $2\cdot 2\cdot 2\cdot 2\cdot 5\cdot 5\cdot 5=2^4\cdot 5^3=2000$ different ways to answer the questionnaire.

Example. How many different 7-place license plates are possible if the first 3 places are to be occupied by letters and the final 4 by numbers?

Solution. $26\cdot 26\cdot 26\cdot 10\cdot 10\cdot 10\cdot 10=175,760,000$.

Example. In the above example, how many license plates would be possible if repetition among letters or numbers were prohibited?

Solution. $26\cdot 25\cdot 24\cdot 10\cdot 9\cdot 8\cdot 7=78,624,000$.

Theorem. (Power Set Cardinality Theorem) If $A$ is a finite set, then $|\wp(A)|=2^{|A|}$.

Proof. The proof boils down to counting how many different ways there are to determine subsets of $A$. Let $B$ be a subset of $A$. For each $x\in A$, there are two possibilities: either $x\in B$ or $x\not\in B$. Since $A$ has $n$ elements, there are $\stackrel{n\ \mathrm{fold}}{\overbrace{2\cdot 2\cdots 2}}=2^n$ different ways to determine subsets of $A$.

References: Not in particular order.

[1] Applied Discrete Structures, Al Doerr and Ken Levasseur. This book is available for free under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 United States License.

[2] A First Course in Probability, Sheldon Ross, 5th Edition, Prentice-Hall, 1998