\documentstyle[12pt,twoside,amsfonts,eepic,psfig]{article}
\input{macros-course}
\parskip1.5ex
\parindent0pt


\begin{document}
\handout{notes14}{Notes 14}{October 26, 1995}

\newcommand{\binom}[2]{{#1 \choose #2}}

\section{Binomial Coefficients}

There are infinitely many interesting binomial coefficient identities.
They can't all be learned, but a few standard tools let you rederive
them as needed.  One approach is algebraic, and usually works by brute
force.  A cleverer method of {\em combinatorial} proof builds a
thought experiment that avoids all the math by using the semantics of
the binomial coefficients.


${n \choose 0}=1$.  ${n \choose 1}=n$.

Binomial coefficients are {\em unimodal:} ${n \choose r}$ increases
with $r$ until $r=n/2$, then decreases. 
\[
{n\choose r}/{n \choose r-1}= (n-r+1)/r
\]


Coefficients form a bell curve: suppose each student is equally likely
to get each of $n$ questions during the semester right or wrong.  Then the
bell curve describes how many ways the student can get $K$ questions
right, namely ${n \choose k}$.

\begin{figure}[htbp]
\centerline{\psfig{figure=bell.ps,height=2in}}
\caption{Bell Curve.}
\label{fig:bell}
\end{figure}


\begin{theorem} ${n \choose r} = {n \choose n-r}$
\end{theorem}
\begin{proof} (Algebraic) 
\[ {n\choose r} = \frac{n!}{r!(n-r)!} = \frac{n!}{(n-r)!(n-(n-r))!} = {n\choose n-r}.\]
\end{proof}

\begin{proof} (Combinatorial) Choosing $r$ objects from $n$ is the
  same as ``unchoosing'' the remaining $n-r$ objects.  Thus there is a
  bijection between the sets of size $r$ and those of size $n-r$.
  Hence, there is the same number of each.
\end{proof}

\begin{theorem} ${n \choose r} = \frac{n}{r}{n-1 \choose r-1}$
\end{theorem}
\begin{proof} (Algebraic)
\begin{eqnarray*}
{n \choose r} &= &\frac{n!}{r!(n-r)!}\\
&= &\frac{n}{r}\frac{(n-1)!}{(r-1)!(n-r)!}\\
&= &\frac{n}{r}{n-1 \choose r-1}
\end{eqnarray*}
\end{proof}
\begin{proof}(Combinatorial) Consider choosing a committee and a leader
  of size $r$ from among $n$ guys.  One way is to pick the leader
  first ($n$ ways) and then pick the other $r-1$ committee members from
  the remainder (${n-1 \choose r-1}$ ways).  The other is to pick the
  $r$ committee members ({$n \choose r$} ways) and then pick a leader
  from among them ($r$ ways).  Thus
\[
n{n-1 \choose r-1} = r{n \choose r}.
\]
Now divide both sides by $r$.
\end{proof}

\begin{theorem}[Pascal]
\[
{n \choose r} = {n-1 \choose r} + {n-1 \choose r-1}
\]
\end{theorem}
\begin{proof} (Algebraic)
\begin{eqnarray*}
 {n-1 \choose r} + {n-1 \choose r-1} & = & \frac{(n-1)!}{r!(n-1-r)!} +
 \frac{(n-1)!}{(r-1)!(n-r)!} \\
 &= &(n-r)\frac{(n-1)!}{r!(n-r)!} + r\frac{(n-1)!}{r!(n-r)!}\\
 &= &n\frac{(n-1)!}{r!(n-r)!}\\
 &= &{n \choose r}
\end{eqnarray*}

\end{proof}
\begin{proof} (Combinatorial) Let $S=\set{1,\ldots,n}$.
\begin{itemize}
\item $A = \set{X \subseteq S \mid \|X\|=r}$ ($r$-combs of $S$)
\item $B=\set{X \subseteq S \mid \|X\| = r \wedge 1 \in X}$
\item $C=\set{X \subseteq S \mid \|X\| = r \wedge 1 \notin X}$
\end{itemize}
We know that $A=B \cup C$ and $B,C$ are disjoint.
\begin{itemize}
\item $\|B\| = {n-1 \choose r-1}$
\item $\|C\| = {n-1 \choose r}$
\end{itemize}
Rule for sum says ${n \choose r} = \|A\| = \|B\|+\|C\|$.
\end{proof}

\begin{figure}[htbp]
\centerline{\psfig{figure=pascal.ps,height=2in}}
\caption{Pascal's triangle.}
\label{fig:pascal}
\end{figure}

What happens if I add the coefficients in one row?
\begin{theorem}
\[
\sum_{k=0}^n {n \choose k} = 2^n
\]
\end{theorem}
\begin{proof} (induction) Let $P(n)$ be 
\[
\sum_{k=0}^n {n \choose k} = 2^n
\]
Base case. If $n=1$ then 
\[
\sum_{k=0}^1 {1 \choose k} = {1\choose 0} + {1\choose 1} = 1 + 1 =  2^1.
\]
Hence $P(1)$ is true.\\
Inductive step. Assume $P(n-1)$ is true. Then 
\begin{eqnarray*}
\sum_{k=0}^{n+1} {n+1 \choose k} & = {n+1\choose 0} + \sum_{k=1}^{n} ({n \choose k} + {n\choose k-1}) + {n+1\choose n+1} & \mbox{ by Pascal's identity}\\
& =  {n\choose 0} + \sum_{k=1}^{n-1} 2({n \choose k}) + {n\choose n} & \\
& = 2\sum_{k=0}^n {n \choose k} & \\
& = 2^{n+1} & \mbox{ by inductive hypothesis}.
\end{eqnarray*}
Hence, $P(n+1)$ is true. So $P(n)$ is true for all $n$.
\end{proof}

\begin{proof} (combinatorial)
Consider the collection of all possible subsets of an $n$ element
universe. There are $2^n$ such subsets. Now count the collection based
on the sizes of the subsets. There are ${n\choose k}$ subsets of size $k$, for $k=0,1,\ldots,n$. Hence the theorem follows.
\end{proof}


\begin{theorem}[Vandermonde]
\[
{m+n \choose r} = \sum_{k=0}^r {m \choose r-k}{n\choose k}
\]
\end{theorem}
\begin{proof}(Induction using Pascal's identity)
Let $P(n)$ be 
\[
{m+n \choose r} = \sum_{k=0}^r {m \choose r-k}{n\choose k}
\]
Base Case. If $n =0$ then
\[
{m+0 \choose r} = \sum_{k=0}^r {m \choose r-k}{0\choose k} = {m\choose r}
\]
Hence $P(0)$ is true.\\
Inductive Step. Assume $P(n)$ is true. Then
\begin{eqnarray*}
{m+n+1 \choose r} & = &{m+n \choose r} + {m+n \choose r-1} \quad \mbox{ by Pascal's identity}\\
& = &\sum_{k=0}^r {m \choose r-k}{n\choose k} + \sum_{k=1}^r {m \choose r-k}{n\choose k-1}  \quad \mbox{ by inductive hypothesis}\\
& =  &{m \choose r}{n\choose0} + \sum_{k=1}^r {m \choose r-k}({n\choose k} + {n\choose k-1})  \\
& =  &{m \choose r}{n+1\choose 0} + \sum_{k=1}^r {m \choose
  r-k}{n+1\choose k}  \quad \mbox{ by Pascal's identity}\\ 
& = &\sum_{k=0}^r {m \choose r-k}{n+1\choose k} 
\end{eqnarray*}
Hence, $P(n+1)$ is true. So $P(n)$ is true for all $n$.
\end{proof}

\begin{proof} (Combinatorial) Suppose there are $m$ red balls and $n$ blue 
balls.  Consider all possible ways to choose $r$ balls. There are
${m+n \choose r}$ such ways. Now count the number of ways based on how
many of the balls are blue.There are ${m \choose r-k}{n\choose k}$
ways to choose $r$ balls such that $k$ of them are blue, for $k
=0,1,\ldots,r$. Hence the theorem follows.
\end{proof}


\section{The Binomial Theorem}

\begin{theorem}
  Let $n \in \naturals$. Then for all $x$ and $y$
  $$ (x+y)^n = \sum_{k=0}^n \binom{n}{k}x^ky^{n-k} $$
\end{theorem}

\begin{xample}
  $(x+y)^4 = 1x^4+4x^3y+6x^2y^2+4xy^3+1y^4$
\end{xample}

\begin{proof}
  (Algebraic) By induction (HW)
\end{proof}

\begin{proof}
  (Combinatorial) 
  $$ (x+y)(x+y)(x+y)(x+y) \;\; n=4 \; \mbox{binomials}$$
  Each $x^ky^{n-k}$ term selects $k$ binomials from the $n$ to have
  $x$, rest $y$. $\binom{n}{k}$ ways of choosing binomials.
\end{proof}

\subsection{Identities via Binomial Theorem }

Binomial theorem gives slick proofs of previous theorems.  e.g.:
\begin{eqnarray*}
  \sum_{k=0}^n \binom{n}{k} &= &2^n. \;\; \mbox{Plug in} \; x=1,y=1.
  \hfil (*)\\
  \sum_{k=0}^n (-1)^k\binom{n}{k} &= &0. \;\; \mbox{Plug in} \; x=-1,y=1.
  \hfil (**)
\end{eqnarray*}

Combinatorial interpretation: number of ways of selecting an even
number of elements from a set of $n$ equals the number of ways of
selecting an odd number.

$$\sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k} = 2^{n-1}$$
$$ \mbox{LHS} = \frac{(*)+(**)}{2} = \mbox{\# ways to pick even} = 2^{n-1}$$
Pascal's identity:
\[
(x+y)^n = x(x+y)^{n-1} + y(x+y)^{n-1}
\]
Vandermonde:
\[
(1+t)^{m+n} = (1+t)^m(1+t)^n
\]

\section{General Binomial Theorem}

\begin{defin}
  {\bf General binomial coefficient} $\binom{\alpha}{k}$ for $\alpha
  \in \reals$ and $k\in \naturals$:
  \begin{eqnarray*}
    \binom{\alpha}{k} &= \frac{1}{k!}\prod_{j=0}^{k-1}(\alpha-j)\\ & =
    &\frac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!} \\
    \binom{\alpha}{0} &= 1
  \end{eqnarray*}
\end{defin}

\begin{theorem}
  Let $\alpha \in \reals$ and $\left| \frac{x}{y} \right| <1$. Then
  $$(x+y)^\alpha=\sum_{k=0}^\infty \binom{\alpha}{k}x^{\alpha-k}y^k$$
\end{theorem}

\begin{proof}
  Calculus.
\end{proof}

\begin{xample}
  Approximate $\sqrt{2}$ \\
  $$\sqrt{2} = (x+y)^{\frac{1}{2}}, \; \mbox{where} \; x=1,y=1, \;
  \mbox{but}\; \left| \frac{x}{y} \right| \not < 1$$
  $$ \sqrt{2} =
  2\frac{\sqrt{2}}{2}=2\sqrt{\frac12}=2(1-\frac12)^{\frac12}=2(x+y)^{\frac12},
  \; \mbox{where} \; x=1, y=-\frac12 $$ 
  $$(1-\frac12)^{\frac12} = \sum_{k=0}^\infty \binom{\frac12}k
  \left(-\frac12 \right)^k $$
    $$ \binom{\frac12}0=1, \binom{\frac12}1=\frac12,
    \binom{\frac12}2=\frac{\left( \frac12 \right)\left(-\frac12
    \right)}{2!}=-\frac18, \binom{\frac12}3=\frac{\left( \frac12
  \right)\left(-\frac12\right)\left(-\frac32\right)}{3!}=\frac1{16},
etc. $$
\begin{eqnarray*}
  \sqrt{2} &= 2\left(
  1+\frac12\left(-\frac12\right)+\left(-\frac18\right)
  \left(\frac14\right)+\left(\frac1{16}\right)
    \left(-\frac18\right)+\cdots\right) \\
&= 2\left(1-\frac14-\frac1{32}-\frac{1}{128}-\cdots\right) \\
&\approx 2(.7109375) = 1.421875
\end{eqnarray*} 
\end{xample}

\section{Principle of Inclusion and Exclusion}

Problem: How many numbers form $\{1,\cdots,100\}$ are divisible by 3
or 5?

By 3: $\lfloor \frac{100}3 \rfloor = 33$ \\
By 3: $\lfloor \frac{100}5 \rfloor = 20$ 

3 or 5: Rule of Sum $\Rightarrow 33+20=53$. WRONG! Thus counts number
divisible by 15 twice; must subtract out.

By 15: $\lfloor \frac{100}{15} \rfloor = 6$ 

3 or 5: 33+20-6=47

Venn diagram:
\setlength{\unitlength}{0.0125in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
\begin{picture}(240,155)(0,-10)
\texture{cccccccc 0 0 0 cccccccc 0 0 0 
	cccccccc 0 0 0 cccccccc 0 0 0 
	cccccccc 0 0 0 cccccccc 0 0 0 
	cccccccc 0 0 0 cccccccc 0 0 0 }
\put(130.000,80.000){\shade\arc{100.000}{2.2143}{4.0689}}
\put(130.000,80.000){\arc{100.000}{2.2143}{4.0689}}
\put(70.000,80.000){\shade\arc{100.000}{5.3559}{7.2105}}
\put(70.000,80.000){\arc{100.000}{5.3559}{7.2105}}
\put(70,80){\ellipse{100}{100}}
\put(130,80){\ellipse{100}{100}}
\path(240,0)(240,140)(0,140)
	(0,0)(240,0)
\put(220,120){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}U}}}}}
\put(140,100){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}B}}}}}
\put(40,100){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}A}}}}}
\end{picture}


$|A\cup B|=|A|+|B|-|A\cap B|$

3 sets:

\setlength{\unitlength}{0.0125in}
%
\begingroup\makeatletter\ifx\SetFigFont\undefined
% extract first six characters in \fmtname
\def\x#1#2#3#4#5#6#7\relax{\def\x{#1#2#3#4#5#6}}%
\expandafter\x\fmtname xxxxxx\relax \def\y{splain}%
\ifx\x\y   % LaTeX or SliTeX?
\gdef\SetFigFont#1#2#3{%
  \ifnum #1<17\tiny\else \ifnum #1<20\small\else
  \ifnum #1<24\normalsize\else \ifnum #1<29\large\else
  \ifnum #1<34\Large\else \ifnum #1<41\LARGE\else
     \huge\fi\fi\fi\fi\fi\fi
  \csname #3\endcsname}%
\else
\gdef\SetFigFont#1#2#3{\begingroup
  \count@#1\relax \ifnum 25<\count@\count@25\fi
  \def\x{\endgroup\@setsize\SetFigFont{#2pt}}%
  \expandafter\x
    \csname \romannumeral\the\count@ pt\expandafter\endcsname
    \csname @\romannumeral\the\count@ pt\endcsname
  \csname #3\endcsname}%
\fi
\fi\endgroup
\begin{picture}(300,235)(0,-10)
\put(80,160){\ellipse{114}{114}}
\put(160,160){\ellipse{114}{114}}
\put(120,80){\ellipse{114}{114}}
\put(240,180){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}U}}}}}
\put(160,160){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}B}}}}}
\put(60,160){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}A}}}}}
\put(120,60){\makebox(0,0)[lb]{\smash{{{\SetFigFont{12}{14.4}{rm}C}}}}}
\path(300,0)(300,220)(0,220)
	(0,0)(300,0)
\end{picture}


$|A\cup B|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

In general, for $m$ sets,
$$ \left| \cup_i A_i \right| = \sum_i |A_i| - \sum_{i \neq j} |A_i
\cap A_j| + \sum_{i,j,k \;\mbox{distinct}} |A_i \cap A_j \cap A_k| -
\cdots + (-1)^{m+1}\left| \cap_i A_i \right| $$

Prove by induction on the number of sets.

Often, see inclusion/exclusion stated in terms of what is {\bf not}
in sets $A_i \subseteq U$
$$ \left| \cap_i \overline{A_i} \right| = |U| - \sum_i |A_i| + \sum_{i
  \neq j} |A_i \cap A_j| - \sum_{i,j,k \mbox{distinct}} |A_i \cap A_j
\cap A_k| - \cdots + (-1)^{m}\left| \cap_i A_i \right| $$

For $m$ sets, 1st term has 1 set, 2nd term has m sets, 3rd term has
$\binom{m}{2}$ sets, $\cdots$, $k$th term has $\binom{m}{k}$ sets.

\begin{example}
How many primes less than $100$?  $100$ minus numbers divisible by
$2,3,5$ or $7$ plus these 4 numbers.  Let
\[
P_2 = \mbox{numbers divisible by $i$}
\]
note $\|P_i\| = \lfloor 100/i \rfloor$.

\newcommand{\npart}[1]{{\lfloor \frac{100}{#1} \rfloor}}

Then quantity is:
\begin{eqnarray*}
99 & -&\npart{2}-\npart{3}-\npart{5}-\npart{7}\\
 &+&\npart{2\cdot 3} + \npart {2 \cdot 5} +\npart{2 \cdot 7} + \npart {3
  \cdot 5} +\npart{3 \cdot 7} +\npart {5\cdot 7}\\
&-&\npart{2 \cdot 3 \cdot 5} - \npart {2 \cdot 3 \cdot  7} - \npart{2
  \cdot 5 \cdot 7} - \npart{3 \cdot 5 \cdot 7}\\
&+&\npart{2 \cdot 3 \cdot 5 \cdot 7}
\end{eqnarray*}
which is
\[
99-50-33-20-14+16+10+7+6+4+2-3-2-1-0+0=21
\]
so there are 25 primes.
\end{example}

\end{document}
