2.1.5 Solved Problems:
Combinatorics
Let $A$ and $B$ be two finite sets, with $A=m$ and $B=n$. How many distinct functions (mappings) can you define from set $A$ to set $B$, $f:A \rightarrow B$?
 Solution
 We can solve this problem using the multiplication principle. Let $$A =\{a_1,a_2,a_3,...,a_m\},$$ $$B =\{b_1,b_2,b_3,...,b_n\}.$$ Note that to define a mapping from $A$ to $B$, we have $n$ options for $f(a_1)$, i.e., $f(a_1) \in B=\{b_1,b_2,b_3,...,b_n\}$. Similarly we have $n$ options for $f(a_2)$, and so on. Thus by the multiplication principle, the total number of distinct functions $f:A \rightarrow B$ is $$n \cdot n \cdot n \cdots n = n^m.$$
Problem
A function is said to be onetoone if for all $x_1\neq x_2$, we have $f(x_1)\neq f(x_2)$. Equivalently, we can say a function is onetoone if whenever $f(x_1)=f(x_2)$, then $x_1=x_2$. Let $A$ and $B$ be two finite sets, with $A=m$ and $B=n$. How many distinct onetoone functions (mappings) can you define from set $A$ to set $B$, $f:A \rightarrow B$?
 Solution
 Again let $$A =\{a_1,a_2,a_3,...,a_m\},$$ $$B =\{b_1,b_2,b_3,...,b_n\}.$$ To define a onetoone mapping from $A$ to $B$, we have $n$ options for $f(a_1)$, i.e., $f(a_1) \in B=\{b_1,b_2,b_3,...,b_n\}$. Given $f(a_1)$, we have $n1$ options for $f(a_2)$, and so on. Thus by the multiplication principle, the total number of distinct functions $f:A \rightarrow B$, is $$n \cdot (n1) \cdot (n2) \cdots (nm+1) = P^n_{m}.$$ Thus, in other words, choosing a onetoone function from $A$ to $B$ is equivalent to choosing an $m$permutation from the $n$element set $B$ (ordered sampling without replacement) and as we have seen there are $P^n_{m}$ ways to do that.
Problem
An urn contains $30$ red balls and $70$ green balls. What is the probability of getting exactly $k$ red balls in a sample of size $20$ if the sampling is done with replacement (repetition allowed)? Assume $0\leq k \leq 20$.
 Solution
 Here any time we take a sample from the urn we put it back before the next sample (sampling with replacement). Thus in this experiment each time we sample, the probability of choosing a red ball is $\frac{30}{100}$, and we repeat this in $20$ independent trials. This is exactly the binomial experiment. Thus, using the binomial formula we obtain $$P(k \textrm{ red balls})={20 \choose k} (0.3)^k(0.7)^{20k}.$$
Problem
An urn consists of $30$ red balls and $70$ green balls. What is the probability of getting exactly $k$ red balls in a sample of size $20$ if the sampling is done without replacement (repetition not allowed)?
 Solution
 Let $A$ be the event (set) of getting exactly $k$ red balls. To find $P(A)=\frac{A}{S}$, we need to find $A$ and $S$. First, note that $S={100 \choose 20}$. Next, to find $A$, we need to find out in how many ways we can choose $k$ red balls and $20k$ green balls. Using the multiplication principle, we have $$A= {30 \choose k}{70 \choose 20k}.$$ Thus, we have $$P(A)= \frac{{30 \choose k}{70 \choose 20k}}{{100 \choose 20}}.$$
Problem
Assume that there are $k$ people in a room and we know that:
 $k=5$ with probability $\frac{1}{4}$;
 $k=10$ with probability $\frac{1}{4}$;
 $k=15$ with probability $\frac{1}{2}$.
 What is the probability that at least two of them have been born in the same month? Assume that all months are equally likely.
 Given that we already know there are at least two people that celebrate their birthday in the same month, what is the probability that $k=10$?
 Solution

 The first part of the problem is very similar to the birthday problem, one
difference here is that here $n=12$ instead of $365$. Let $A_k$ be the event that
at least two people out of $k$ people have birthdays in the same month. We have
$$P(A_k)=1\frac{P^{12}_k}{12^k}, \textrm{for } k \in \{2,3,4,...,12\}$$
Note that $P(A_k)=1$ for $k>12$. Let $A$ be the event that at least two people in the
room were born in the same month. Using the law of total probability, we have
$P(A)$ $= \frac{1}{4} P(A_5)+\frac{1}{4} P(A_{10})+ \frac{1}{2} P(A_{15})$ $= \frac{1}{4} \left(1\frac{P^{12}_5}{12^5}\right)+\frac{1}{4} \left(1\frac{P^{12}_{10}}{12^{10}}\right)+ \frac{1}{2}$.
 The second part of the problem asks for $P(k=10  A)$. We can use Bayes' rule to write
$P(k=10  A)$ $=\frac{P(Ak=10)P(k=10)}{P(A)}$ $= \frac{P(A_{10})}{4P(A)}$ $=\frac{1\frac{P^{12}_{10}}{12^{10}}}{(1\frac{P^{12}_5}{12^5})+(1\frac{P^{12}_{10}}{12^{10}})+ 2}$.
 The first part of the problem is very similar to the birthday problem, one
difference here is that here $n=12$ instead of $365$. Let $A_k$ be the event that
at least two people out of $k$ people have birthdays in the same month. We have
$$P(A_k)=1\frac{P^{12}_k}{12^k}, \textrm{for } k \in \{2,3,4,...,12\}$$
Note that $P(A_k)=1$ for $k>12$. Let $A$ be the event that at least two people in the
room were born in the same month. Using the law of total probability, we have

Problem
How many distinct solutions does the following equation have? $$x_1+x_2+x_3+x_4=100, \textrm{ such that }$$ $$x_1 \in \{1,2,3..\}, x_2 \in \{2,3,4,..\}, x_3,x_4 \in \{0,1,2,3,...\}.$$
 Solution
 We already know that in general the number of solutions to the equation $$x_1+x_2+...+x_n=k, \textrm{ where } x_i \in \{0,1,2,3,...\}$$ is equal to $${n+k1 \choose k}={n+k1 \choose n1}.$$ We need to convert the restrictions in this problem to match this general form. We are given that $x_1 \in \{1,2,3..\}$, so if we define $$y_1=x_11,$$ then $y_1 \in \{0,1,2,3,...\}$. Similarly define $y_2 =x_22$, so $y_2 \in \{0,1,2,3,...\}$. Now the question becomes equivalent to finding the number of solutions to the equation $$y_1+1+y_2+2+x_3+x_4=100, \textrm{ where } y_1,y_2,x_3,x_4 \in \{0,1,2,3,...\},$$ or equivalently, the number of solutions to the equation $$y_1+y_2+x_3+x_4=97, \textrm{ where } y_1,y_2,x_3,x_4 \in \{0,1,2,3,...\}.$$ As we know, this is equal to $${4+971 \choose 3}={100 \choose 3}.$$
Problem (The matching problem)
Here is a famous problem: $N$ guests arrive at a party. Each person is wearing a hat. We collect all
hats and then randomly redistribute the hats, giving each person one of the $N$ hats randomly.
What is the probability that at least one person receives his/her own hat?
Hint: Use the inclusionexclusion principle.
 Solution

Let $A_i$ be the event that $i$'th person receives his/her own hat. Then we are interested in
finding $P(E)$, where $E=A_1 \cup A_2 \cup A_3 \cup ... \cup A_N$. To find $P(E)$, we use the
inclusionexclusion principle. We have
$P(E)=P\biggl(\bigcup_{i=1}^N A_i\biggr)$ $=\sum_{i=1}^N P(A_i)\sum_{i,j\,:\,i < j}P(A_i\cap A_j)$ $+\sum_{i,j,k\,:\,i < j < k}P(A_i\cap A_j\cap A_k)\ \cdots\ +(1)^{N1}\, P\biggl(\bigcap_{i=1}^N A_i\biggr)$.
Note that there is complete symmetry here, that is, we can write $$P(A_1) =P(A_2)=P(A_3)=...=P(A_N);$$ $$P(A_1 \cap A_2)=P(A_1 \cap A_3)=...=P(A_2 \cap A_4)=...;$$ $$P(A_1 \cap A_2 \cap A_3)=P(A_1 \cap A_2 \cap A_4)=...=P(A_2 \cap A_4 \cap A_5)=...;$$ $$...$$ Thus, we have $$\sum_{i=1}^N P(A_i)=N P(A_1);$$ $$\sum_{i,j\,:\,i < j}P(A_i\cap A_j)= {N \choose 2} P(A_1 \cap A_2);$$ $$\sum_{i,j,k\,:\,i < j < k}P(A_i\cap A_j\cap A_k)={N \choose 3} P(A_1 \cap A_2 \cap A_3);$$ $$...$$ Therefore, we have$P(E)$ $=NP(A_1) {N \choose 2} P(A_1 \cap A_2)$ $+ {N \choose 3} P(A_1 \cap A_2 \cap A_3)...+(1)^{N1}P(A_1 \cap A_2 \cap A_3 ... \cap A_N) \hspace{30pt} (2.5)$
Now, we only need to find $P(A_1)$, $P(A_1 \cap A_2)$, $P(A_1 \cap A_2 \cap A_3)$, etc. to finish solving the problem. To find $P(A_1)$, we have $$P(A_1)=\frac{A_1}{S}.$$ Here, the sample space $S$ consists of all possible permutations of $N$ objects (hats). Thus, we have $$S=N!$$ On the other hand, $A_1$ consists of all possible permutations of $N1$ objects (because the first object is fixed). Thus $$A_1=(N1)!$$ Therefore, we have $$P(A_1)=\frac{A_1}{S}=\frac{(N1)!}{N!}=\frac{1}{N}$$ Similarly, we have $$A_1 \cap A_2=(N2)!$$ Thus, $$P(A_1 \cap A_2)=\frac{A_1 \cap A_2}{S}=\frac{(N2)!}{N!}=\frac{1}{P^{N}_{N2}}.$$ Similarly, $$P(A_1 \cap A_2 \cap A_3)=\frac{A_1 \cap A_2 \cap A_3}{S}=\frac{(N3)!}{N!}=\frac{1}{P^{N}_{N3}};$$ $$P(A_1 \cap A_2 \cap A_3 \cap A_4)=\frac{A_1 \cap A_2 \cap A_3 \cap A_4}{S}=\frac{(N4)!}{N!}=\frac{1}{P^{N}_{N4}};$$ $$...$$ Thus, using Equation 2.5 we have $$P(E)=N. \frac{1}{N} {N \choose 2} \cdot \frac{1}{P^{N}_{N2}}+ {N \choose 3} \cdot \frac{1}{P^{N}_{N3}}...+(1)^{N1}\frac{1}{N!} \hspace{40pt} (2.6)$$ By simplifying a little bit, we obtain $$P(E) =1 \frac{1}{2!}+\frac{1}{3!}....+(1)^{N1}\frac{1}{N!}.$$ We are done. It is interesting to note what happens when $N$ becomes large. To see that, we should remember the Taylor series expansion of $e^{x}$. In particular, $$e^x=1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+...$$ Letting $x=1$, we have $$e^{1}=1\frac{1}{1!}+\frac{1}{2!}\frac{1}{3!}+...$$ Thus, we conclude that as $N$ becomes large, $P(E)$ approaches $1\frac{1}{e}$.

Let $A_i$ be the event that $i$'th person receives his/her own hat. Then we are interested in
finding $P(E)$, where $E=A_1 \cup A_2 \cup A_3 \cup ... \cup A_N$. To find $P(E)$, we use the
inclusionexclusion principle. We have