
\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Lecture 2: Basic Counting Principles}
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}
\bigskip

Reading: Grimaldi Sections 1.1, 1.2

\vspace{1.0cm}

{{\bf Lattice paths} arise in theoretical physics.}

\bigskip
\medskip

\quad \quad {
\setlength{\tabcolsep}{10pt}
\renewcommand{\arraystretch}{1.75}
\begin{tabular}{|c|c|c|c|c|c|} \hline
 & & & & & \\ \hline
 & & & & & \\ \hline
 & & & & & \\ \hline
 & & & & & \\ \hline
\end{tabular}
}

\bigskip
\medskip

How many lattice paths are there from $(0,0)$ to $(6,4)$ if we  \\
are restricted to {\blue North} steps and {\blue East} steps only?

\end{frame}

\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}[Rule of Sum]
If there are $m$ ways to perform task $X$ and $n$ ways to perform task $Y$,
there are $m+n$ ways to perform {\bf either} $X$ or $Y$.
\end{definition}


\begin{definition}[Rule of Product]
If there are $m$ ways to perform task $X$ and $n$ ways to perform task $Y$, 
there are $m \, n$ ways to perform {\bf both} $X$ and $Y$.
\end{definition}

Examples.

\vspace{5cm}
\end{frame}

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

Exercise. If there are 10 people at a party and all hug each other, how many hugs are there?

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


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

\begin{theorem} [ Strings ]
If $\Sigma$ is an alphabet with $k$ letters, the number of strings 
of length $n$ over $\Sigma$ is $k^n$.
\end{theorem}

Proof.

\vspace{7cm}
\end{frame}



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

\begin{theorem}[ Permutations ]
The number of permutations of a set of $n$ distinct objects is $n!$.
\end{theorem}

Proof.
\vspace{8cm}
\end{frame}





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

\begin{definition} [ Permultations with Repetition ]
Suppose there $\blue k_1$ objects of type $\blue A$, $\red k_2$ of type $\red B$, \dots, 
and $\dgreen k_r$ of type $\dgreen R$ and let $n = k_1 + k_2 + \dots + k_n$ be the total number of objects.
The number of distinct permutations is denoted by 
$\ds { n \choose { k_1, k_2, \dots, k_r } } .$
\end{definition}

Example.  Consider the letters $M,E,E,N,N$.  How many permutations are there?

\vspace{6cm}

\end{frame}


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

\begin{theorem} [Permutations with Repetition]
 $$ { n \choose {k_1,k_2,\dots,k_r} }  = \frac{n!}{k_1!,k_2!,\dots,k_r!} .$$
\end{theorem}

\noindent
\textbf{Proof.}

\vspace*{6cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}

Exercise. \ How many binary strings of length $20$ are there with exactly $13$ $1$'s?
\vspace{9cm}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}

\begin{theorem} [ Subsets and Combinations ]
If $S$ is a set of size $n$, the number of subsets of size $k$
$\ds {n \choose k} = \frac{n!}{k! (n-k)!}.$
\end{theorem}

{\bf Proof.}

\vspace{8cm} 

\end{frame}

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

{\large {\bf Lattice paths} arise in theoretical physics.}

\bigskip

\quad \quad {
\setlength{\tabcolsep}{10pt}
\renewcommand{\arraystretch}{1.75}
\begin{tabular}{|c|c|c|c|c|c|} \hline
 & & & & & \\ \hline
 & & & & & \\ \hline
 & & & & & \\ \hline
 & & & & & \\ \hline
\end{tabular}
}

\bigskip

How many lattice paths are there from $(0,0)$ to $(6,4)$ if we  \\
are restricted to {\blue North} steps and {\blue East} steps only?

\vspace{4cm}

\end{frame}

