2.1.5 Solved Problems:
Combinatorics

Problem

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 one-to-one if for all $x_1\neq x_2$, we have $f(x_1)\neq f(x_2)$. Equivalently, we can say a function is one-to-one 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 one-to-one 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 one-to-one 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 $n-1$ 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-1) \cdot (n-2) \cdots (n-m+1) = P^n_{m}.$$ Thus, in other words, choosing a one-to-one 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)^{20-k}.$$


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 $20-k$ green balls. Using the multiplication principle, we have $$|A|= {30 \choose k}{70 \choose 20-k}.$$ Thus, we have $$P(A)= \frac{{30 \choose k}{70 \choose 20-k}}{{100 \choose 20}}.$$


Problem
Assume that there are $k$ people in a room and we know that:
  1. What is the probability that at least two of them have been born in the same month? Assume that all months are equally likely.
  2. 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
      1. 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}$.

      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(A|k=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}$.



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+k-1 \choose k}={n+k-1 \choose n-1}.$$ 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_1-1,$$ then $y_1 \in \{0,1,2,3,...\}$. Similarly define $y_2 =x_2-2$, 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+97-1 \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 inclusion-exclusion 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 inclusion-exclusion 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)^{N-1}\, 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)^{N-1}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 $N-1$ objects (because the first object is fixed). Thus $$|A_1|=(N-1)!$$ Therefore, we have $$P(A_1)=\frac{|A_1|}{|S|}=\frac{(N-1)!}{N!}=\frac{1}{N}$$ Similarly, we have $$|A_1 \cap A_2|=(N-2)!$$ Thus, $$P(A_1 \cap A_2)=\frac{|A_1 \cap A_2|}{|S|}=\frac{(N-2)!}{N!}=\frac{1}{P^{N}_{N-2}}.$$ Similarly, $$P(A_1 \cap A_2 \cap A_3)=\frac{|A_1 \cap A_2 \cap A_3|}{|S|}=\frac{(N-3)!}{N!}=\frac{1}{P^{N}_{N-3}};$$ $$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{(N-4)!}{N!}=\frac{1}{P^{N}_{N-4}};$$ $$...$$ Thus, using Equation 2.5 we have $$P(E)=N. \frac{1}{N}- {N \choose 2} \cdot \frac{1}{P^{N}_{N-2}}+ {N \choose 3} \cdot \frac{1}{P^{N}_{N-3}}-...+(-1)^{N-1}\frac{1}{N!} \hspace{40pt} (2.6)$$ By simplifying a little bit, we obtain $$P(E) =1- \frac{1}{2!}+\frac{1}{3!}-....+(-1)^{N-1}\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}$.





The print version of the book is available through Amazon here.

Book Cover