Other Basic Counting Techniques

Processing math: 100%

$\def\xautoref#1{\ref{#1}} \renewcommand{\thepage}{\roman{page}} \renewcommand{\thepage}{\arabic{page}} \def\radius{3} \def\steps{18} \renewcommand{\arraystretch}{2.2} \def\openbox{\undefined} \def\ellipsea{[rotate=30](0,0) ellipse (3cm and 2cm)} \def\thm{\undefined} \def\ellipseb{[rotate=150](3,1.72) ellipse (3cm and 2cm)} \def\cor{\undefined} \def\ellipsec{[rotate=270](3,-1.7) ellipse (3cm and 2cm)} \def\prop{\undefined} \def\lem{\undefined} \def\defn{\undefined} \def\rem{\undefined} \renewcommand{\indexname}{Index} \newcommand{\noneed}{(\!\emph{You do not need to show your work.})} \renewcommand{\indexname}{List of Notation} \newcommand{\multiset}[2]{\left(\!\binom{#1}{#2}\!\right)} \newcommand{\tmultiset}[2]{\big(\!\binom{#1}{#2}\!\big)} \newcommand{\twoonone}{\twocolumn \setlength{\textwidth}{9.5 in} \setlength{\textheight}{7.25 in} \setlength{\columnsep}{0.5in} \hoffset=-1in \voffset=-1in } \newcommand{\theProbPart}{\Alph{ProbPart}} \newcommand{\practiceproblems}{ \section*{Practice Exercises} \addcontentsline{toc}{section}{Practice Exercises} } \newcommand{\problempart}{ \textbf{Part \Alph{ProbPart}}\ } \newcommand{\solutions}{$\star$} \newcommand{\leftsolutions}{\hspace{-2.2em}\makebox[2em][l]{\solutions}} \newcommand{\solutionsection}[2]{ \section*{Chapter {\ref{#1}} Exercise {\ref{#2}}} } \newcommand{\nextSeq}{\stepcounter{countSeq}\arabic{countSeq}, } \newcommand{\noSeq}{\stepcounter{countSeq}} \newcommand{\lastSeq}{and \stepcounter{countSeq}\arabic{countSeq} } \renewcommand{\thechapter}{\arabic{chapter}} \def\chapterrunhead{\partrunhead} \def\sectionrunhead{\partrunhead} \newcommand{\TTbf}[1]{\textbf{\large #1}} \newcommand{\whline}{\noalign{\global\savedwidth\arrayrulewidth \global\arrayrulewidth 2pt}\hline \noalign{\global\arrayrulewidth\savedwidth}} \newcommand{\leftnone}[1]{\hbox to 0pt{#1\hss}} \newcommand{\hypend}{\whline} \newcommand{\nohypotheses}{ \\} \newcommand{\AndIntro}[2]{$\eand$-intro (lines ${#1}$ and ${#2}$)} \newcommand{\AndIntroB}[2]{$\eand$-intro \\ (lines ${#1}$ and ${#2}$)} \newcommand{\AndElim}[1]{$\eand$-elim (line ${#1}$)} \newcommand{\OrIntro}[1]{$\eor$-intro (line ${#1}$)} \newcommand{\OrElim}[2]{$\eor$-elim (lines ${#1}$ and ${#2}$)} \newcommand{\IfIntro}[2]{$\eif$-intro (lines ${#1}$--${#2}$)} \newcommand{\IfElim}[2]{$\eif$-elim (lines ${#1}$ and ${#2}$)} \newcommand{\IffIntro}[2]{$\eiff$-intro (lines ${#1}$ and ${#2}$)} \newcommand{\IffElim}[1]{$\eiff$-elim (line ${#1}$)} \newcommand{\IffElimB}[2]{$\eiff$-elim \\ (lines ${#1}$ and ${#2}$)} \newcommand{\NotIntro}[2]{Proof by Contradiction (lines ${#1}$--${#2}$)} \newcommand{\NotElim}[1]{$\enot$-elim (line ${#1}$)} \newcommand{\Repeat}[1]{repeat~(line ${#1}$)} \newcommand{\AllElim}[1]{$\forall$-elim (line ${#1}$)} \newcommand{\AllElimSet}[2]{$\forall$-elim (lines ${#1}$ and~${#2}$)} \newcommand{\AllIntro}[1]{$\forall$-intro (line ${#1}$)} \newcommand{\AllIntroSet}[2]{$\forall$-intro (lines ${#1}$--${#2}$)} \newcommand{\ExistElim}[3]{$\exists$-elim (lines ${#1}$ and ${#2}$--${#3}$)} \newcommand{\ExistElimSet}[3]{$\exists$-elim (lines ${#1}$ and ${#2}$--${#3}$)} \newcommand{\ExistIntro}[1]{$\exists$-intro (line ${#1}$)} \newcommand{\ExistIntroSet}[2]{$\exists$-intro (lines ${#1}$ and~${#2}$)} \newcommand{\EqualIntro}{$=$-intro} \newcommand{\EqualElim}[2]{$=$-elim (lines ${#1}$ and~${#2}$)} \newcommand{\NotSimplify}[1]{$\enot$-simplify (line $#1$)} \newcommand{\Cases}[3]{Proof by cases (lines $#1$, $#2$, and $#3$)} \newcommand{\by}[2]{#1 (#2)} \newcommand{\var}[1]{\text{#1}} \newcommand{\bigset}[2]{\left\{\, #1 \mathrel{\left| \right.} #2 \,\right\} } \renewcommand{\see}[1]{{(}see~\ref{#1}{)}} \newcommand{\seeex}[1]{{(}see Exer.~\ref{#1}{)}} \newcommand{\fullseeex}[2]{{(}see Exer.~\ref{#1}\pref{#1-#2}{)}} \newcommand{\fullcsee}[2]{(see~\fullcref{#1}{#2})} \newcommand{\fullsee}[2]{(see~\fullref{#1}{#2})} \newcommand{\fullcref}[2]{\xautoref{#1}\pref{#1-#2}} \newcommand{\fullCref}[2]{\xautoref{#1}\pref{#1-#2}} \newcommand{\fullcf}[2]{(cf.~\ref{#1}\pref{#1-#2})} \newcommand{\cfSect}[1]{(cf.~\S\ref{#1})} \newcommand{\power}{\mathcal{P}} \newcommand{\compose}{\mathbin{\circ}} \newcommand{\Id}{I} \newcommand{\sm}{\smallsetminus} \newcommand{\comp}[1]{\overline{#1}} \newcommand{\rel}{\mathrel{R}} \newcommand{\divides}{\mathrel{|}} \newcommand{\nmids}{\nmid} \newcommand{\class}[1]{ \overline{#1}} \newcommand{\edgeG}{\mathrel{\displaystyle\mathop{\edge}\limits^G}} \newcommand{\edgeH}{\mathrel{\displaystyle\mathop{\edge}\limits^H}} \newcommand{\edgeK}{\mathrel{\displaystyle\mathop{\edge}\limits^K}} \newcommand{\edgeGone}{\mathrel{\displaystyle\mathop{\edge}\limits^{G_1}}} \newcommand{\edgeGtwo}{\mathrel{\displaystyle\mathop{\edge}\limits^{G_2}}} \newcommand{\edgeGthree}{\mathrel{\displaystyle\mathop{\edge}\limits^{G_3}}} \newcommand{\arc}{\mathrel{\lower3pt\hbox{\LARGE$\rightarrow$}}} \newcommand{\arcG}{\mathrel{\displaystyle\mathop{\arc}\limits^G}} \newcommand{\arcH}{\mathrel{\displaystyle\mathop{\arc}\limits^H}} \renewcommand{\vec}[1]{\overrightarrow{#1}} \newcommand{\boxprod}{\mathbin{\square}} \newcommand{\headrulewidth}{0pt} \renewcommand{\sectionmark}[1]{} \newcommand{\optional}{{\upshape(optional)}} \newcommand{\blue}[1]{{\color{blue}#1}} \newcommand{\faint}[1]{{\scriptsize\color{blue}#1}} \newcommand{\SL}{Propositional Logic} \newcommand{\QL}{First-Order Logic} \newcommand{\univ}{\script{U}} \renewcommand{\implies}{\eif} \newcommand{\?}{\mathrel{\displaystyle\mathop{=}\limits^?}} \newcommand{\pref}[1]{\eqref{#1}} \newcommand{\fullref}[2]{\ref{#1}\pref{#1-#2}} \newcommand{\hint}[1]{{\small{[}\textit{Hint:} #1{]}}} \renewcommand{\natural}{\mathbb{N}} \newcommand{\rational}{\mathbb{Q}} \newcommand{\real}{\mathbb{R}} \newcommand{\integer}{\mathbb{Z}} \newcommand{\iso}{\cong} \newcommand{\bibd}{\mathcal{B}} \newcommand{\code}{\mathcal{C}} \newcommand{\ul}{\underline} \newcommand{\mytheoremheaderfont}[1]{{\bfseries\sffamily\MakeUppercase{#1}}} \newcommand{\optargfont}[1]{{\bfseries\sffamily #1}} \newcommand{\theexerthm}{\arabic{exerthm}} \newcommand{\proofnamestyle}{\bfseries\sffamily} \renewcommand{\thepart}{\Roman{part}} \renewcommand{\contentsname}{\Huge\bfseries\sffamily Contents} \newcommand{\tocsectionlabelwidth}{0.9cm} \newcommand{\tocsummary}[3]{ \indentlabel{\hbox to \tocsectionlabelwidth{\hss}}\enspace#3} \renewcommand{\solutions}{} \newcommand{\notationentry}[2]{\item #1, #2 } \newcommand{\notationindexname}{List of Notation} \newcommand{\notationchapter}[2]{ \item \hbox{\hskip-\itemindent \chaptername\ #2. #1} } \renewcommand{\includeonly}[1]{} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&}$

🔗

Chapter 10
Other Basic Counting Techniques

🔗

There are two other elementary techniques that are surprisingly useful even in quite difficult counting problems. We will wrap up our exploration of enumeration by discussing these techniques.

🔗

Summary.

Pigeonhole Principle
Generalised Pigeonhole Principle
Even more generalised pigeonhole principle
Inclusion-Exclusion

Chapter 10 Other Basic Counting Techniques

Summary.

Chapter 10
Other Basic Counting Techniques