
\documentclass[10pt]{article}
\usepackage{amsmath,amssymb,amsfonts,fancyhdr}
\usepackage{graphicx}
%
\setlength{\textheight}{9in}
\setlength{\topmargin}{-0.75in}
\setlength{\textwidth}{7in}
\setlength{\oddsidemargin}{-.2in}
\setlength{\parskip}{6pt}
\setlength{\parindent}{0pt}
%\usepackage{fullpage}
\renewcommand{\headrulewidth}{1pt}
\setlength{\headsep}{1cm}
% \usepackage{txfonts}
\usepackage{newcent}
\usepackage{fancyhdr}
\usepackage{multirow}   % for table formatting
\usepackage{hyperref}  % for weblinks in pdf
\usepackage{color}

\DeclareSymbolFont{extraup}{U}{zavm}{m}{n}
\DeclareMathSymbol{\varheart}{\mathalpha}{extraup}{86}
\DeclareMathSymbol{\vardiamond}{\mathalpha}{extraup}{87}
\newcommand{\red}{\color{red}}
\newcommand{\black}{\color{black}}



\newcommand{\ds}{\displaystyle} 
\newcommand{\QQ}{{\mathbb{Q}}} % blackboard Q
\newcommand{\Qbar}{{\overline{\QQ}}} % blackboard Qbar
\newcommand{\ZZ}{{\mathbb{Z}}} % blackboard Z
\newcommand{\NN}{{\mathbb{N}}} % blackboard N
\newcommand{\CC}{{\mathbb{C}}} % blackboard C
\newcommand{\Zplus}{{\mathbb{Z^+}}} % blackboard Z^+
\newcommand{\FF}{{\mathbb{F}}} % blackboard F
\newcommand{\RR}{{\mathbb R}} % blackboard R
\newcommand{\Rtwo}{{\mathbb R^2}} % blackboard R^2
\newcommand{\Rthree}{{\mathbb R^3}} % blackboard R^3
\newcommand{\RRn}{{\mathbb R^n}} % blackboard R^n
\newcommand{\D}{{\cdot}} % dot
\def\mod#1{{\ifmmode\text{\rm\ (mod~$#1$)}
\else\discretionary{}{}{\hbox{ }}\rm(mod~$#1$)\fi}}

\def\tra{70}   %text rotation angle in table header
\newcommand{\tablehead}[1]{\rotatebox{\tra}{\scriptsize{#1}}}


%----------- colours ------------------------------------------------------
\definecolor{SFUred}{rgb}{0.60547,0.140625,0.17969}
\definecolor{SFUblue}{rgb}{.1602, .2734, .51172}
\definecolor{SFUgrey}{rgb}{.28515,.28125,.25}

\definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}
\definecolor{FireBrick}{rgb}{0.5812,0.0074,0.0083}
\definecolor{RoyalBlue}{rgb}{0.0236,0.0894,0.6179}
\definecolor{RoyalGreen}{rgb}{0.0236,0.6179,0.0894}
\definecolor{RoyalRed}{rgb}{0.6179,0.0236,0.0894}
\definecolor{LightBlue}{rgb}{0.8544,0.9511,1.0000}
\definecolor{Black}{rgb}{0.0,0.0,0.0}
\definecolor{FuncColor}{rgb}{1.0,0.0,0.0}
%------------------------------------------------------------------------------
%amps stuff

\usepackage{enumitem}
\setlist[enumerate,1]{label=}
\setlist[enumerate,2]{label=\Alph*.}
\setlist[enumerate,3]{label=\arabic*.}
\setlist[enumerate,4]{label=(\alph*)}



% check boxes for after instructors questions
\newcommand{\insertcheckboxes}{
\begin{center}
\fbox{
\begin{tabular}{ccccc}
done & checked & corrected & study MT & study final \\
$\Box$ &  $\Box$ &  $\Box$ &  $\Box$ &  $\Box$
\end{tabular}
}
\end{center}
}


% standard basis vectors
\def\ihat{{\bf \hat{i}}}
\def\jhat{{\bf \hat{j}}}
\def\khat{{\bf \hat{k}}}

% vector arrow notation
\newcommand{\bvec}[1]{\vec{ \bf #1}}  % absolute value


\newcommand{\twovec}[2]{\left[\begin{array}{c}
#1\\ #2\\ \end{array}\right] }

\newcommand{\closethegap}{\vspace{-2mm} }

\newcommand{\threevec}[3]{\left[\begin{array}{c}
#1\\ #2\\ #3\\ \end{array}\right] }

\newenvironment{soln}[1]{ \textit{Solution #1:} }{\medskip}

\pagestyle{plain}

%------------------------------------------------
% different types of labels for lists
% 1) type of label
%\renewcommand{\theenumi}{\arabic{enumi}}   default
%\renewcommand{\theenumi}{\alph{enumi}}     alphabetic   (use capital A for capitals)
%\renewcommand{\theenumi}{\roman{enumi}}    roman numerals (use capital R for capitals)
%
% 2) formatting of label
%\renewcommand{\labelenumi}{(\theenumi)}   default
%\renewcommand{\labelenumi}{\theenumi.}    remove brackets
%------------------------------------------------


%------------ Course Information --------------------
\newcommand{\coursename}{Discrete Mathematics II}
\newcommand{\coursenum}{MACM 201 - D100, D200 and D300}
\newcommand{\semester}{Spring 2021}
\newcommand{\instructor}{Mahsa Faizrahnemoon, Michael Monagan and Amarpreet Rattan}

%------------ Assignment Information -------------
\newcommand{\anum}{1}
\newcommand{\duedate}{January 25th, 2021}
\newcommand{\duetime}{11:00pm}

\pagestyle{fancy}
\fancyhf{} 

\lhead{\includegraphics[height=1cm]{logo.png}}
\rhead{\large\sc \coursenum ~~~~Assignment\ \#\anum}
\lfoot{ {\color{blue} \sc Copyright \instructor}}
\rfoot{{\small \thepage}}



%--------- Now for the document ----------------------------------

\begin{document}
\hfill{{\bf Due Date}:     \duedate, \duetime}

\subsection*{Instructions}

Answer all questions on paper or on a tablet using your own handwriting.
Include a cover page with your name, student ID and a list of the questions 
you have answered.

\smallskip
If you use paper, take a photo of each page using your phone or scan each page
and upload your work to crowdmark.
If you use a tablet, export your work to a .pdf file and upload
the file(s) to crowdmark.

\smallskip
Please number each page so that if you upload your
pages in the wrong order we can find your answers.

\smallskip
You are expected to attempt all questions, including the questions
from the textbook and the instructor's questions.
We will only mark about 5 questions.
We will post solutions to all questions on Canvas by 9am the day after the assignment is due.
For this reason we cannot give extensions to assignments.

\smallskip
Don't forget to write {\bf your name} and {\bf student ID number} on the {\bf cover page}!

\begin{enumerate}
\item { \color{SFUred} \textbf{Textbook Reading} }

		\begin{itemize}	
			\item Sections: 1.1, 1.2, 1.3, 1.4
                \end{itemize}


%=====================================
% Definitions, Concepts & Keywords
%=====================================
%\item {\color{SFUred}\textbf{Definitions, Concepts \& Keywords}}
%%\textbf{Definitions, Concepts \& Keywords}:
%
%\begin{itemize}
%\item[$\bullet$] Know the difference between strings, sets, subsets and permutations.  
%\item[$\bullet$] Understand the basic terminology on graphs and trees.
%\item[$\bullet$] Know how to count permutations, combinations, and use the Binomial Theorem.
%\item[$\bullet$] Know how to count permutations and combinations with repetition.
%\end{itemize}

\item {\color{SFUred}\textbf{Exercises}}

\begin{enumerate}

   %=====================================
   % Textbook Questions
   %=====================================	
   \item  \textbf{Textbook Questions : Grimaldi, 5th edition} 

        \begin{itemize}
	\item[]  Section 1.2 Exercises 7, 10, and 15. % Fall 2020 5, 20
	\item[]  Section 1.3 Exercises 4 and 30. % Fall 2020 6, 30.  Also 7 is good.
	\item[]  Section 1.4 Exercises 2, 12, and 15. % Fall 2021 1, 10.  Also 8, 12 is good.
        \end{itemize}

   %=====================================
   % Our Questions
   %=====================================
   \item \textbf{Instructors Questions}

   \begin{enumerate}
% These are from Lecture 1: Combinatorial ojbects
   \item List all binary strings of length 5 with three 1 bits.
         You should get $5 \choose 3$ of them.
   \item There are $n$ balls labelled $1,2,3,\dots,n$ and $n$ boxes labelled $1,2,3,\dots,n$.
         \begin{enumerate}
         \item How many ways are there to put the balls into the boxes?
         \item How many ways are there if each box must have one ball?
         \end{enumerate}
   %\item DNA sequences have an alphabet $\{A,C,G,T\}$. \\
   %      How many DNA sequences of length $n$ are there?  Note that the
   %      DNA sequences $ACTG$ and $GTCA$ are considered the same.
   %      Note, this problems is more difficult than it first looks.
   \item  How many palindromes of length $n$ are there for the alphabet $\Sigma = \{A,B,C,D\}$. \\
          A palindrome is a word that reads the same forwards as backwards, e.g. $ABBA$.

   %\item Six people are sitting at a circular table. \\
   %      How many (circular) permutations of them are there? \\
   %      Note, the circular permutations $1 2 3 4 5 6$ and
   %      $2 3 4 5 6 1$ are considered the same.

   %\item Let $G$ be a graph with vertex set $V = \{1,2,3,4,5,6\}$.
   %      Suppose $G$ has no edges between odd numbered vertices and
   %      also no edges between even numbered vertices.
   %      \begin{itemize}
   %      \item[(a)] Draw such a graph with the maximum number of edges.
   %      \item[(b)] How many such graphs are there?
   %      \end{itemize}
   \item Consider the graph $G=(V,E)$ given by vertexes $V=\{1,2,3,4,5,6\}$ \\
         and edges $E=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,1\},\{2,5\},\{1,6\}\}$. \\
         Draw $G$ and draw all paths of length 5 in $G$.

   %\item Draw a graph with 6 vertices where each vertex has degree 2. \\
   %      Draw a different graph with 6 vertices where each vertex has degree 2.
   \item Draw a graph with 6 vertices where each vertex has degree 3.
         Draw a different graph with 6 vertices where each vertex has degree 3.
         Explain how they are different.

   \item Draw all unlabelled trees with 5 vertices.  You should get 3 trees.

% These are from Lecture 2:  1.2 Permutations and a bit of 1.3 Combinations
   %\item \begin{enumerate}
   %      \item How many {\it combinations} of size 3 can one produce from $a,b,c,d,e,f$? % C(6,3)
   %      \item How many {\it permutations} of size 3 can one produce from $a,b,c,d,e,f$? % 6x5x4
   %      \end{enumerate}

   %\item Let $A= \{a,b,c,d\}$ and $B = \{1,2,3,4\}$.
   %      Let $f(x)$ be a function from $A$ to $B$. \\
   %      One such function is shown in the table below.
   %      \begin{center}
   %      \begin{tabular}{ c|c|c|c|c }
   %         $x$ & $a$ & $b$ & $c$ & $d$ \\ \hline
   %      $f(x)$ &  1  &  3  &  1  &  2 \\
   %      \end{tabular}
   %      \end{center}
   %	 \begin{enumerate}
   %		\item Find the number of functions from $A$ to $B$. % 4^4
   %		\item Find the number of onto functions from $A$ to $B$. % 4!
   %	 \end{enumerate}

% These are from Lecture 3 : 1.3 The Binomial Theorem
   \item Write out the proof that ${ n \choose k } = \frac{n!}{k! (n-k)!}$
         from the class notes. % Force them to study this proof
   %\item If $\ds {30 \choose 20} = 30,045,015$ what is $\ds {30 \choose 10}$ ? 
   %\item Show that ${n \choose 2}{n-2 \choose 2} = 6 {n \choose 4}$.
   \item Show that ${n \choose 2}+{n-1 \choose 2}$ is a perfect square.
   \item % Adapted from 1.3 Exercise 8 
           A box has 10 red balls, 10 green balls, 10 blue balls
           and 10 yellow balls.  Each set of 10 balls is numbered 1 to 10.
   %       Suppose four balls are chosen from the box.
   %      \begin{enumerate}
   %      \item How many ways can there be four of the same colour?   %  4 C(10,4)
   %      \item How many ways can there be three of one colour
   %            and one of another colour?   %  4 C(10,3) x 30
   %      \item How many ways can there be two of one colour and 
   %            two of a different colour.   %  4 C(10,2) 3 C(10,2) / 2
   %      \end{enumerate}
          Suppose six balls are chosen from the box.
         \begin{enumerate}
         \item How many ways can there be six of the same colour?   %  4 C(10,6)
         \item How many ways can there be four of one colour
               and two of another colour?   %  4 C(10,4) 3 C(10,2)
         \item How many ways can there be three of one colour and 
               three of a different colour.   %  4 C(10,3) 3 C(10,3) / 2
         \item How many ways can there be two of one colour, two of a second colour,
               and two of a third colour?  % C(4,3) C(10,2)^3
         \end{enumerate}

   \item We will count the number of cycles in the complete graph $K_6$.
         \begin{enumerate}
         \item How many cycles on 6 vertices are in $K_6$?
         \item How many cycles on 5 vertices are in $K_6$?
         \item How many cycles on 4 vertices are in $K_6$?
         \item How many cycles on 3 vertices are in $K_6$?
         \end{enumerate}

   %\item Determine the coefficient of 
   %      \begin{enumerate}
   %      \item $x^2 y^3 z^2$ in $(x+y+z)^7$
   %      \item $x^2 y^3 z^2$ in $(x+2y+z)^7$
   %      \end{enumerate}
   \item Consider the expressions $f=(x+y+z)^7$ and $g=(x+y-3z)^7$.
         \begin{enumerate}
         \item Find the coefficient of $x^2 y^3 z^2$ in $f$ and $g$?
         \item What is the sum of all the coefficients in $f$ and $g$?
         \item How many terms are there in the expansion of $f$ and $g$? \\
               Note $(x+y)^3=x^3+3x^2y+3xy^2+y^3$ has 4 terms $x^3,3x^2y,3xy^2$ and $y^3$.
         \end{enumerate}

% These are from 1.4
   \item
         \begin{enumerate}
         \item How many ways can Mary distribute 12 apples and 10 oranges to her three children?
         \item How many ways can Mary distribute 12 apples and 10 oranges to her three children 
         such that each child gets at least two apples and at least one orange.
         \end{enumerate}

%\item     % A problem of interest
%          In a standard deck of 52 cards there are
%          are 13 kinds of cards labelled $A,K,Q,J,10,9,8,7,6,5,4,3,2$ in
%          each of four suits $\red \varheart$ (hearts), $\red \vardiamond$ (diamonds)
%                             $\clubsuit$ (clubs) and $\spadesuit$ (spades).
%          In the game of standard poker a player is dealt 5 cards.
%          \begin{enumerate}
%          \item How many ways are there to get three of a kind? \\
%                An example of such a poker hand is 
%                $\red 8 \varheart \, \black 8 \spadesuit \, 8 \clubsuit \, \red 5 \vardiamond \, J \varheart$
%          \item How many ways are there to get two of one kind and three of another kind? \\
%                For example $\red 8 \varheart \, \black 8 \spadesuit \, 8 \clubsuit \, \red J \vardiamond \, J \varheart$
%          \item How many ways are there to get five different kinds.
%                For example $\red 8 \varheart \, \black 9 \spadesuit \, 10 \clubsuit \, \red J \vardiamond \, Q \varheart$
%                
%          \end{enumerate}
\end{enumerate}

\vspace{0.5cm}


\end{enumerate}

% Lecture 1  0 + 5 problems
% Lecture 2  2 + 4 problems
% Lecture 3  2 + 4 problems
% Lecture 4  2 + 3 problems
% Total 5 + 6 + 6 + 5 = 22 problems

\end{enumerate}
\end{document}
