%% 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{graphicx}
\usepackage{amssymb}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\noun}[1]{\textsc{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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*{example*}{Exemple}
 \theoremstyle{definition}
 \newtheorem*{defn*}{Définition}
 \theoremstyle{definition}
  \newtheorem{xca}{Exercice}
 \theoremstyle{remark}
 \newtheorem*{rem*}{Remarque}
 \theoremstyle{plain}    
 \newtheorem*{thm*}{Théorème} 
 \theoremstyle{definition}
  \newtheorem{problem}[thm]{Problem}
 \theoremstyle{plain}    
 \newtheorem*{conjecture*}{Conjecture} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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{Functions (section 4.4)}


\section{Introduction}

The notion of function is pretty natural, and used in many domains
(programming languages, calculus, \ldots{}). So far, the intuitive
notion of function was sufficient, but we now need a more formal definition,
and we will use relations for this.

We will also see how certain functions, called bijections, provide
powerful counting methods.

\begin{example*}
Let $S$ be a set of cars and $T$ be the set of all colors. 

Consider the relation {}``is of color''.

What properties does this relation have ?\char`\"{}

%

%

%

%

%

%%

You can speak about THE color of the car: uniquely defined.
\end{example*}

\section{Formal definition of functions}


\subsection{Functions with one variable}

\begin{defn*}
A \emph{function} $f:\textrm{ }S\textrm{ }\rightarrow\textrm{ }T$
between two sets $S$ and $T$ is a relation such that any element
$s$ of $S$ is in relation with a unique element of $T$. 

\vspace{0.3cm}
\begin{center}\includegraphics{function}\end{center}
\vspace{0.3cm}

This unique element, denoted $f(s)$ is the \emph{image} of $s$.

If $f(s)=y$, then $s$ is a \emph{preimage} of $y$.
\vspace{0.3cm}

$S$ is the \emph{domain} of $f$;

$T$ is the \emph{codomain} of $f$;

The set $\{ f(s)\textrm{ },\textrm{ }s\in S\}$ is the \emph{range}
of $f$.
\end{defn*}
\begin{example*}
The identity on a set $S$ if the function $id_{S}:S\rightarrow S$
defined by $id_{S}(x):=x$.
\end{example*}
One way to define a function is to provide an equation, or any other
mean that allows to compute the image of an element of the domain.

\begin{example*}
$f(n):=n+2$;

$f(L):=sort(L)$;

$f(x):=[x]$.
\end{example*}
\begin{defn*}
\emph{Graph} of a function from $\R$ to $\R$ (or any subset of them):
\end{defn*}
\begin{xca}
Draw the graphs of the functions $f(x)=x^{2}$, $g(x)=\sqrt{x}$,
and $h(x):=\left|x\right|$.
\end{xca}

\subsection{Functions with several variables}

The argument of a function does not need to be a simple number.

\begin{example*}
$f(x,y)=x^{2}+2xy$
\end{example*}
\begin{defn*}
A function with $n$ variables is a function whose argument is a $n$-uple:

\[
f\textrm{ }:\textrm{ }S_{1}\times\cdots\times S_{n}\textrm{ }\rightarrow\textrm{ }T.\]

\end{defn*}
\begin{example*}
Here are a few functions with several variables:
\end{example*}
\begin{itemize}
\item $f\textrm{ }:\{ students\}\times\{ test1,test2,final\}\textrm{ }\rightarrow\textrm{ }\{1,2,\ldots,100\}$
\[
f(Jason,test2):=\cdots\]

\item $f:\textrm{ }\{ True,False\}^{3}\textrm{ }\rightarrow\textrm{ }\{ True,False\}$\[
f(A,B,C)=(A\wedge B)'\wedge C\]

\end{itemize}

\subsection{Equality of functions}

\begin{example*}
Are the functions $f(x):=x$ and $g(x):=\left|x\right|$ equal ?
\end{example*}
%

%

%

%

%

%%

\begin{defn*}
Two functions $f$ and $g$ are \emph{equal} iff they have same domain
$S$, same codomain $T$, and $f(x)=g(x)$ for all $x$ in $S$.
\end{defn*}

\section{Properties of functions}


\subsection{Injective, surjective and bijective functions}

\begin{example*}
Let $P$ be the set of all residents in America;

let $N$ be the set of all assigned Social Security Number (SSN);

let $SSN:\textrm{ }P\rightarrow N$ be the function which assigns
to each person $x$ its SSN $SSN(x)$.
\end{example*}
A Social Security Number is useful because it uniquely describes a
person!

That is, given an assigned SSN, you can find the person having this
SSN.

\begin{defn*}
The function $SSN$ is \emph{invertible}.

The \emph{inverse} of the function $SSN$ is the function $SSN^{-1}:\textrm{ }N\rightarrow P$
such that: 

$SSN^{-1}(n)$ is the person having $n$ as SSN.
\end{defn*}
What properties does a function need to be invertible?

%

%

%

%

%

%%

To be invertible, a function needs to have the two following properties:

\begin{defn*}
A function $f\textrm{ }:S\textrm{ }\rightarrow\textrm{ }T$ is \emph{injective}
(\emph{one-to-one}) iff

\[
(\forall x\in S)(\forall y\in S)\textrm{ }(f(x)=f(y))\rightarrow(x=y)\]
 

{}``If x and y have the same SSN, then x is the same person as y''
\begin{defn*}
A function $f\textrm{ }:S\textrm{ }\rightarrow\textrm{ }T$ is \emph{surjective}
(\emph{onto}) iff
\end{defn*}
\[
(\forall y\in T)(\exists x\in S)\textrm{ }f(x)=y\]


{}``For any assigned SSN, there is a person which has this SSN.''
\begin{defn*}
A function $f\textrm{ }:S\textrm{ }\rightarrow\textrm{ }T$ is \emph{bijective}
iff it's injective and surjective.
\end{defn*}
\end{defn*}
\begin{xca}
Which one of the following functions from $\R$ to $\R$ are bijective?
\end{xca}
\begin{enumerate}
\item $f(x):=x^{2}$;
\item $f(x):=x^{3}$;
\item $f(x):=\frac{1}{1+x^{2}}$;
\item $f(x):=\exp(x)$;
\item $f(x):=\log(x)$;
\end{enumerate}

\subsection{Composition of functions}

\begin{defn*}
Let $f:S\rightarrow T$ and $g:T\rightarrow U$ be two functions.

The \emph{composition function} $g\bullet f$ is the function from
$S$ to $U$ defined by\[
g\bullet f(x):=g(f(x)).\]

\end{defn*}
\begin{rem*}
The standard symbol for composition is an empty circle! In those notes
a full circle is used instead due to a bug in lyx ...
\end{rem*}
\begin{xca}
Define $f:\R\rightarrow\R$ by $f(x):=x+1$, and $g:\R\rightarrow\R$
by $g(x):=x^{2}$.

What is the value of $g\bullet f(1)$? What is $g\bullet f$?

What is the value of $f\bullet g(1)$? What is $f\bullet g$?
\end{xca}
\begin{thm*}
Let $f:S\rightarrow T$ and $g:T\rightarrow U$ be two functions.

%

%

%

%

%%
\end{thm*}
\begin{enumerate}
\item If $f$ and $g$ are injective, then $g\bullet f$ is injective.
\item If $f$ and $g$ are surjective, then $g\bullet f$ is surjective.
\item If $f$ and $g$ are bijective, then $g\bullet f$ is bijective.
\end{enumerate}
\begin{proof}
3. is a direct consequence of 1 and 2.
\begin{enumerate}
\item Assume $f$ and $g$ are injective. We have :\[
(\forall x)(\forall y)\textrm{ }(f(x)=f(y))\textrm{ }\rightarrow\textrm{ }(x=y)\]
 \[
(\forall x)(\forall y)\textrm{ }(g(x)=g(y))\textrm{ }\rightarrow\textrm{ }(x=y)\]
 We want to prove that :\[
(\forall x)(\forall y)\textrm{ }(g\bullet f(x)=g\bullet f(y))\textrm{ }\rightarrow\textrm{ }(x=y)\]
Take $x$ and $y$ such that $g\bullet f(x)=g\bullet f(y)$\\
By definition $g(f(x))=g(f(y))$.\\
Then, since $g$ is injective, $f(x)=f(y)$. \\
Since $f$ is also injective $x=y$. \\
We are done!
\item Left as exercise.
\end{enumerate}
\end{proof}

\subsection{Inverse of function}

\begin{example*}
If you take the SSN of a person, and then lookup the person having
this SSN, you will get back the original person. That is, composing
the function $SSN$ and the function $SSN^{-1}$ yields the identity.
\end{example*}
\begin{defn*}
Let $f:S\rightarrow T$ be a function. 

If there exists a function $g:T\rightarrow S$ such that $g\bullet f=id_{S}$
and $f\bullet g=id_{T}$, then $g$ is called the \emph{inverse function}
of $f$, and is denoted $f^{-1}$.
\end{defn*}
\begin{thm*}
A function $f$ is bijective iff its inverse $f^{-1}$ exists.
\end{thm*}
\begin{xca}
Give the inverses (if they exists!) of the following functions:
\begin{enumerate}
\item $f(x):=x-1$;
\item $f(x):=x^{2}$;
\item $f(x):=x^{3}$;
\item $f(x):=\exp(x)$.
\end{enumerate}
\end{xca}

\section{Functions and counting}


\subsection{Injections, surjections, bijections and cardinality of sets}

\begin{example*}
You distribute $n$ different cakes between $k$ child.

Such a distribution can be formalized by a function $f$: 

$f(4)=5$ means that the $4$th cake is given to the $5$th child.
\end{example*}
\begin{enumerate}
\item Suppose $f$ is injective. 

\begin{itemize}
\item What does it mean ?
\item What can you say about $n$ and $k$ ?$k\geq n$
\end{itemize}
\item Suppose $f$ is surjective. 

\begin{itemize}
\item What does it mean ?
\item What can you say about $n$ and $k$ ?
\end{itemize}
\item Suppose $f$ is bijective. 

\begin{itemize}
\item What does it mean ?
\item What can you say about $n$ and $k$ ?
\end{itemize}
\end{enumerate}
\begin{thm*}
Let $S$ and $T$ be two sets.

If there exists an injective function between $S$ and $T$, then
$\left|S\right|\leq\left|T\right|$. 

If there exists a surjective function between $S$ and $T$, then
$\left|S\right|\geq\left|T\right|$. 

If there exists a bijective function between $S$ and $T$, then $\left|S\right|=\left|T\right|$. 
\end{thm*}
Note that we have never given a formal definition of the size of a
set. 

We just relied on the intuitive notion.

In set theory, the theorem above is actually the definition of cardinality:

\begin{itemize}
\item Two sets have the same cardinality (size), iff they are in bijection.
\item A set is of size $n$ iff it's in bijection with $\{1,\ldots,n\}$.
\end{itemize}

\subsection{Examples of bijections}


\subsubsection{Finite and countable sets}

Do you remember how we proved that $Z$ was countable ?

\begin{itemize}
\item A set $S$ is finite if there is an enumeration $s_{1},\ldots,s_{k}$
of $S$.\\
 This enumeration is actually a bijection from $\{1,\ldots,k\}$ to
$S$!
\item A set $S$ is denumerable if there is an enumeration $s_{1},\ldots,s_{k},\ldots$
of $S$.\\
This enumeration is actually a bijection from $\N$ to $S$!
\end{itemize}

\subsubsection{Y/B buildings, 0/1 strings and pairs of rabbits}

\begin{problem}
Counting: 
\begin{enumerate}
\item buildings with yellow and blue floors, without consecutive yellow
floors.
\item strings of $0$ and $1$ without two consecutive $1$. 
\end{enumerate}
\end{problem}
The answer in both case is the Fibonacci sequence.

Those two problems are fundamentally the same:

There is a bijection between solutions of the first and solutions
to the second!

So if you solve the one of them, you solve both of them.

\begin{problem}
Counting pairs of rabbits after $n$ generations (ex 29 p. 140).
\end{problem}
Here also the solution is the Fibonacci sequence.

Can you find the bijection ?


\subsubsection{Strings of well-balanced parenthesis and Dyck paths}

A string of well-balanced parenthesis is a string such as \texttt{\noun{(()())}}\textsf{\noun{,}}
where each open parenthesis is closed and vice versa.

\begin{defn*}
A Dyck path of size $n$, is a path in $\N\times\N$ from $(0,0)$
to $(2n,0)$ such that each step is either $(1,1)$ or $(1,-1)$.

\vspace{0.3cm}
\begin{center}\includegraphics{Dyck} \end{center}

The important fact is that such a path never goes under the x-axis.
\end{defn*}
\begin{xca}
Find all strings of well-balanced parenthesis of length $0$, $2$,
$4$,$6$, $8$, $10$.

Find all Dyck paths of size $0$, $1$, $2$, $3$, $4$.
\end{xca}
Do you notice something ?

\begin{conjecture*}
There are as many Dyck paths of size $n$ than strings of well balanced
parenthesis of length $2n$.
\end{conjecture*}
How to prove this conjecture?

Let $D$ be the set of Dyck paths of size $n$.

Let $S$ be the set of strings of well balanced parenthesis of length
$2n$.

We just have to construct a bijection $f:S\rightarrow D$.

Take $s=s_{1}\cdots s_{2n}\in S$, and build a path $f(s)$ in the
following way: 

read $s$ from left to right; if $s_{i}$ is a \texttt{(}, go right
and up, else go right and down.

\begin{xca}
Draw $f(s)$ for the following strings: \texttt{()}, \texttt{()()},
\texttt{((()(())())())}.
\end{xca}
Why is $f(s)$ indeed a Dyck path of size $n$?

\begin{itemize}
\item There are $2n$ steps to the right
\item In $s$, there are as many $'('$ as $')'$, so the final position
is $(2n,0)$.
\item At any position $i$ in $s$, there are more $'('$ than $')'$ before
$i$.
\end{itemize}
How to prove that $f$ a bijection ?

Lets try to construct an inverse $g$ for $f$:

Take a path $p$, and build a string $g(p)$ in the following way:
go through $p$ from left two right. For each up step, add a \texttt{$'('$}
to $g(p)$, and for each down step, add a \texttt{$')'$}.

\begin{xca}
Apply $g$ to the paths obtained in the previous exercises.
\end{xca}
For the same reasons as above, the resulting string $g(p)$ is a string
of well balanced parenthesis.

Moreover, by construction $f(g(p))=p$ for any $p\in D$ and $g(f(s))=s$,
for any $s\in S$.

So $g$ is indeed an inverse for $f$. 

Therefore, $f$ is a bijection and consequently $\left|S\right|=\left|D\right|$,
as wanted.


\subsubsection{Ordered trees and strings of well-balanced parenthesis}

\begin{defn*}
The set of all ordered trees can be defined recursively as follow:
\end{defn*}
\begin{itemize}
\item A single node is an ordered tree
\item If $t_{1},\ldots,t_{k}$ are $k$ ordered trees, the structure obtained
by adding a common father to $t_{1},\ldots,t_{k}$ is an ordered tree.
\end{itemize}
\begin{xca}
Draw all ordered trees on $1,2,3,4,5$ nodes.
\end{xca}
\begin{example*}
Prove that any ordered tree on $n$ nodes has $n-1$ edges.

%

%

%

%

%

%%

Ordered trees are defined recursively, so using recursion seems reasonable.

The property is true on a tree with one node.

Let $t$ be a tree on $n>1$ nodes. 

Assume the property is true for any tree of size $<n$. 

By construction, $t$ is build by adding a common father to $k$ trees
$t_{1},\ldots,t_{k}$.

Let $n_{i}$ be the number of nodes of $t_{i}$. 

We have $n=n_{1}+\cdots+n_{k}+1$.

Clearly $n_{i}<n$, so by induction each $t_{i}$ has $n_{i}-1$ edges.

Conclusion: the number of edges of $t$ is :

\[
(n_{1}-1)+\cdots+(n_{k}-1)+k=n_{1}+\cdots+n_{k}=n-1.\]

\end{example*}
\begin{thm*}
There are as many trees with $n$ nodes as strings of well balanced
parenthesis of length $2(n-1)$.
\end{thm*}
%

%

%

%

%

%

%%

Let's define recursively a bijection $f$ between trees and well balanced
parenthesis:

\begin{itemize}
\item If $t$ has a single node, then $f(t)$ is the empty string;
\item If $t$ is build from $k$ subtrees $t_{1},\ldots,t_{k}$, then $f(t):=(f(t_{1}))\cdots(f(t_{k}))$.
\end{itemize}
\begin{xca}
Apply $f$ to a few trees.
\end{xca}
Here also, it's easy to construct the inverse of $f$, so $f$ is
a bijection.

Since $f$ maps trees on $n$ nodes on strings of length $2(n-1)$,
and vice-versa, we are done with the proof of the theorem.


\subsubsection{Catalan Numbers}

We have seen that many different kind of objects (trees, strings of
well balanced parenthesis, Dyck paths) are counted by the same sequence
of numbers: \[
1,1,2,5,14,\ldots\]


This sequence is called the Catalan sequence $C(0),C(1),C(2),C(3),\ldots$.

\begin{problem}
What is the value $C(n)$ ?
\end{problem}
It's enough to count, for example, the number of Dyck paths of length
$2n$.

There is a beautiful trick to do this. It's called \emph{André's inversion
principle}.

Will you find it ?


\section{Conclusion}

\begin{itemize}
\item There are often connections between apparently unrelated objects (trees,
strings of well balanced parenthesis, Dyck paths, ...).
\item Those connections, formalized by bijections, provide powerful methods
for counting objects.
\item The Sloane is very handy to suggest connections! 
\end{itemize}

\end{document}
