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)!}$