\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Lecture 1: Fundamental Combinatorial Objects}

{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

\bigskip

We will study four combinatorial objects

\begin{itemize}
\item[1] sets and subsets
\item[2] strings and permutations
\item[3] graphs
\item[4] trees
\end{itemize}

Example \ Sets and Subsets

\vspace*{4cm}
\end{frame}

\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

{\bf \large Strings}

\begin{definition}[ alphabet and string ]
An {\bf alphabet} $\Sigma$ is a set of $n$ elements called {\bf letters}. \\
A {\bf string} $S$ of size $n$ is an ordered sequence of $n$ letters from $\Sigma$.
\end{definition}

\bigskip
Examples \quad  {\large $\Sigma = \{0,1\}$} \hspace*{2cm} {\large $\Sigma = \{A,C,G,T\}$}

\vspace{5cm}

Exercise \ How many DNA sequences are there of length $n$ ?
\end{frame}

\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

Example \ Find all strings of length 6 over $\{0,1\}$ that 
don't have 10 as a substring.

\vspace*{12cm}
\end{frame}


\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

{\bf \large Permutations}

\begin{definition}[ permutation ]
A {\bf permutation} $P$ over an alphabet $\Sigma$ is a string over $\Sigma$ where
every letter occurs exactly once.
\end{definition}

Example \ $\Sigma = \{1,2,3\}$ find all permutations.

\vspace*{4.5cm}
\begin{theorem} The number of permutations of a set of $n$ objects is $n!$.
\end{theorem}

\end{frame}

%\normalsize
% Jamie, I deleted this because I went 5 mins over time.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}
%
%{\bf Permutations are used in cryptography as functions. }
%
%\vspace{2cm}
%\input{perm}
%\vspace{3cm}
%
%\end{frame}


\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

{\bf \large Graphs}

\begin{definition}[ graph ]
A (simple) {\bf graph} $G$ is a pair $(V,E)$ where $V$ is a set of {\bf vertices}
and $E$ is a set of unordered pairs of vertices called {\bf edges}.  
If $e=\{i,j\} \in E$ we say vertices $i$ and $j$ are {\bf adjacent}.
The {\bf degree} of a vertex is the number of adjacent vertices.
\end{definition}
Example \ $\blue V = \{1,2,3,4,5,6\}$, 
$\dblue E = \{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{1,5\},\{2,5\},\{4,6\}$


\vspace{5cm}

\end{frame}

\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

{\bf Question.} \ How many edges can a graph with $n$ vertices have?

\vspace{6.5cm}


\begin{definition}[ complete graph ]
A graph $G=(V,E)$ is {\bf complete} if $|V| \ge {\bf 1}$
and for all $i,j \in V$ the edge $\{i,j\} \in E$. \quad
The complete graph with $n$ vertices is denoted $K_n$.
\end{definition}

\end{frame}

\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

\begin{definition}[ path graph ]
A graph $G=(V,E)$ is a {\bf path} if $|V| \ge {\bf 1}$ 
and $V$ may be ordered $v_1,v_2,\dots,v_n$ so that
$E  = \{ \{v_1,v_2\}, \{v_2,v_3\},\dots,\{v_{n-1},v_n\} \}$.
The path graph with $n$ vertices is denoted $P_n$.
\end{definition}

\begin{definition}[ cycle graph ]
A graph $G=(V,E)$ is a {\bf cycle} if $|V| \ge {\bf 3}$ and $V$ may be ordered
$E  = \{ \{v_1,v_2\}, \{v_2,v_3\},\dots,\{v_{n-1},v_n\}, \{v_n,v_1\} \}$.  The cycle graph with $n$ vertices is denoted $C_n$.
\end{definition}

Examples

\vspace{4cm}

\end{frame}

\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

\begin{definition}[ connected graph ]
A graph $G=(V,E)$ is {\bf connected} if there is a path in $G$ from
vertex $i \in V$ to vertex $j$ for all $i\ne j$.
\end{definition}

\begin{definition}[ tree ]
A graph $G=(V,E)$ is a {\bf tree} if it is connected and has no cycles.
\end{definition}

Example.  All (unlabelled) trees with 4 vertices.

\vspace*{4cm}

Exercise. Draw all (unlabelled) trees with 5 vertices. \\
% There are 3
% Exercise. Draw all labelled trees with 5 vertices.
% There are 60,60,5 in each class path, fork, spoke

Exercise. If $G$ is a tree with $n>0$ vertices, how many edges must $G$ have?

\end{frame}

