\documentstyle[12pt,psfig]{article}
\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6.5in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newcommand{\qed}{\mbox{\ \ \ }\rule{6pt}{7pt} \bigskip}
\newcommand{\binom}[2]{{#1 \choose #2}}

\begin{document}

{\bf Tutorial 8.}

\date{}

\section{Binomial coefficients}
In lecture, we saw the {\em binomial coefficients} 
$${n \choose r} = \frac{n!}{r!(n-r)!}$$
These represent the number of ways to
choose $r$ elements from a set of $n$ elements, where the order does
not matter. Here we see more properties of binomial coefficients.

Recall that 
for $0 \leq r \leq n$, 
$${n \choose r} = {n \choose n-r}.$$

The next theorem gives the ratio between successive binomial
coefficients (same $n$, successive $r$):

\begin{theorem}
Suppose $1 \leq r \leq n$. 
Then 
$${n \choose r} = {(n-r+1) \over r} {n \choose r-1}.$$
\end{theorem}

{\em Proof. } Consider,
$${n \choose r} / {n \choose r-1}$$
$$= \frac{n!}{r!(n-r)!} \times \frac{(r-1)!(n-(r-1))!}{n!} = (n-r+1)/r.$$
\qed

Note that this ratio is $> 1$, which means the successive
coefficients are increasing, as long as $r < \frac{n+1}{2}$. 
Also, the ratio is $<1$, which means the coefficient are decreasing,
when $r > \frac{n+1}{2}$. 
This says that the coefficients increase, reach the maximum, 
then decrease, i.e., they
are {\em unimodal}. 
They form a bell-shaped curve:
\begin{figure}[htbp]
\centerline{\psfig{figure=bell.ps,height=2in}}
\caption{Bell Curve}
\label{fig:bell}
\end{figure}

We will see more about bell curves when we discuss probability.

Here is another identity about binomial coefficients.

\begin{theorem}
Suppose $0 \leq r \leq m,n$. 
Then 
\[
{m+n \choose r} = \sum_{k=0}^r {m \choose r-k}{n\choose k}
\]
\end{theorem}

{\em Proof. }
Suppose there are $m$ red balls and $n$ blue balls, all distinct.  
There are ${m+n \choose r}$ ways to choose $r$ balls from the two
sets combined.
This is the LHS of the identity.
Now decompose this collection of choices based on how many of the
chosen balls are blue and how many are red.
For any $k$, $0 \leq k \leq r$, there are ${m \choose r-k}$ ways to
choose $r-k$ red balls, and ${n \choose k}$ ways to choose $k$ blue
balls.
By the product rule, that makes ${m \choose r-k} {n\choose k}$
ways to choose $r$ balls such that $k$ of them are blue. 
Adding up these numbers for all $k$ we have that this is
$\sum_{k=0}^r {m \choose r-k}{n\choose k}$ which is the RHS. \qed


\section{Derangements}

A {\em derangement} is a permutation of $1,2,\ldots,n$ where $i$ 
is not in the $i^{th}$ position. E.g. the
number of ways of addressing $n$ envelopes to $n$ people so that
all the envelopes are mailed to wrong addresses. Let us
represent the number of derangements on $n$ elements as $!n$.

\begin{theorem}
$$!n = n! \sum_{k=0}^n { (-1)^k \over k! } $$
\end{theorem}

We can prove the theorem using the inclusion-exclusion principle. 
Recall that for sets $A_1,A_2,\ldots,A_n$,
$$|A_1 \cup \ldots \cup A_n| = \sum_{1\leq i \leq n} |A_i| -
 \sum_{1 \leq i_1 < i_2 \leq n} |A_{i_1} \cap A_{i_2}| $$
$$+\sum_{1 \leq i_1 < i_2 < i_3\leq n} |A_{i_1} \cap A_{i_2} \cap A_{i_3}| - \ldots + (-1)^{n+1} |A_1 \cap A_2 \cap \ldots \cap A_n|$$
Or more succintly,
$$|A_1 \cup \ldots \cup A_n| = \sum_{k=1}^n (-1)^{k+1} \sum_{S \subseteq \{1,\ldots,n\}, |S| = k} |\cap_{i \in S} A_i|.$$

This expresses the size of the union of $n$ sets in terms of intersections
of subsets of the $n$ sets. We have an analogous inclusion-exclusion formula
for expressing the the size of the intersection:
$$|A_1 \cap \ldots \cap A_n| = \sum_{k=1}^n (-1)^{k+1} \sum_{S \subseteq \{1,\ldots,n\}, |S| = k} |\cup_{i \in S} A_i|.$$

We will use this latter formula to find the number of derangements on $n$
elements.

{\em Proof. }
Let $A_1$ be the set of permutations where the element $1$ is mapped to
a position other than $1$. Similarly let $A_i$ for $i = 1,\ldots,n$ be
the set of permutations of $1,\ldots,n$ where $i$ is not mapped to the
$i^{th}$ position. Note that in a permutation in $A_i$ any element $j \neq i$
could be mapped to $j$ itself.

Now the set of derangements is exactly $A_1 \cap A_2 \cap \ldots \cap A_n$,
because in this set each element $i$ is taken to a position other than $i$.
So we can apply the inclusion-exclusion formula. But to do this we need
to know the size of the union of a subset of the $A_i$'s. E.g. what
is $|A_1 \cup A_2 \cup A_3|$ ?  The set $A_1 \cup A_2 \cup A_3$ is the
set of permutations where at least one of the elements $1,2,3$ is mapped
to a location other than itself. So the only permutations that are
not in this set are those where all three of $1,2,3$ are mapped to the
positions $1,2,3$ respectively. But the latter set is easy to count: there
are exactly $(n-3)!$ permutations where $1,2,3$ are mapped to $1,2,3$
respectively. The total number of permuations is of course $n!$. 
So we have $|A_1 \cup A_2 \cup A_3| = n! - (n-3)!$.
What about the union of $k$ of the $A_i$'s?  Let $S \subseteq \{1,\ldots,n\}$.
Then, $\cup_{i \in S} A_i$ is the set of permutations where at least one
of the elements $i \in S$ is mapped to a position other than $i$. So the
number of permutations not in this set is the number of permutations where
the elements in $S$  are mapped to themselves. But this is $(n-k)!$, and hence
$$|\cup_{i \in S, |S| =k} A_i| = n! - (n-k)!$$

From the inclusion-exclusion formula,
$$|A_1 \cap \ldots \cap A_n| = \sum_{k=1}^n (-1)^{k+1} \sum_{S \subseteq \{1,\ldots,n\}, |S| = k} |\cup_{i \in S} A_i|$$
$$ = \sum_{k=1}^n (-1)^{k+1} \sum_{S \subseteq \{1,\ldots,n\}, |S| = k} 
        (n! - (n-k)!) $$
Since there are ${n \choose k}
$ subsets of $n$ of size $k$, 
$$ =  \sum_{k=1}^n (-1)^{k+1} {n \choose k}
(n! - (n-k)!)$$
$$ = \sum_{k=0}^n (-1)^{k+1} {n \choose k}
(n! - (n-k)!)$$
$$ = n!\sum_{k=0}^n (-1)^{k+1} {n \choose k}
 - \sum_{k=0}^n (-1)^{k+1} {n \choose k}
(n-k)!$$
$$ = n!(1+(-1))^n + \sum_{k=0}^n (-1)^k {n! \over k!}$$
$$ = n! \sum_{k=0}^n {(-1)^k \over k!}$$
\qed

The taylor expansion of $e^x$ is
$$e^x = 1 + x + {x^2 \over 2!} + {x^3 \over 3!} + ... $$
That is, $$e^x = \sum_{k=0}^\infty {x^k \over k!}$$
For $x = -1$, we have
$$e^{-1} = 1/e = \sum_{k=0}^\infty {(-1)^k  \over k!}$$

This looks very close to our formula for derangements which 
is $n!$ times the first $n+1$ terms in this expansion.
In fact, we can observe that the number of derangements is the nearest
integer to $n!/e$. To see this, consider the difference $n!/e - !n$.
$$n!/e - !n = n! (\sum_{k=n+1}^\infty {(-1)^k \over k!}) $$
$$ = (-1)^{n+1}({ 1 \over n+1} - {1 \over (n+1)(n+2)} + .. + 
  {(-1)^{k+1} \over (n+1)(n+2)\ldots (n+k)} + ..)$$
So for $n \geq 1$, 
$$|n!/e - !n| = { 1 \over n+1} - {1 \over (n+1)(n+2)} + .. + 
  {(-1)^{k+1} \over (n+1)(n+2)\ldots (n+k)} + ..$$
$$ \leq {1 \over 2} - {1 \over 2.3 } + .. + {(-1)^{k+1} \over (k+1)!} = 1/e$$

The last inequality can be observed by grouping the terms of the
summation into pairs (the first two, next two and so on) and then
comparing.
The difference between $n!/e$ and $!n$ is at most $1/e$, so the number of 
derangements must be the integer closest to $n!/e$.

\section{Boolean Circuits}

Let us consider boolean circuits with 
AND, OR and NOT gates. The {\em size} of a boolean circuit is the number of 
gates it has. Does every boolean function have a circuit of a reasonably
small size?  One notion of reasonably small is when the size $s$ of the 
circuit is bounded by a polynomial in the number of inputs $k$, i.e., 
$s \leq k^t$ where $t$ is some fixed number. We see here that
in fact most boolean functions {\em need} circuits of exponential size.

\begin{lemma}
The number of boolean functions on $k$ inputs,
$f: \{0,1\}^k \rightarrow \{0,1\}$ is $2^{2^k}$.
\end{lemma}

{\em Proof. }
A boolean function $f$ maps each $0,1$ string of length $k$ to one
of $0,1$. We can define a mapping from boolean functions to 
subsets of $0,1$ strings of length $k$ as follows: A function
$f$ is mapped to the subset of strings that it maps to $0$.
This mapping from boolean functions to subsets of the set of all
strings of length $k$ is a injection because for any two distinct functions
there is some string which one of them sends to $0$ while the other
maps to $1$. It is also a surjection because we can define the 
inverse map from subsets of $\{0,1\}^k$ to boolean functions as
follows: map a subset $S$ of strings to the function which maps
the strings in the subset to $0$ and all other strings to $1$. 
Therefore we have a bijection. Hence the number of boolean functions
is the number of subsets of $0,1$ strings of length $k$. There are $2^k$
strings of length $k$. The number of subsets is $2^{2^k}$. \qed

\begin{lemma}
The number of circuits with $s$ gates and $k$ inputs is at most $(3(s+k))^s$.
\end{lemma}

{\em Proof. }
Consider some circuit with $s$ gates and $k$ inputs. Each gate has
two input wires and one output wire. We can describe a circuit completely
by specifying the where the input and output wires of each gate go.
The total number of inputs plus
gates is $s+k$, so number of possibilities
for the origin of each input wire of a gate is $s+k$. 
Similarly, each output wire is connected to one 
of the gates or just left hanging, so the number of possibilities 
for each output wire is $s+1$. The total number of ways in which we can
wire a single gate is therefore at most $(s+1)(s+k)^2 \leq (s+k)^3$.
There are $s$ gates to be wired like this. By the product rule, the 
total number of boolean circuits is at most $((s+k)^3)^s = (s+k)^{3s}$. \qed

\begin{theorem}
For any $t \geq 1$, for all $k > C_t$, 
there exist boolean functions on $0,1$ strings of 
length $k$ that need circuits of size  $> k^t$. Here $C_t$ is 
a constant that depends only on $t$. 
\end{theorem}

{\em Proof. }
Let $s = k^t$ for any fixed $t \geq 1$. Then the number of circuits
of size $s$ is at most 
$$(k^t+k)^{3k^t} \leq (k^{t+1})^{3k^t} $$
$$\leq k^{3(t+1)k^t}$$ 

If every boolean function has circuits of size at most $k^t$ for
some $t$, then 
$$2^{2^k} \leq k^{3(t+1)k^t}$$
$$ 2^k \leq 3(t+1)k^t\log k$$
$$ k \leq t \log k + \log 3(t+1) + \log \log k$$

So if we let $C_t = 3(t+1)^2$ 
then the above condition is violated for all $k > C_t$. 
That is, for any $k > C_t$ there are functions on $k$ inputs that
need more than $k^t$ gates.  \qed



\section{Team Problems}
\begin{enumerate}
\item 
 \begin{enumerate}
  \item Find a recurrence relation for the number of derangements on $n$ elements.
  \item Using the recurrence, 
verify our formula for the number of derangements.
  \end{enumerate}
\item 
 \begin{enumerate}
  \item $${n \choose r}{r \choose k} = {n \choose k}{n-k \choose r-k}$$
  \item $${2n \choose 2} = 2{n \choose 2} + n^2$$
 \end{enumerate}
\end{enumerate}
\end{document}


