Hints to selected activities and exercises
Skip to main content \( \def\negchoose#1#2{\genfrac{[}{]}{0pt}{}{#1}{#2}_{-1}}
\newcommand{\mchoose}[2]{\left(\!\binom{#1}{#2}\!\right)}
\newcommand{\cycle}[1]{\arraycolsep 5 pt
\left(\begin{array}#1\end{array}\right)}
\newcommand{\importantarrow}{\Rightarrow}
\newcommand{\qchoose}[2]{\left[{#1\atop#2}\right]_q}
\newcommand{\bp}{
\begin{enumerate}{\setcounter{enumi}{\value{problemnumber}}}}
\newcommand{\ep}{\setcounter{problemnumber}{\value{enumi}}
\end{enumerate}}
\newcommand{\ignore}[1]{}
\renewcommand{\bottomfraction}{.8}
\renewcommand{\topfraction}{.8}
\newcommand{\apple}{\text{🍎}}
\newcommand{\ap}{\apple}
\newcommand{\banana}{\text{🍌}}
\newcommand{\ba}{\banana}
\newcommand{\pear}{\text{🍐}}
\newcommand{\pe}{\pear}
\DeclareMathOperator{\Fix}{Fix}
\DeclareMathOperator{\Orb}{Orb}
\newcommand{\F}{\mathcal{F}}
\newcommand{\alert}{\fbox}
\def\d{\displaystyle}
\def\course{Math 228}
\newcommand{\f}[1]{\mathfrak #1}
\newcommand{\s}[1]{\mathscr #1}
\def\N{\mathbb N}
\def\B{\mathbf{B}}
\def\circleA{(-.5,0) circle (1)}
\def\Z{\mathbb Z}
\def\circleAlabel{(-1.5,.6) node[above]{$A$}}
\def\Q{\mathbb Q}
\def\circleB{(.5,0) circle (1)}
\def\R{\mathbb R}
\def\circleBlabel{(1.5,.6) node[above]{$B$}}
\def\C{\mathbb C}
\def\circleC{(0,-1) circle (1)}
\def\F{\mathbb F}
\def\circleClabel{(.5,-2) node[right]{$C$}}
\def\A{\mathbb A}
\def\twosetbox{(-2,-1.5) rectangle (2,1.5)}
\def\X{\mathbb X}
\def\threesetbox{(-2,-2.5) rectangle (2,1.5)}
\def\E{\mathbb E}
\def\O{\mathbb O}
\def\U{\mathcal U}
\def\pow{\mathcal P}
\def\inv{^{-1}}
\def\nrml{\triangleleft}
\def\st{:}
\def\~{\widetilde}
\def\rem{\mathcal R}
\def\sigalg{$\sigma$-algebra }
\def\Gal{\mbox{Gal}}
\def\iff{\leftrightarrow}
\def\Iff{\Leftrightarrow}
\def\land{\wedge}
\def\And{\bigwedge}
\def\entry{\entry}
\def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}
\def\Vee{\bigvee}
\def\VVee{\d\Vee\mkern-18mu\Vee}
\def\imp{\rightarrow}
\def\Imp{\Rightarrow}
\def\Fi{\Leftarrow}
\def\var{\mbox{var}}
\def\Th{\mbox{Th}}
\def\entry{\entry}
\def\sat{\mbox{Sat}}
\def\con{\mbox{Con}}
\def\iffmodels{\bmodels\models}
\def\dbland{\bigwedge \!\!\bigwedge}
\def\dom{\mbox{dom}}
\def\rng{\mbox{range}}
\def\isom{\cong}
\DeclareMathOperator{\wgt}{wgt}
\newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}}
\newcommand{\va}[1]{\vtx{above}{#1}}
\newcommand{\vb}[1]{\vtx{below}{#1}}
\newcommand{\vr}[1]{\vtx{right}{#1}}
\newcommand{\vl}[1]{\vtx{left}{#1}}
\renewcommand{\v}{\vtx{above}{}}
\def\circleA{(-.5,0) circle (1)}
\def\circleAlabel{(-1.5,.6) node[above]{$A$}}
\def\circleB{(.5,0) circle (1)}
\def\circleBlabel{(1.5,.6) node[above]{$B$}}
\def\circleC{(0,-1) circle (1)}
\def\circleClabel{(.5,-2) node[right]{$C$}}
\def\twosetbox{(-2,-1.4) rectangle (2,1.4)}
\def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}
\def\ansfilename{practice-answers}
\def\shadowprops{{fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}}}
\newcommand{\hexbox}[3]{
\def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2}
\def\y{-\r*#1-sin{30}*\r*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}
\newcommand{\card}[1]{\left| #1 \right|}
\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\)
Solutions C Hints to selected activities and exercises
Please resist the urge to look at a hint right away. Try to complete the activity or exercise and only look at the hint for verification or if you are really stuck.
A technical note: if you are using the pdf version, you can click on the title of the hint to link back to the original activity/exercise. Those activities/exercises that have hints will display a link [hint] that will take you to the hint.
Chapter 1 Basic Combinatorics
¶
Section 1.1 Pascal's Triangle and Binomial Coefficients
¶
Activity 6 .
(c)
Exercise 9 .
Section 1.2 Proofs in Combinatorics
¶
Subsection 1.2.1 Two Motivating Examples
¶
Activity 11 .
Activity 12 .
(a) (b)
Activity 13 .
(d)
Activity 14 .
Activity 15 .
Activity 16 .
(a) (b)
Activity 17 .
Subsection 1.2.2 Interlude: The Sum and Product Principles
¶
Exercise 23 .
(a) (b) (d)
Exercise 24 .
Exercise 25 .
(a)
Exercise 26 .
Activity 27 .
(a) (c)
Activity 28 .
(c)
Subsection 1.2.3 More Proofs
¶
Exercise 31 .
Exercise 32 .
Exercise 33 .
Exercise 34 .
Exercise 35 .
Exercise 36 .
Exercise 37 .
Exercise 38 .
Exercise 39 .
Subsection 1.2.4 Non-combinatorial Proofs in Combinatorics
¶
Exercise 41 .
Section 1.3 Counting with Equivalence
¶
Subsection 1.3.1 The Quotient Principle
¶
Activity 43 .
(a) (c)
Exercise 44 .
Exercise 45 .
Exercise 46 .
(a) (b)
Exercise 47 .
Exercise 48 .
Subsection 1.3.2 When does Order Matter?
¶
Activity 49 .
(a) (b) (c)
Exercise 50 .
Exercise 51 .
Activity 52 .
(a) (b)
Activity 57 .
(c) (e)
Activity 58 .
(b) (c)
Activity 59 .
(a)
Subsection 1.3.3 More Distribution Problems
¶
Activity 62 .
Exercise 63 .
Exercise 66 .
Section 1.4 Counting with Recursion
¶
Subsection 1.4.1 Finding Recurrence Relations
¶
Exercise 69 .
Exercise 70 .
Exercise 71 .
Exercise 72 .
Exercise 73 .
(a)
Exercise 74 .
Exercise 75 .
Subsection 1.4.2 Using Recurrence Relations
¶
Activity 76 .
Activity 77 .
Activity 79 .
(a)
Exercise 82 .
Exercise 84 .
(a)
Activity 85 .
(a) (c)
Exercise 87 .
Subsection 1.4.3 Exploring the Fibonacci Sequence
¶
Exercise 95 .
Exercise 99 .
Exercise 102 .
Exercise 106 .
Section 1.5 The Catalan Numbers
¶
Subsection 1.5.1 A Few Counting Problems
¶
Activity 110 .
Activity 112 .
Activity 113 .
Activity 114 .
Subsection 1.5.2 The Catalan Numbers
¶
Activity 115 .
(a) (b)
Exercise 116 .
Activity 117 .
(b) (c)
Activity 118 .
(b) (c)
Exercise 119 .
(a)
Chapter 2 Advanced Combinatorics
¶
Section 2.1 The Principle of Inclusion and Exclusion: the Size of a Union
¶
Subsection 2.1.1 Unions of two or three sets
Activity 133 .
Subsection 2.1.2 Unions of an arbitrary number of sets
Exercise 138 .
(b)
Subsection 2.1.3 The Principle of Inclusion and Exclusion
Exercise 139 .
Subsection 2.1.4 Application of Inclusion and Exclusion
¶
Section 2.2 Generating Functions
¶
Subsection 2.2.3 Generating functions
Exercise 159 .
Exercise 161 .
Subsection 2.2.4 Power series
Activity 163 .
Activity 164 .
Activity 165 .
Subsection 2.2.5 The extended binomial theorem and multisets
Activity 166 .
(b)
Activity 169 .
Activity 170 .
(a)
Exercise 171 .
Exercise 172 .
Exercise 173 .
Subsection 2.2.6 Generating Functions and Recurrence Relations
Exercise 176 .
Exercise 179 .
Subsection 2.2.7 Partial fractions
Activity 182 .
Activity 183 .
Exercise 185 .
Exercise 187 .
Exercise 188 .
(a) (d)
Section 2.3 Partitions of Sets
¶
Subsection 2.3.1 Stirling Numbers of the Second Kind
Activity 193 .
(d)
Activity 195 .
Exercise 196 .
Exercise 198 .
Exercise 199 .
Activity 201 .
(a) (b)
Subsection 2.3.2 Formulas for Stirling Numbers (of the second kind)
¶
Exercise 203 .
Activity 204 .
(b) (e)
Activity 205 .
(b)
Activity 206 .
Subsection 2.3.3 Identities with Stirling Numbers
¶
Activity 215 .
(a)
Exercise 217 .
Section 2.4 Partitions of Integers
¶
Subsection 2.4.1 Partition numbers
¶
Exercise 237 .
Exercise 239 .
Subsection 2.4.2 Using Geometry
¶
Activity 242 .
(a)
Exercise 244 .
Subsection 2.4.3 Partitions into distinct parts
Exercise 255 .
Activity 256 .
Exercise 257 .
Exercise 258 .
Exercise 259 .
Subsection 2.4.4 Using Generating Functions
¶
Activity 260 .
Activity 261 .
(a) (b)
Activity 262 .
Exercise 263 .
Exercise 266 .
Exercise 267 .
Exercise 269 .
Section 3.2 Walking Around Graphs
¶
Subsection 3.2.2 Proofs for Euler Paths and Circuits
Activity 283 .
(a) (b)
Section 3.3 Planar Graphs and Euler's Formula
¶
Subsection 3.3.1 Interlude: Mathematical Induction
Activity 291 .
(a) (b) (c)
Subsection 3.3.2 Proof of Euler's formula for planar graphs.
Activity 293 .
Section 3.4 Applications of Euler's Formula
¶
Subsection 3.4.1 Non-planar Graphs
Activity 296 .
(a)
Activity 298 .
Activity 299 .
Subsection 3.5.1 Coloring in General
Activity 310 .
(a)
Activity 311 .
(b) (c)
Activity 312 .
Activity 313 .
Subsection 3.5.3 Ramsey Theory
¶
Activity 318 .
Activity 319 .
Activity 320 .
Activity 321 .
(b)
Section 3.6 Matching in Bipartite Graphs
¶
Activity 328 .
(c)
Activity 329 .
login
