# Introductory Combinatorics: Combinations 2

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, $$\label{eq:multcoeff}\begin{pmatrix}n\\n_1,n_2,\cdots,n_r\end{pmatrix}=\frac{n!}{n_1!n_2!\cdots n_r!}$$ 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. $$\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}$$

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

# Introductory Combinatorics: Combinations 1

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 $$\label{eq:comb}\begin{pmatrix}n\\r\end{pmatrix}=\frac{n!}{r!(n-r)!}$$ $\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. $$\label{eq:combidentity}\begin{pmatrix}n\\r\end{pmatrix}=\begin{pmatrix}n-1\\r-1\end{pmatrix}+\begin{pmatrix}n-1\\r\end{pmatrix}$$ 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) $$\label{eq:binomthm}(x+y)^n=\sum_{r=0}^n\begin{pmatrix}n\\r\end{pmatrix}x^ry^{n-r}$$

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 $$\label{eq:binom}\sum_{r=0}^n\begin{pmatrix}n\\r\end{pmatrix}=(1+1)^n=2^n$$

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

# Introductory Combinatorics: Permutations

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 $$\label{eq:perm}P(n,r)=\prod_{j=0}^{r-1}(n-j)=n(n-1)(n-2)\cdots(n-r+1)$$

The expression in \eqref{eq:perm} can be written as $$\label{eq:perm2}P(n,r)=\frac{n!}{(n-r)!}$$ 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

# Introductory Combinatorics:The Basic Principle of Counting

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

# Modular Arithmetic

Recall the equivalence relation $\equiv\ \mathrm{mod}\ n$ on $\mathbb{Z}$ (we discussed it here) $$p\equiv q\ \mathrm{mod}\ n\ \Longleftrightarrow\ n|(p-q)$$ Let us denote by $p\ \mathrm{mod}\ n$ the remainder when $p$ is divided by $n$. The definition of the equivalence relation implies that $$p\equiv q\ \mathrm{mod}\ n\ \Longleftrightarrow\ p\ \mathrm{mod}\ n=q\ \mathrm{mod}\ n$$ (The proof is left as an exercise.) When an integer $p$ is divided by $n$, the remainder $p\ \mathrm{mod}\ n$ is an integer satisfying the inequality $0\leq p\ \mathrm{mod}\ n\leq n-1$. Therefore, the equivalence class $[p]$ is one of $[0],[1],\cdots,[n-1]$, i.e. the quotient set $\mathbb{Z}_n=\mathbb{Z}/\equiv\mathrm{mod}\ n$ is $$\mathbb{Z}_n=\{[0],[1],[2],\cdots,[n-1]\}$$ Also recall that in here we defined $+$ and $\cdot$ on $\mathbb{Z}_n$ by \begin{align*}[a]+[b]&=[a+b]\\ [a]\cdot[b]&=[a\cdot b]\end{align*} These operations are well-defined due to the following properties (see Problem Set 12 #7): if $a\equiv b\ \mathrm{mod}\ n$ and $c\equiv d\ \mathrm{mod}\ n$, then \begin{aligned}a+c&\equiv b+d\ \mathrm{mod}\ n\\a\cdot c&\equiv b\cdot d\ \mathrm{mod}\ n\end{aligned}\label{eq:congrel} The following is another useful property: if $a\equiv b\ \mathrm{mod}\ n$ and $c$ is an integer then $$\label{eq:congrel2}c\cdot a\equiv c\cdot b\ \mathrm{mod}\ n$$ Its proof is straightforward so it is left as an exercise. The properties \eqref{eq:congrel} and \eqref{eq:congrel2} can be used to calculate the remainder when a significantly large integer is divided by an integer $n$.

Example. What is $N\ \mathrm{mod}\ 21$ where $$N=113\times (167+484)+192\times 145?$$

Solution. $N=113\times (167+484)+192\times 145=101403$, which is not really a large number. One can simply divide 101403 by 21 and find the remainder 15. Let us now try a different way. Note that $113\equiv 8\ \mathrm{mod}\ 21$, $167\equiv 20\ \mathrm{mod}\ 21$, $484\equiv\ 1\mathrm{mod}\ 21$, $192\equiv 3\ \mathrm{mod}\ 21$, and $145\equiv 19\ \mathrm{mod}\ 21$. Hence by using \eqref{eq:congrel} we have $$N\equiv 8\times (20+1)+3\times 19=225\ \mathrm{mod}\ 21$$ 225 is a much smaller number and one can easily divide it by 21 and obtain the remainder 15. On the other hand, $21\equiv 0\ \mathrm{mod}\ 21$ and $19\equiv -2\ \mathrm{mod}\ 21$ since $19=21-2$. So by using the properties \eqref{eq:congrel} and \eqref{eq:congrel2}, we have $$N\equiv 8\times 0+3\times (-2)=-6\equiv 15\ \mathrm{mod}\ 21$$ since $-6=21(-1)+15$.

Example. What is $10^3\ \mathrm{mod}\ 7$?

Solution. $1000$ is not a large number and one can easily divide it by 7 to obtain $1000=142\cdot 7+6$ and so $10^3\equiv 6\ \mathrm{mod}\ 7$. There is a smarter way to do this though. Note that $10=7\cdot 1+3$, so $10\equiv 3\ \mathrm{mod}\ 7$. Using \eqref{eq:congrel}, we obtain $$10^3\equiv 3\cdot 3\cdot 3=27\equiv 6\ \mathrm{mod}\ 7$$

The remainder when a large number is divided by an integer sometimes can be calculated using repeated squaring as seen in the following example.

Example. Find $3^{25}\ \mathrm{mod}\ 7$.

Solution. \begin{align*}3^{25}&=(3^{12})^2\cdot 3\\&=((3^6)^2)^2\cdot 3\\&=(((3^3)^2)^2)^2\cdot 3\\&=(((3^2\cdot 3)^2)^2)^2\cdot 3\\&\equiv (((2\cdot 3)^2)^2)^2\cdot 3\\&=((36)^2)^2\cdot 3\\&\equiv 3\ \mathrm{mod}\ 7\end{align*} where we use the fact $36\equiv 1\ \mathrm{mod}\ 7$.

Definition. $[y]$ is said to be a multiplicative inverse of $[x]$ in $\mathbb{Z}_n$ if $x\cdot y\equiv 1\ \mathrm{mod}\ n$.

It is not necessarily that every non-zero element of $\mathbb{Z}_n$ has a multiplicative inverse. For example, let us consider the multiplication table of $\mathbb{Z}_4$. Here, we denoted $[a]$ by simply $a$. $$\begin{array}{|c|c|c|c|c|}\hline\cdot & 0 & 1 & 2 & 3\\\hline 0 & 0 & 0 & 0 &0\\\hline1 & 0 & 1 & 2 & 3\\\hline2 & 0 & 2 & 1 & 2\\\hline3 & 0 &3 & 0 &3\\\hline\end{array}$$ As clearly seen in the table, 3 does not have a multiplicative inverse. On the other hand, in $\mathbb{Z}_5$ all non-zero elements have multiplicative inverses as shown in the following table. $$\begin{array}{|c|c|c|c|c|c|}\hline\cdot & 0 & 1 & 2 & 3 & 4\\\hline 0 & 0 & 0 & 0 & 0 & 0\\\hline 1 & 0 & 1 & 2 & 3 & 4\\\hline 2 & 0 & 2 & 4 & 1 & 3\\\hline 3 & 0 &3 & 1 & 4 & 2\\\hline 4 & 0 & 4 & 3 & 2 & 1\\\hline\end{array}$$ Notice that 5 is a prime number. In fact, we have the following cool theorem.

Theorem. If $p$ is prime, then every non-zero element of $\mathbb{Z}_p$ has a multiplicative inverse. Therefore, $\mathbb{Z}_p$ is a finite field.

Proof. Let $a$ be an integer such that $1\leq a\leq p-1$. Then clearly $$\mathbb{Z}_p[a]=\{[0],[1\cdot a],\cdots,[(p-1)\cdot a]\}\subseteq\mathbb{Z}_p$$ If $[0],[1\cdot a],\cdots,[(p-1)\cdot a]$ are mutually distinct, $\mathbb{Z}_p[a]=\mathbb{Z}$ and therefore, $[i]\cdot[a]=[i\cdot a]=1$ for some $1\leq i\leq p-1$. That is, $[a]$ has a multiplicative inverse. So the proof of this theorem boils down to showing that $\mathbb{Z}_p[a]$ has $p$ distinct elements for any $1\leq a\leq p-1$. This is a consequence of the lemma below.

Lemma. If $p$ is a prime number such that $p\not| a$ and $i\cdot a\equiv j\cdot a\ \mathrm{mod}\ p$ then $i\equiv j\ \mathrm{mod}\ p$.

Proof. If $i\cdot a\equiv j\cdot a\ \mathrm{mod}\ p$ then $p|a(i-j)$. Since $p\not| a$, $p|i-j$ i.e. $i\equiv j\ \mathrm{mod}\ p$.

References.

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

[2] A Short Course in Discrete Mathematics, Edward A. Bender and S. Gil Williamson, Dover Publications, 2012