%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Lecture 4: Combinations with repetition: Grimaldi 1.4}

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

\bigskip

How many combinations of size 3 are there from $S = \{a,b,c\}$ if repetitions are allowed?
\vspace{9cm}

\end{frame}

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

\begin{theorem}[ combinations with repetitions ]
Let $S$ be a set with $n$ elements.
The number of ways to select $k$ objects from $S$, with repetition allowed, is
$$
{n+k-1 \choose k}=\frac{(n+k-1)!}{k!(n-1)!}.
$$
\end{theorem}

\textbf{Proof with binary strings.}
\vspace{9cm}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example.  How many integer solutions are there to

$\ds  x_1+x_2+x_3+x_4+x_5 =10$ with $x_i \ge 0$ ?


\vspace{8cm}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

Example.  How many integer solutions are there to

$\ds x_1 + x_2 \le 7$ with $x_1\ge 0$ and $x_2 \ge 0$?

\vspace*{2cm}

Example.  How many ways are their to distribute 5 apples,
4 oranges and 3 pears to three people?

\vspace{5cm}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

Example. \ Consider the following code segments. \\
What is the value of counter after the loops have executed ?

\bigskip
\input{counter}


\vspace{3cm}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Example.  A box contains 10 red balls, 10 green balls and 10 blue balls.
Each set of balls is numbered 1 to 10.  Suppose 7 balls are drawn at
random from the box.  In how many ways can there be 3 of one colour,
2 of a second colour and 2 of the 3rd colour. % 3 x 10C3 x 2C2 x 10C2 x 10C2


\vspace{12cm}
\end{frame}

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

Exercise. How many paths of length 2 edges are there in $K_6$?

\vspace{12cm}
\end{frame}
