%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{amsbook}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\setlength\parskip{\smallskipamount}
\setlength\parindent{0pt}
\usepackage{amssymb}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\noun}[1]{\textsc{#1}}
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \numberwithin{section}{chapter}
 \theoremstyle{plain}    
 \newtheorem{thm}{Theorem}[section]
 \numberwithin{equation}{section} %% Comment out for sequentially-numbered
 \numberwithin{figure}{section} %% Comment out for sequentially-numbered
 \theoremstyle{definition}
 \newtheorem*{defn*}{Définition}
 \theoremstyle{remark}    
 \newtheorem*{note*}{Note} 
 \theoremstyle{definition}
  \newtheorem*{example*}{Exemple}
 \theoremstyle{plain}    
 \newtheorem*{thm*}{Théorème} 
 \theoremstyle{definition}
  \newtheorem{xca}{Exercice}
 \theoremstyle{definition}
  \newtheorem{problem}[thm]{Problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}

\usepackage[francais,american]{babel}
\makeatother
\begin{document}

\chapter{Combinatorics (section 3.2\ldots{}3.5)}


\section{Introduction}

Goal: answer \emph{{}``How many ?''} questions:

\begin{itemize}
\item How many ways to climb a stair ?
\item How many rows in a truth table ?
\item How many trees ?
\end{itemize}
Applications:

\begin{itemize}
\item Analysis of algorithms
\item Statistics
\item Size of a database
\end{itemize}

\section{Counting}


\subsection{Preliminaries}

\begin{defn*}
The \emph{size} of a finite set is the number of elements in this
set.

The size of $S$ is denoted by $\left|S\right|$ (or, often in the
literature, $\# S$).
\end{defn*}
\begin{note*}
In the sequel, we only consider finite sets !
\end{note*}
A\emph{{}``how many ?''} question is usually formalized as follow: 

\begin{enumerate}
\item Define the set $S$ of the objects to be counted
\item What is the size of $S$ ?
\end{enumerate}
Techniques to answer this question:

\begin{itemize}
\item breakup $S$ as some combination of simpler sets
\item transform $S$ into a set, the size of which is already known
\end{itemize}

\subsection{The addition principle}

\begin{example*}
A small company wants to know how many computers it owns, given that
it owns $5$ Mac's, and $3$ UNIX stations. 

Let:
\begin{itemize}
\item $C$ be the sets of computers, 
\item $M$ be the set of Mac's ($\left|M\right|=5$),
\item $U$ be the set of UNIX stations ($\left|U\right|=3$).
\end{itemize}
Then, $C=M\cup U$.

What is the size of $C$ ?

\[
\left|C\right|=\left|M\right|+\left|U\right|=5+3=8\]

\end{example*}
\begin{thm*}
(Addition principle) Let $A$ and $B$ be disjoint sets (e.g. $A\cap B=\emptyset$).
Then: \[
\left|A\cup B\right|=\left|A\right|+\left|B\right|.\]

\end{thm*}
\begin{example*}
Imagine $2$ of the $5$ Mac's are actually running Linux.

What is the size of $C$ ?

Well, $\left|C\right|=6<8$.
\end{example*}
So, the disjoint hypothesis is important ! 

What to do when the sets are not disjoint ?

\begin{thm*}
Let $A$ and $B$ be two sets. Then:

\[
\left|A\cup B\right|=\left|A\right|+\left|B\right|-\left|A\cap B\right|.\]

\end{thm*}
%

%

%

%

%

%

%

\begin{proof}
We just have to split $A$, $B$, and $A\cup B$ into unions of disjoint
subsets:

\[
A=(A-B)\cup(A\cap B)\]


\[
B=(B-A)\cup(A\cap B)\]


\[
A\cup B=(A-B)\cup(A\cap B)\cup(B-A).\]


(Practice: draw and prove those set identities!).

Then,

\begin{eqnarray*}
\left|A\right|+\left|B\right|-\left|A\cap B\right| & = & (\left|A-B\right|+\left|A\cap B\right|)+(\left|B-A\right|+\left|A\cap B\right|)-\left|A\cap B\right|\\
\, & = & \left|A-B\right|+\left|A\cap B\right|+\left|B-A\right|\\
\, & = & \left|A\cup B\right|\end{eqnarray*}

\end{proof}
\begin{example*}
In the example above, $\left|C\right|=\left|M\right|+\left|U\right|-\left|M\cap U\right|=5+3-2=6$.
\end{example*}
\begin{xca}
There are $24$ students in a class, all of them are math majors or
computer science major. $10$ are math majors, and $20$ are computer
science majors. How many double-major are there in this class ?
\end{xca}

\subsection{The multiplication principle}

\begin{example*}
You are a car dealer. For each car you sell, you propose several options
(color, 2WD/4WD, airbag, ABS, radio, \ldots{}). Of course, you would
like to always have all possible combinations of options in stock.
On the other hand, you cannot afford to store too many cars in your
parking lot. So you need to know how many possible combinations of
options there are.
\begin{itemize}
\item 2WD / 4WD
\item Black / Yellow / Green
\end{itemize}
How many combinations are there ?

First solution: draw a \emph{decision tree}.

The choices are independent! 

The number of sub-branches at each level is constant.

Therefore, we have $2\cdot3=6$ choices.

Let's formalize this.

Let $C$ be the set of all choices. Each choice can be represented
by a couple. 

For example a yellow 2WD car with black seats can be represented as:

\[
(2,Y)\]


So, $C$ can be viewed as the cross product:

\[
\{2,4\}\times\{ B,Y,G\}.\]

\end{example*}
\begin{thm*}
Let $A$ and $B$ be two sets. Then,

\[
\left|A\times B\right|=\left|A\right|\cdot\left|B\right|.\]

\end{thm*}
\begin{example*}
In the example above, $\left|C\right|=\left|\{2,4\}\times\{ B,Y,G\}\right|=\left|\{2,4\}\right|\cdot\left|\{ B,Y,G\}\right|=2\cdot3=6$.
\begin{xca}
How many possible different phone numbers are there ?
\end{xca}
\end{example*}

\subsubsection{Strings}

Strings are commonly used objects in computer science. 

{}``how many'' questions often be translate into questions about
sets of strings.

\begin{defn*}
Let $S$ be a set, that we call \emph{alphabet}. 

Elements of $S$ are called \emph{letters}.

A \emph{string} over $S$ is a sequence $(s_{1},s_{2},\ldots,s_{n})$
of elements of $S$. 

$\lambda:=()$ is the empty string.

The set of all strings of length $n$ is $S^{n}=S\times\cdots\times S$.

The set of all finite strings over $S$ is denoted $S^{*}$.

A \emph{language} is a set of strings.
\end{defn*}
\begin{example*}
Let $S:=\{0,1\}$. A string over $S$, like \texttt{001001} is called
a binary string.

Let $S:=\{ a,b,\ldots,z\}$. Then \texttt{bonjour} is a string over
$S$ of length $7$.

A phone number \texttt{\noun{3032733462}} is a string over $\{0,1,2,3,4,5,6,7,8,9\}$.

The set of all English words is a language.
\end{example*}
%

\begin{example*}
Count the following:
\begin{enumerate}
\item binary strings of length $4$? 
\item strings of length $n$ over an alphabet containing $p$ letters ?
\end{enumerate}
\end{example*}

\subsection{Decision trees}

\begin{example*}
A kid is allowed to pick $3$ candies (one after another), out of
one jelly bean, one lollipop and $2$ gummy bears (one blue, one yellow).
In how many ways can he do this ?

Draw a decision tree.

The choices are not independent

The multiplication principle does not apply.

However, the number of choices at each step does not change!

So the answer is: $5\cdot4\cdot3=60$.
\end{example*}
\begin{xca}
Count the following:
\begin{enumerate}
\item Strings of length $4$ over $\{1,2,3,4,5\}$ with no repetitions.
\item Strings of length $n$ over $\{1,\ldots,n\}$ with no repetitions.
\end{enumerate}
\end{xca}
%

\begin{xca}
How many ways to toss a coin five times without two heads in a row
?

Note: the decision tree is irregular.
\end{xca}

\subsection{Combining those principles together}

\begin{example*}
Count the following:

Exercise 18-19 p. 195
\begin{itemize}
\item Strings of length $n$ over $\{1,\ldots,n\}$ with repetitions.
\item Strings of length $n$ over $\{0,1\}$ with two consecutive $1$.
\item How many four-digits numbers begin with $4$ or $5$? 
\item How many ways to toss a coin seven times with two heads in a row ?
\end{itemize}
\end{example*}

\subsection{Principle of Inclusion and Exclusion}

\begin{example*}
All the guests at a dinner party drink coffee, chocolate or tea; $11$drink
coffee, $9$ drink tea, $10$ drink chocolate; $3$ drink coffee and
tea, $5$ drink tea and chocolate; $6$ drink coffee and chocolate

Formalization: what is the size of $\left|A\cup B\cup C\right|$?
\end{example*}
Generalization ?

%

%

%

%

%

%

%%

\begin{thm*}
(Principle of Inclusion and exclusion)

Let $A_{1},\ldots,A_{n}$ be $n$ sets. Then,

\begin{eqnarray*}
\left|A_{1}\cup\cdots\cup A_{n}\right| & = & \left|A_{1}\right|+\cdots+\left|A_{n}\right|\\
\, & \, & -\left|A_{1}\cap A_{2}\right|-\cdots-\left|A_{n-1}\cap A_{n}\right|\\
\, & \, & +\left|A_{1}\cap A_{2}\cap A_{3}\right|+\cdots\left|A_{n-2}\cap A_{n-1}\cap A_{n}\right|\\
\, & \, & +(-1)^{n+1}\left|A_{1}\cap\cdots\cap A_{n}\right|\\
\, & = & \sum_{I\subset\{1,\cdots,n\}}(-1)^{\left|I\right|+1}\left|\bigcap_{i\in I}A_{i}\right|\end{eqnarray*}
 
\end{thm*}
\begin{proof}
Induction.
\end{proof}

\subsection{Pigeon Hole principle}

\begin{xca}
It's early in the morning, and you don't want to wake up your significant
whatever by turning on the light. You know you only have black and
white socks in your drawer. Is it possible to exit the room with at
least two socks with the same color ?
\end{xca}
\begin{thm*}
(Pigeon hole principle)

If more than $k$ items are placed in $k$ bins, then at least one
bin has more than one item inside.
\end{thm*}
\begin{example*}
How many people do you need to have in a room to ensure at least two
of them have the same birthday ?
\end{example*}

\subsection{Permutations: sequences without repetitions}

\begin{example*}
How many ways to choose a committee with $1$ president and $1$ vice-president
out of a group of $n$ persons.

This amount to find the number of strings of length $2$ over a set
of size $n$, without repetitions. This is $n(n-1)$.
\end{example*}
\begin{defn*}
We denote by $P(n,k)$ the number of strings of length $k$ over a
set of size $n$ without repetitions.
\end{defn*}
\begin{example*}
$P(n,0)=\textrm{ }$, $P(n,1)=\textrm{ }$, $P(n,n)=\textrm{ }$,
$P(1,2)=\textrm{ }$.
\end{example*}
%

%

%

%

%

%%

\begin{thm*}
$P(n,k)=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}$.
\end{thm*}

\subsection{Combinations}

\begin{example*}
How many ways to choose $3$ voluntaries out of a group of $5$ persons?
\end{example*}
\begin{defn*}
We denote by $C(n,k)$ the number of subsets of size $k$ of a set
of size $n$.
\end{defn*}
\begin{example*}
$C(n,0)=\textrm{ }$, $C(n,1)=\textrm{ }$, $C(n,n)=\textrm{ }$,
$C(1,2)=\textrm{ }$.
\end{example*}
%

%

%

%

%

%%

\begin{thm*}
$C(n,k)=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots1}=\frac{n!}{k!(n-k)!}$.
\end{thm*}
\begin{example*}
Ex. 51 p. 210:

A committee of $8$ students is to be selected from a class consisting
of $19$ freshmen and $34$ sophomores.
\end{example*}
\begin{enumerate}
\item In how many ways can $3$ freshmen and $5$ sophomores be selected?
\item In how many ways can a committee with exactly $1$ freshman be selected?
\item In how many ways can a committee with at most $1$ freshman be selected?
\item In how many ways can a committee with at least $1$ freshman be selected?
\end{enumerate}
\begin{example*}
What is the total number of subsets of $S$ ?
\begin{example*}
What is the number of paths between Stratton Hall and Golden Tourism
Information center ?
\end{example*}
\end{example*}

\subsection{Combinations with repetitions}

\begin{example*}
In how many ways can you distribute $10$ lollipops between $4$ kids.
\end{example*}
\begin{thm*}
The number of combinations with repetitions of $k$ elements of a
set $S$ of size $n$ is $C(n+k-1,n)$.
\end{thm*}
\begin{example*}
In how many ways can you distribute $10$ lollipops between $4$ kids,
so that every kid get at least one lollipop ?
\end{example*}

\subsection{Summary}

\vspace{0.3cm}
\begin{center}\begin{tabular}{|c|c|}
\hline 
Addition principle ($A$ and $B$ disjoint)&
$\left|A\cup B\right|=\left|A\right|+\left|B\right|$\tabularnewline
\hline 
Principle of Inclusion-Exclusion&
$\left|A\cup B\right|=$$\left|A\right|+\left|B\right|-\left|A\cap B\right|$$\left|A_{1}\cup\cdots\cup A_{n}\right|=\cdots$\tabularnewline
\hline 
Multiplication principle&
$\left|A\times B\right|=\left|A\right|\cdot\left|B\right|$$\left|A^{k}\right|=\left|A\right|^{k}$\tabularnewline
\hline 
Sequences of $k$ elements of $S$ ($\left|S\right|=n$)&
$n^{k}$\tabularnewline
\hline 
Permutations:&
$P(n,k)=\frac{n!}{(n-k)!}$\tabularnewline
\hline
Sequences of $k$ elements of $S$, w/o repetitions&
\tabularnewline
\hline 
Sequences of $k$ elements of $\{0,1\}$, w/o successive $1$&
Fibonacci: $F(k)$\tabularnewline
\hline
Combinations: subsets of size $k$ of $S$&
$C(n,k)=\frac{n!}{k!(n-k)!}$\tabularnewline
\hline
All subsets of $S$&
$2^{n}$\tabularnewline
\hline
Combinations with repetitions&
$C(n+k-1,k)$\tabularnewline
\hline
\end{tabular}\end{center}
\vspace{0.3cm}


\section{Properties of binomial coefficients; Combinatorial proofs }

\begin{example*}
How many subsets of size $14$ of a set of size $15$ ?
\end{example*}
\begin{thm*}
$C(n,k)=C(n,n-k)$
\end{thm*}
\begin{proof}
~
\end{proof}
\begin{enumerate}
\item Algebraic proof
\item Combinatorial proof
\end{enumerate}
\begin{defn*}
\emph{Combinatorial proof}: 

Goal: prove that two quantities $a$ and $b$ are equal

Technique: 
\end{defn*}
\begin{enumerate}
\item construct a set $A$ of size $a$; 
\item construct a set $B$ of size $b$;
\item construct a \emph{bijection} between $A$ and $B$
\end{enumerate}
\begin{problem}
Recursive computation of $C(n,k)$ ?
\end{problem}
%

%

%

%

%

%%

\begin{thm*}
$C(n,k)=C(n-1,k)+C(n-1,k-1)$
\end{thm*}
\begin{proof}
~
\end{proof}
\begin{enumerate}
\item Algebraic proof
\item Combinatorial proof
\end{enumerate}
\begin{example*}
Compute $C(7,4)$, without calculator.
\end{example*}
\begin{defn*}
Pascal triangle:

\vspace{0.3cm}
\begin{center}\begin{tabular}{|c||c|c|c|c|c|c|c|c|}
\hline 
$n$\textbackslash{}$k$&
$0$&
$1$&
$2$&
$3$&
$4$&
$5$&
$6$&
$7$\tabularnewline
\hline
\hline 
$0$&
1&
&
&
&
&
&
&
\tabularnewline
\hline
$1$&
1&
1&
&
&
&
&
&
\tabularnewline
\hline
$2$&
1&
2&
1&
&
&
&
&
\tabularnewline
\hline
$3$&
1&
3&
3&
1&
&
&
&
\tabularnewline
\hline
$4$&
1&
4&
6&
4&
1&
&
&
\tabularnewline
\hline
$5$&
1&
5&
10&
10&
5&
1&
&
\tabularnewline
\hline
$6$&
1&
6&
15&
20&
15&
6&
1&
\tabularnewline
\hline
$7$&
1&
7&
21&
35&
35&
21&
7&
1\tabularnewline
\hline
\end{tabular}\end{center}
\vspace{0.3cm}

\end{defn*}
%

%

%

%

%%

\begin{thm*}
$C(n,0)+\cdots+C(n,n)=2^{n}$
\end{thm*}
\begin{proof}
~
\end{proof}
\begin{enumerate}
\item Algebraic proof ?
\item Combinatorial proof
\end{enumerate}

\subsection{The binomial theorem}

\begin{problem}
Compute $(x+y)^{n}$ .
\end{problem}
%

%

%

%

%%

\begin{thm*}
There is a formula for expanding $(x+y)^{n}$:

\begin{eqnarray*}
(x+y)^{n} & = & \sum_{k=0}^{k=n}C(n,k)x^{n-k}y^{k}\\
\textrm{ } & = & C(n,0)x^{n}+C(n,1)x^{n-1}y+C(n,2)x^{n-2}y^{2}+\cdots+C(n,n)y^{n}\end{eqnarray*}

\end{thm*}

\section{Conclusion}
\end{document}
