\documentclass[10pt]{article}
\usepackage{fullpage}
\usepackage{setspace}
\usepackage{parskip}
\usepackage{titlesec}
\usepackage[section]{placeins}
\usepackage{xcolor}
\usepackage{breakcites}
\usepackage{lineno}
\usepackage{hyphenat}
\PassOptionsToPackage{hyphens}{url}
\usepackage[colorlinks = true,
linkcolor = blue,
urlcolor = blue,
citecolor = blue,
anchorcolor = blue]{hyperref}
\usepackage{etoolbox}
\makeatletter
\patchcmd\@combinedblfloats{\box\@outputbox}{\unvbox\@outputbox}{}{%
\errmessage{\noexpand\@combinedblfloats could not be patched}%
}%
\makeatother
\usepackage[round]{natbib}
\let\cite\citep
\renewenvironment{abstract}
{{\bfseries\noindent{\abstractname}\par\nobreak}\footnotesize}
{\bigskip}
\titlespacing{\section}{0pt}{*3}{*1}
\titlespacing{\subsection}{0pt}{*2}{*0.5}
\titlespacing{\subsubsection}{0pt}{*1.5}{0pt}
\usepackage{authblk}
\usepackage{graphicx}
\usepackage[space]{grffile}
\usepackage{latexsym}
\usepackage{textcomp}
\usepackage{longtable}
\usepackage{tabulary}
\usepackage{booktabs,array,multirow}
\usepackage{amsfonts,amsmath,amssymb}
\providecommand\citet{\cite}
\providecommand\citep{\cite}
\providecommand\citealt{\cite}
% You can conditionalize code for latexml or normal latex using this.
\newif\iflatexml\latexmlfalse
\providecommand{\tightlist}{\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}%
\AtBeginDocument{\DeclareGraphicsExtensions{.pdf,.PDF,.eps,.EPS,.png,.PNG,.tif,.TIF,.jpg,.JPG,.jpeg,.JPEG}}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\begin{document}
\title{Weekly Blog \#4 - Who's Ready for some PIE?}
\author[1]{TJ}%
\affil[1]{Affiliation not available}%
\vspace{-1em}
\date{\today}
\begingroup
\let\center\flushleft
\let\endcenter\endflushleft
\maketitle
\endgroup
\sloppy
\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.28\columnwidth]{figures/pie/pie}
\end{center}
\end{figure}
\section*{Introduction}
{\label{140539}}\par\null
In combinatorics, counting techniques are utilized to solve problems in
a variety of combinations. The rule of sum states that if A and B are
sets with no elements in common, then we just combine the sets. What
happens if set A and B do have elements in common? Those elements will
have been double counted in the original combination. The Principle of
Inclusion and Exclusion (PIE) is a counting technique that ensures that
an element does not get counted twice.
Here is an example:
\begin{itemize}
\tightlist
\item
Set A represents people that prefer Blueberry pie, Set B represents
people that prefer Cherry pie. If there are no common elements in the
sets, then the rule of sum states
\end{itemize}
if $A \cap B = \varnothing $, then $|A \cup B| = |A| + |B|$.\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.28\columnwidth]{figures/venn/A-and-B}
\end{center}
\end{figure}
\begin{itemize}
\tightlist
\item
A venn diagram will illustrate what happens when elements in set A
also appear in set B. There could be people that cannot decide and
like both Blueberry and Cherry pie, and those appear in the purple
set. So the rule can be extended to say for any sets A and B
\end{itemize}
$A$ and $B$, $|A \cup B| = |A| + |B| - |A \cap B|$.\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.28\columnwidth]{figures/venn1/venn1}
\end{center}
\end{figure}
The Principle of Inclusion and Exclusion can then be applied to any
number of sets with common elements that we are trying to combine
ensuring that everything gets counted exactly once. We would just add a
step of including or excluding for each additional set we are dealing
with.~
\par\null\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.28\columnwidth]{figures/3venn/3venn}
\end{center}
\end{figure}
\section*{Let's Put it to Use}
{\label{262716}}\par\null
\begin{itemize}
\tightlist
\item
The annual Pie Eating Contest has just ended. There are several pies
left over and the judges get to take them home. How many ways are
there to give the 10 different types of pies to the 4 judges so that
each judge gets to take home at least one pie?
\end{itemize}
\par\null
There are $4^{10}$ ways to distribute the pies, but that includes the option of a judge not taking any pie home. Because of the restriction of each judge getting at least one pie, we would need to subtract the ways that judge 1, 2, 3, or 4 would not get any pie. So that would be ${4 \choose 1} \cdot 3^{10}$. By subtracting those options, we have also included the option that 2 of the judges would not get pie, so we need to add those back in with ${4 \choose 2} \cdot 2^{10}$. Finally we need to subtract the scenario of 3 of the judges not getting pie and that would be $4 \choose 3$. Altogether, the number of ways to distribute the pies is
\begin{center}
$4^{10} - {4 \choose 1} \cdot 3^{10} + {4 \choose 2} \cdot 2^{10} - {4 \choose 3}$.
\end{center}
\par\null
\section*{Ready for PIE?}
{\label{470612}}\par\null
The ability to apply the principle of inclusion and exclusion allows us
to solve more difficult ~problems in combinatorics. By finding the value
to each part of the elements that have been double counted at each step,
we can add or subtract down the line to ensure that each element in
question has only been counted once.~
\par\null
Here are some ways to use PIE, give it a try!
\par\null
\begin{itemize}
\tightlist
\item
How many ways are there to arrange the letters of MASTERPIECE that
avoid the word PIE?
\end{itemize}
\par\null
\begin{itemize}
\tightlist
\item
How many numbers between 1 and 1000 are not divisible by 2, 3, or 5?
\end{itemize}
\par\null\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.28\columnwidth]{figures/cherry/cherry}
\end{center}
\end{figure}
References
Benjamin, A.T. (2009). Discrete Mathematics. Chantilly, VA: The Teaching
Company.
\selectlanguage{english}
\FloatBarrier
\end{document}