Skip to main content
Contents Embed Prev Up Next \(\newcommand{\set}[1]{\{#1\}}
\newcommand{\ints}{\mathbb{Z}}
\newcommand{\posints}{\mathbb{N}}
\newcommand{\rats}{\mathbb{Q}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\complexes}{\mathbb{C}}
\newcommand{\twospace}{\mathbb{R}^2}
\newcommand{\threepace}{\mathbb{R}^3}
\newcommand{\dspace}{\mathbb{R}^d}
\newcommand{\nni}{\mathbb{N}_0}
\newcommand{\nonnegints}{\mathbb{N}_0}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\prob}{\operatorname{prob}}
\newcommand{\Prob}{\operatorname{Prob}}
\newcommand{\height}{\operatorname{height}}
\newcommand{\width}{\operatorname{width}}
\newcommand{\length}{\operatorname{length}}
\newcommand{\crit}{\operatorname{crit}}
\newcommand{\inc}{\operatorname{inc}}
\newcommand{\HP}{\mathbf{H_P}}
\newcommand{\HCP}{\mathbf{H^c_P}}
\newcommand{\GP}{\mathbf{G_P}}
\newcommand{\GQ}{\mathbf{G_Q}}
\newcommand{\AG}{\mathbf{A_G}}
\newcommand{\GCP}{\mathbf{G^c_P}}
\newcommand{\PXP}{\mathbf{P}=(X,P)}
\newcommand{\QYQ}{\mathbf{Q}=(Y,Q)}
\newcommand{\GVE}{\mathbf{G}=(V,E)}
\newcommand{\HWF}{\mathbf{H}=(W,F)}
\newcommand{\bfC}{\mathbf{C}}
\newcommand{\bfG}{\mathbf{G}}
\newcommand{\bfH}{\mathbf{H}}
\newcommand{\bfF}{\mathbf{F}}
\newcommand{\bfI}{\mathbf{I}}
\newcommand{\bfK}{\mathbf{K}}
\newcommand{\bfP}{\mathbf{P}}
\newcommand{\bfQ}{\mathbf{Q}}
\newcommand{\bfR}{\mathbf{R}}
\newcommand{\bfS}{\mathbf{S}}
\newcommand{\bfT}{\mathbf{T}}
\newcommand{\bfNP}{\mathbf{NP}}
\newcommand{\bftwo}{\mathbf{2}}
\newcommand{\cgA}{\mathcal{A}}
\newcommand{\cgB}{\mathcal{B}}
\newcommand{\cgC}{\mathcal{C}}
\newcommand{\cgD}{\mathcal{D}}
\newcommand{\cgE}{\mathcal{E}}
\newcommand{\cgF}{\mathcal{F}}
\newcommand{\cgG}{\mathcal{G}}
\newcommand{\cgM}{\mathcal{M}}
\newcommand{\cgN}{\mathcal{N}}
\newcommand{\cgP}{\mathcal{P}}
\newcommand{\cgR}{\mathcal{R}}
\newcommand{\cgS}{\mathcal{S}}
\newcommand{\bfn}{\mathbf{n}}
\newcommand{\bfm}{\mathbf{m}}
\newcommand{\bfk}{\mathbf{k}}
\newcommand{\bfs}{\mathbf{s}}
\newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}}
\newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}}
\newcommand{\surjection}{\xrightarrow[\text{onto}]{}}
\newcommand{\nin}{\not\in}
\newcommand{\prufer}{\text{prüfer}}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\stab}{stab}
\DeclareMathOperator{\var}{var}
\newcommand{\inv}{^{-1}}
\newcommand{\ds}{\displaystyle}
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Handout 2.1 Combinatorial Proofs
Problem 2.1 .
Let’s go back to license plates allowing any three uppercase letters followed by any three numbers.
(a) How many license plates start with a vowel followed by a consonant?
(b) How many license plates end with a
\(3\) -digit number divisible by
\(5\text{?}\) (Here we allow leading zeros in
\(3\) -digit numbers, unlike in the previous three questions.)
(c) How many license plates start with a vowel followed by a consonant
and end with a
\(3\) -digit number divisible by
\(5\text{?}\)
(d) How many license plates start with a vowel followed by a consonant
or end with a
\(3\) -digit number divisible by
\(5\text{?}\)
Activity 2.1.1 .
(a) How many ways are there to form a string of length 10 using symbols from the 26-letter uppercase English alphabet if exactly three characters in the string are to elements of the set
\(\set{A,B,C,D}\text{?}\) Write a sentence or two to explain your reasoning.
(b) How does your answer change if the characters from the set
\(\set{A,B,C,D}\) must be distinct?
Peer instruction question 1
We saw this sum on the handout during our last class:
\begin{equation*}
\binom{n}{0}+ \binom{n}{1}+ \binom{n}{2}+ \cdots + \binom{n}{n-1}+ \binom{n}{n}
\end{equation*}
A square grid of dots. There are 7 rows, each containing 7 dots. There is a box surrounding the dots lying on the diagonal that runs from the upper-left corner of the grid to the lower-right corner of the grid.
How do the answers to the five bullets above change when the grid is
\((n+1)\times (n+1)\text{?}\)
Activity 2.1.2 .
We just saw that
\begin{equation*}
1 + 2 + \cdots + n = \binom{n+1}{2}\text{.}
\end{equation*}
Can we find a proof that counts \(2\) -element subsets?
Discuss with your group: How many \(2\) -element subsets \(S\) of \([n+1] = \set{1,2,\dots,n+1}\) have each number below as the smallest element of \(S\text{?}\)
\(i\) for
\(1\leq i\leq n+1\)
How can you use this to explain the identity?
Peer instruction question 2
Peer instruction question 3
Peer instruction question 4
