Return-Path: <mslevine@theory.lcs.mit.edu>
Received: from condor.lcs.mit.edu by theory.lcs.mit.edu (5.65c/TOC-1.2S) 
	id AA18894; Thu, 26 Oct 95 13:49:03 EDT
From: mslevine@theory.lcs.mit.edu (Matthew S. Levine)
Received: by condor.lcs.mit.edu (5.65c/TOC-1.2C) 
	id AA00367; Thu, 26 Oct 95 13:45:38 EDT
Date: Thu, 26 Oct 95 13:45:38 EDT
Message-Id: <199510261745.AA00367@condor.lcs.mit.edu>
To: karger
Status: R

\documentstyle[12pt,twoside,amsfonts, amstex, amssymb]{article}
\input{macros-course}

\parskip1.5ex
\parindent0pt

\begin{document}
\handout{notes??}{Notes ??}{October 31, 1995}

\section{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}

Pascal's Triangle:
\begin{align*}
  &1 \\
1 &\; 1 \\
1\; &2\; 1 \\
1 \; 3 &\; 3 \; 1 \\
1 \; 4\; &6 \; 4 \; 1
\end{align*}

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

\begin{proof}
  (Combinatorial) 
  $$ (x+y)(x+y)(x+y)(x+y) \;\; n=4 \; \text{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}

\section{Identities}

\begin{gather}
  \sum_{k=0}^n \binom{n}{k} = 2^n. \;\; \text{Plug in} \; x=1,y=1.
  \tag{*} \\
  \sum_{k=0}^n (-1)^k\binom{n}{k} = 0. \;\; \text{Plug in} \; x=-1,y=1.
  \tag{**} 
\end{gather}

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}$$
$$ \text{LHS} = \frac{(*)+(**)}{2} = \text{\# ways to pick even} = 2^{n-1}$$

$$\sum_{k=0}^n k\binom{n}{k} = n2^{n-1}$$
Plug in $y=1$ and then differentiate binomial theorem with respect to
$x$.
$$ n(x+1)^{n-1} = \sum_{k=1}^n \binom{n}{k}x^{k-1} = \sum_{k=0}^n
\binom{n}{k}x^{k-1} $$
Plug in $x=1$.

\section{General Binomial Theorem}

\begin{defin}
  {\bf General binomial coefficient} $\binom{\alpha}{k}$ for $\alpha
  \in \reals$ and $k\in \naturals$:
  \begin{align*}
    \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{align*}
\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}}, \; \text{where} \; x=1,y=1, \;
  \text{but}\; \left| \frac{x}{y} \right| \nless 1$$
  $$ \sqrt{2} =
  2\frac{\sqrt{2}}{2}=2\sqrt{\frac12}=2(1-\frac12)^{\frac12}=2(x+y)^{\frac12},
  \; \text{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{align*}
  \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{align*} 
\end{xample}

\section{Multinomial Theorem}

\begin{theorem}
  \begin{align*}
    \left( \sum_{k=1}^t x_k \right)^n &=
      \sum_{n_1+n_2+\cdots+n_t=n} \frac{n!}{n_1!n_2!\cdots
        n_t!}x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t} \\
      &= (x_1+x_2+\cdots+x_t)(x_1+x_2+\cdots+x_t)\cdots(x_1+x_2+\cdots+x_t)
  \end{align*}
\end{theorem}

\begin{proof}
  (Combinatorial) For each $(n_1,n_2,\cdots,n_t)$, the number of ways
  $x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t}$ occurs is the number of
  permutations with these $n_i$ as repeat counts.
\end{proof}

\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:
\vspace*{1in}

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

3 sets:

\vspace*{1in}

$|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 \;\text{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 \text{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{xample}
  How many 10-combinations of multiset $X=\{2\cdot a,3\cdot b, 6\cdot
  c\}$?

Consider $Y=\{\infty\cdot a,\infty\cdot b, \infty\cdot c\}$ \\
Let $U$=10-combs of $Y$. $|U|=\binom{10+2}{2}=\frac{12\cdot 11}{2}=66$
(*s and |s)

\begin{align*}
  \text{Let} A &\subseteq U = 10 \text{-combs of} \;Y\;\text{with}\;
  \geq 3 a\text{s} \\
  B &\subseteq U = 10 \text{-combs of} \;Y\;\text{with}\;
  \geq 4 b\text{s} \\
  C &\subseteq U = 10 \text{-combs of} \;Y\;\text{with}\;
  \geq 7 c\text{s} \\
\end{align*}
  
10-combs of $X=\overline{A} \cap \overline{B} \cap \overline{C}$

By inclusion/exclusion,
$$ |X| = |U|-(|A|+|B|+|C|)+(|A \cap B|+|A \cap C|+|B \cap C|)-(|A \cap
B \cap C|) $$

$A$ has 10-combs of $Y$ with $\geq 3a$s. Bijection from $A$ to
7-combs of $Y$ by removing 3 $a$s. (Reverse direction: add 3 $a$s to
7-combs of $Y$)

$$|A| = \binom{7+2}{2}=\binom{9}{2} = \frac{9\cdot 8}{2} = 36 $$

Similar bijections for $B$ and $C$ give:

$$|B| = \binom{6+2}{2}=\binom{8}{2} = \frac{8\cdot 7}{2} = 28 $$
$$|C| = \binom{3+2}{2}=\binom{5}{2} = \frac{5\cdot 4}{2} = 10 $$

$A \cap B$: 10-combs of $Y$ with $\geq 3a$s and $\geq4b$s. Bijection
from $A \cap B$ to 3-combs of $Y$ by removing 3 $a$s and 4 $b$s.

\begin{align*}
  |A \cap B| &= \binom{3+2}{2} = 10 \\
  |A \cap C| &= 1 \\
  |B \cap C| &= 0 \\
  |A \cap B \cap C| &= 0 
\end{align*}

$$ \therefore |X| = 66-(36+28+10)+(10+1+0)-0=17 $$

\end{xample}
\end{document}
