Recall

Last time, we went tover two basic counting problems. In both problems, we counted how many ways we can choose $k$ elements from ${1,\dots,n}$ whe the order of selection does matter; namely, we counted \emph{sequences} of length $k$. If repetition was allowed, the answer was $n^k$ (using the product rule) and if the repetition was not allowed, the answer was $n (n-1) \dots (n-k+1) = n!/(n-k)!$ using the generalized product rule.

Today, we will focus on a similar counting problem but in a scenario in which order does not matter. Before that, let’s recall the division rule.

Division Rule. If $f \colon A \to B$ is a $k$ to $1$ (total surjective) function, and if $A,B$ are finite sets then, $|A| = k \cdot |B|$.

Counting when order does not matter

The number of subsets of size $k$ of ${1,\dots,n}$ captures a counting problem in which the order of the $k$ selected elements does not matter. This is denoted by ${n \choose k}$ and as we show, is equal to ${n \choose k} = \frac{n!}{k! (n-k)!}$.

The proof uses the division rule. Suppose $S_k$ is the set of all subsets of ${1,\dots,n}$ of size $k$ and let $T_k$ be the set of all \emph{sequences} of length $k$ using ${1,\dots,n}$ (where repetition is not allowed). As we saw before, we know that $|T_k|=n!/(n-k)!$. Now, we show a $\ell$-to-1 mapping from $T_k$ to $S_k$, for $\ell=k!$ which, by the division rule will imply that $|S_k|=\frac{n!/(n-k)!}{k!} = \frac{n!}{(n-k)! k!}$.

$\ell$-to-1 mapping from $T_k$ to $S_k$: Map any sequence $(a_1,\dots,a_k)$ to the set ${a_1,\dots,a_k}$. First note taht this is a total surjective function from $T_k$ to $S_k$. Furthermore, for any set $A={a_1,\dots,a_k}$ there are $k!$ permutations like $(b_1,\dots,b_k)$ of the same set $A$ (we proved that already!). Therefore, the mapping is $\ell$-to-1 for $\ell=k!$.

when repetition is allowed. Note that in the problem above, we cannot select the same element $i$ from ${1,\dots,n}$ more than once, but suppose we consider the selections to be “multi-sets” where the order of elements do not matter, but they could be selected more than once. This is a way to model the example problem from last class about donuts.

Give a bijection between the sets that model the following two counting problems: \begin{itemize} \item Selecting $k$ elements from ${1,\dots,n}$ as a “multi-set”; namely, the order of selection does not matter, but we \emph{can} select an element more than once. \item Number of sequences using elements from ${0,1}$ with exactly $k$ ones, and exaclty $n-1$ zeros. \end{itemize}

Using the above bijection, show that selecting $k$ donuts frm $n$ different varieties is possible in a total of ${n+k-1 \choose n-1}$ many ways.

#

Basics of Probability

Probability theory is one of the richest and most beautiful mathematical theories with enormous applications. Here we take a very brief look at it, by using our counting techniques for estimating the “chance” of certaing “outcomes”.

Some of the basic questions we deal with in probability theory look like the following examples. \begin{itemize} \item Suppose a bag contains $10$ donuts and $5$ bagles. If we pick one of the items in the bad \emph{uniformly} (at random), what is the \emph{probability} that we pick a bagel. \item Suppose we do not put back the item that we selected in the previous example. Now, if we take another item, what is the chance that it is a donut \emph{conditioned} on the first item being a bagel? \end{itemize}

Sample Space and Event

The sample space $\Omega= {x_1,\dots,x_n }$ includes all the possible outcomes and their own specific probability $\Pr[xi]$, while the total summation is $1=\sum{x\in \Omega} \Pr[xi]$. An Event $E$ is simply a subset of the sample space $E \subseteq \Omega$, and its probability is defined to be $\Pr[E] = \sum{x \in E} \Pr[x]$.

When we draw one item from a bag of $10$ donuts and $5$ bagles: \begin{itemize} \item What is the sample space? \item What is the probabilty of each outcome? \item What is the Event $B$ that we draw a bagel? \item What is the probability of $B$? \end{itemize}

Conditional Probability

For two events $E,C$, the probability of $E$ hapenning \emph{conditioned} on $C$ happenin is denoted by $\Pr[E \mid C]$ and equal to $$\Pr[E \mid C] = \frac{\Pr[E \cap C]}{\Pr[C]}.$$

For example, for any non-empty $E$, we have $\Pr[E \mid E] = 1$, and for any disjoint events $E,C$ we have $\Pr[E \mid C]=0$.

What is the probability space of taking two items (without repetition) from the same basket of $10$ donuts and $5$ bagles? What is the formal definition of the event $B$ that the first item is a bagel? What is the formal definition of the event $D$ that the second item is a donut? What is the probability of $D$ conditioned on $B$?