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$?

Examples

Today, we want to be able to answer the following questions. The first two are already discussed in class, but we will study them more generally. \begin{enumerate} \item How many subsets does $S$ have if $|S|=n$? \item How many numbers are there that can be represented with (at most) $n$ bits (in base 2) ? \item How many (at most) 16-bit numbers with exactly 4 ones? \item How many ways to choose 12 doughnuts from 5 varieties? \end{enumerate}

The first two questions have the same answer: $2^n$. In fact, because there is a bijection between the sets described in problem 1 and problem 2, then we already know that their answers must be the same.

More generally, all counting problems of today’s class could be described as “what is the size of a set $A$?” We use the definition of finite cardinality from Class 9, to study these questions. Namely, we try to find another set $B$ whose cardinality is known, and that there is a bijection between $A$ and $B$.

Why Counting?

Being able to count (exactly or even approximately) is important for many reasons, some of which are: \begin{itemize} \item Estimating the “cost” of an algorithm, this could be time, space, etc. This comes up when we try to analyze the “efficiency” of an algorithm. \item Estimating the “security” of a cryptographic algorithm. Basically, we would like to know how big is the “space of keys” from which the adversary has to “guess” the correct one. \item Counting is the fundamental to probability theory. \end{itemize}

Counting Rules

Product Rule If $A_1,\dots,A_n$ are finite sets, then the size of their cartesian product is $$|A_1 \times \dots \times A_n| = |A_1| \cdot |A_2| \dots |A_n| $$

We previously saw this rule in Class 7, but we will use it more heavily today, and we will see some extensions of it.

Using the product rule, formally prove that the answer to the first two example problems are both $2^n$. (Hint, let $S={a_1,\dots,a_n}$ and let $A_i = {a_i,0}$.)

# # #

Sum Rule. If $A_1,\dots,A_n$ are finite \emph{disjoint} sets, then the size of their \emph{union} is $$|A_1 \cup \dots \cup A_n| = |A_1| + |A_2| \dots +|A_n|.$$

The sum rule is even simpler than the product rule, but together with the product rule, they become very powerful.

Using the product and sum rules, count how many passwords of 6 to 8 characters exist if the first character can be an english letter (upper or lower case, so $26 \times 2$ possibilities) and the rest of the characters are either a letter or digit ($(26 \times 2) + 10$ possibilities).

#

Generalized product rule. Suppose $S$ is a set containing length-$k$ sequences like $(a_1,\dots,a_k)$. If there are $n_i$ possibilities for $i^{\text th}$ entry $a_i$ for any possible prefix $a1,\dots,a{i-1}$, then $|S|=n_1 \cdot n_2 \dots n_k$.

Using the generalizd product rule, prove that the number of permutations over any set $S={s_1,\dots,s_n}$ is $n!$. A permutation is simply a sequence $(a_1,\dots,a_n)$ where each $s_i$ appears in that sequence exactly once.

# # #

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 number is so important that has its own notation ${n \choose k}$.

Using the division rule, prove that ${n \choose k} = \frac{n!}{k! (n-k)!}$