\part{Fundamentals} \chapter{Combinatorial principles} Naive set theory is the foundation for combinatorics. Enumerative combinatorics essentially deals with determining the cardinality of finite sets defined by predicates. Enumerative combinatoric Therefore we develop our fundamental counting techniques by going deeper into naive set theory. This part attempts to introduce combinatorics from an intuitive perspective as well as a rigiorous perspective from naive set theory. A strong background in set theory is highly reccomended. \section{Addition principle} "To count the total amount of elements among various groups, add the groups together" \begin{example} If one can only wear a necklace or a ring, and there are 7 necklaces and 5 rings, how many possible outfits are there? $7+5$ or $12$ different fits. \end{example} \section{multiplication principle} \begin{theorem}[Addition principle] Let $(X_k)^{n}_{k=1}$ be a sequence of disjoint sets, then the following holds. \[ |\bigcup^{n}_{k=1} X_k| = \sum^{n}_{k=1} |X_k|\] \end{theorem} \begin{example} A pizzeria makes pizzas with a 'protein' (cut of meat), a sauce, and a choice of condiments. If there are 5 protien choices, 3 sauces, and 10 condiment choices, how many pizza combinations are there? $5\cdot 3 \cdot 10$ or $150$ \end{example} \begin{theorem}[Multiplication principle] Let $(X_k)^{n}_{k=1}$ be a sequence of sets, then the following holds. \[ |\prod^{n}_{k=1} X_k| = \prod^{n}_{k=1} |X_k|\] \end{theorem} \section{Division principle} \begin{example} 2 red, 1 green, and a 1 blue marble are placed in a line on a desk. How many ways can the marbles be ordered if they are all used in the process and the red marbles are indistinguishable? $\frac{4\cdot 3 \cdot 2 \cdot 1}{2}$ or $12$ \end{example} \begin{theorem}[Division principle] Let there be a partition on $X$ where each partition set has $d$ elements, then the amount of partition sets is $\frac{|X|}{d}$. \end{theorem} \section{Pidgeon hole principle} \begin{lemma} Let $X$ be a finite set and $f : X \to Y$ a function, then the following holds. \[|X| = \sum_{y \in Y} |f^{-1}( \{y\} )| \] \end{lemma} \begin{theorem}[Pidgeon hole principle] Let $X,Y$ be finite sets such that $|X| > |Y|$ and let $f: X \to Y$ be a function, then there exists $2$ distinct elements $x_1,x_2 \in X$ such that $f(x_1)=f(x_2)$ (i.e $f$ is not injective). \end{theorem} One can furthermore guarantee the following. \begin{theorem}[Extended pidgeon hole principle] Let $X,Y$ be finite sets such that $|X| > n|Y|$ and let $f: X \to Y$ be a function, then there exists a set of $n+1$ distinct elements $E=\{x_1,x_2,...x_{n+1} \} \subseteq X$ such that $f(x_i)=f(x_j)$ for any $x_i,x_j \in E$. \end{theorem} Here is a really cool example problem. \begin{example} A university is conducting 2006 seminars, each with 40 attendees. For each pair of seminars, there is exactly one person attending both. Is it true that there must be someone attending all 2006 seminars? \end{example} By the extended pidgeon hole principle we can see that there exist some person attending $\lceil \frac{2005}{40}\rceil+1 =52$ eminars, however one can prove that someone attending strictly more than 40 seminars must attend them all. Let $p$ attend $t > 40$ seminars $S_1,S_2,...,S_t$, and assume by hypothesis that $p$ doesn't attend $U$. Futhermore assume we have $U \cap S_i = U \cap S_j =\{x_i\}$, then $|S_i \cap S_j| =2$ since they contain both $p$ and $x_i$, creating a contradiction, implying that $U \cap S_i$ is disjoint to any $U \cap S_j$. The inequality $|U| \geq |\bigcup^{t}_{i=1}U \cap S_i|$ should hold, but this yields $40 \geq t$, which is a contradiction that disproves our hypothesis. \section{Inclusion-exclusion principle} We understand through the addition principle that the cardinality of a finite union of finite disjoint sets is merely the sum of said set's cardinalities (i.e to find the total among of options between 2 groups of distinct options, simply sum the groups). If we are forced to deal with non-disjoint sets (i.e groups that contain overlap), we must consider a more general principle that tells how to calculate the finite union of arbitrary finite sets. Indeed we hope that the addition principle would be a corollary of this result. We will consider the case of 2 sets. \begin{proposition}[Inclusion-exclusion principle (2 sets)] \[ |X\cup Y| = |X|+|Y|- |X \cap Y|\] \end{proposition} \begin{proposition}[Inclusion-exclusion principle (3 sets)] \[ |X\cup Y \cup Z| = |X|+|Y|+|Z| - |X \cap Y|- |X \cap Z| - |Y \cap Z| +|X \cap Y \cap Z|\] \end{proposition} \begin{theorem}[Inclusion-exclusion principle] \[|\bigcup_{k=1}^{n} X_k| = \sum_{i=1}^{n} (-1)^{i-1} \sum_{J \subseteq \mathbb{N}\cap [1,n], |J|=i} |\bigcup_{j \in J} X_j|\] \end{theorem} \section{Bijection principle} If can find a bijection between twk sets, then they have the same amount of elements (cardinality). Maybe this seems slighly obvious, but the real power behind this techniquw is if we find a bijection from an open problem to a problem we have already solved, we can use the same technique as the old problem to solve the new problem (we'll see this with the 'stars and bars' method). \begin{theorem} Let $f: X \to Y$ be bijective, then $|X|=|Y|$. \end{theorem} Generating functions and recurrecne relations are more advanced combinatorial principles; these will be deferred. \chapter{Permutations and combinations} \section{Permutations} Consider a multiset (a set that allows for multiple instances of elements); how many k-tuples (ordered sequences of k instances) can be made from the multiset? These are called permutations; . However there are 2 different 'rules' we can place on ourselves when counting permutations or doing any other activity based on drawing instances from multisets. Now that the basic techniques of combinatorics are understood, we'll use them to solve more complex problems. The first of which is the problem of \emph{permutations}; consider a set of $n$ elements; how many $k$-tuples (ordered sequence with $k$ terms) can be formed by elements of this set? Here's another perspective; given a set of $n$ symbols $\Sigma$, how many strings of length $k$ can be formed? One may note there are 2 different 'rules' we can place on ourselves when counting permutations. \section{Repetition} We can either count permutations 'with' or 'without' repetition. Repetition means that when we draw an element from the set,the set 'replenishes' that element back into the set so that it may be drawn again later. Without repetition, the element is 'deleted' from the set and cannot be chosen again. \begin{example} Given the set $\Sigma=\{ \mathrm{A,B,C},\hdots,\mathrm{Z} \}$, we want to find how many possible strings of length 3 exists, given that the set has replacement. There are 26 possibilities for the first letter, and since we have replacement, ther are 26 possibilities for the second letter since the previously chosen letter 'regenerated' back into $\Sigma$. Similarly, there are 26 possibilities for that third letter. So there are $26^3$ or $17576$ possible strings. \end{example} \begin{example} Given the set $\Sigma=\{ \mathrm{A,B,C},\hdots,\mathrm{Z} \}$, we want to find how many possible strings of length 3 exists, given that the set doesn't have replacement. There are 26 possibilities for the first letter, and since we don't have replacement, ther are 25 possibilities for the second letter since the previously chosen letter was 'deleted' from $\Sigma$ when we chose it. Similarly, there are 24 possibilities for that third letter. So there are $26\cdot 25 \cdot 24$ or $15600$ possible strings. \end{example} \section{Factorial function} Recall how in our last example we took the product of $26$,$25$, and $24$; numbers adjacent to eachother. We'll introduce a powerful notation to compactly represent the product of the \begin{definition}[Factorial function] The \emph{factorial function} is the function $! : \mathbb{N} \to \mathbb{N}$ that represents the product of the first $n$ natural numbers, where $0!=1$ by convention. \[0!=1\] \[n!=\prod^{n}_{k=1} k\] \end{definition} Alternatively, one can define the factorial function recursively in the dollowing manner. \begin{proposition} The factorial function obeys the following recurrence relation \[0!=1\] \[n!=(n-1)!n\] \end{proposition} The factorial function appears abundantly in the study of enumerative combinatorics, however it also arises in many other fields of mathematics. There \begin{definition} \[(n)_{m} = \prod^{m-1}_{k=0}(n-k) = \frac{n!}{(n-m)!}\] \end{definition} \begin{definition} \[n^{(m)} = \prod^{m-1}_{k=0}(n+k) = \frac{(n+m-1)!}{(n-1)!}\] \end{definition} \section{Permutations with repetition} Relies soley on the multiplication principle. \begin{proposition} There are $n^k$ $k$-tuples that can be formed by a set of $n$ elements with repetition. \end{proposition} \section{Permutations without repetition} Uses the multiplication principle, however noting the fact that the set is depleted after chosing an element due to lack of repetition. \begin{definition}[$k$-permutation of $n$] A \emph{$k$-permutation of $n$ } is a function specified by the solution of the combinatorial problem below. \[ P(n,k) = |\{ (x_i)_{i=1}^{k} : x_i \in \mathbb{N} \cap [1,n] \land x_i \neq x_j \}| \] Essentially, how many ways are there to create strings of length $k$ can be formed from a set of $n$ distinct symbols, where each symbol can be used a maximum of once? \end{definition} \begin{proposition} The following formula counts the amount of $k$-tuples that can be formed by a set of $n$ elements without repetition. \[ P(n,k)= \frac{n!}{(n-k)!}=(n)_{k}\] \end{proposition} \section{Permutations on a multiset} Division principle is used to ignore the permutations between instances of the same element. \section{Combinations} \subsection{Combination without repetition} Permutations count the way to order $k$ objects chosen from $n$ objects. However, what if we're only concern3e with the types of objects that can bw chosen, rather than also counting the ordering of these choices? This is the idea of a \emph{combination}; we first consider the case without repetition. While permutations consider how many $k$-tuples can be formed by our set of $n$ elements; \emph{combinations} consider how many sets (or multisets when repetition is allowed) of cardinality $k$ can be formed. The difference is that permutation counts uniquely ordered strings of elements, while combinations don't; they only care about what elements are \begin{definition}[$k$-Combination of $n$] A \emph{$k$-combination of $n$} is a function specified by the solution of the combinatorial problem below. \[C(n,k) = |\{ S \subseteq \mathbb{N} \cap [1,n] : |S|=k \}| \] Essentially, how many ways are there to create strings of length $k$ can be formed from a set of $n$ distinct symbols, where each symbol can be used a maximum of once and the order of symbols doesn't matter? \end{definition} This problem is extremely similar to the problem of permutation without repetition, however for combinations without repetition we use the division principle to ignore order. \begin{proposition} The following formula counts the amount of $k$-sets that can be formed by a set of $n$ elements without repetition. \[ C(n,k)= \frac{n!}{(n-k)!k!}\] $C(n,k)$ is the combination function. \end{proposition} \subsection{Binomial coefficient} There is an alternate notation for the combination function, called the \emph{binomial coefficient}. It gets its name from its role in the binomial theorem of elementary algebra. \[\binom{n}{k}= \frac{n!}{(n-k)!k!}\] Since the combination function is quite frequent, this notation is more convenient to employ. It gets its name for being related to the coefficients of a binomial when expanded. \[ \binom{n}{k}=\binom{n-1}{k-1}+ \binom{n-1}{k}\] \[ \binom{n}{k}=\binom{n}{n-k}\] \[ \binom{n}{0}=1\] \[ \binom{n}{1}=n\] \[ \sum^{n}_{k=0} \binom{n}{k}=2^n\] \[ \sum^{k}_{j=0} \binom{m}{j}\binom{n-m}{m-j} = \binom{n}{k} \] \[ \binom{2n}{n} = \sum^{n}_{k=0} \binom{n}{k}^{2} \] \[ \sum^{n}_{k=0} \binom{n}{k} = 2^{n} \] \begin{theorem}[Vandermonde's convolution] \[ \binom{r+s}{n} = \sum^{n}_{k=0} \binom{r}{k} \binom{s}{n-k} \] \end{theorem} \subsection{Combination with repetition} An effective method is to - stars & bars approach \begin{proposition} \[ |\{ M : U_M \subseteq \mathbb{N} \cap [1,n] : |M|=k \}| =\binom{n+k-1}{k} \] \end{proposition} - twelvefold way $k$-ary Necklace of length $n$ %\chapter{Examples of combinatorial proofs} %\section{Golomb's proof of Fermat's little theorem} %Therefore there are $a^p-a$ $a$-colored $p$-ary necklaces accounting for symmetry of the necklace. %$p | a^p-a$ %\section{Carmichael's polygon-circle problem} \chapter{Derangements} A particularly interesting formula for derangements that follows from this is one including $e$! One may realise the similarity of our previous series to the definition of the exponential function; it is essentially a partial sum of the series for $\frac{1}{e}$! \begin{definition}[$n$-derangements] surjective operations of $n$ elements with no fixed points. \[D_n = | \{ (f : \mathbb{N}\cap[1,n] \to \mathbb{N}\cap[1,n]) : f \text{ is surjective } \land \nexists n \in \mathbb{N}\cap[1,n] [ f(n) = n ] \}| \] \[D_0 = \{ (f : \emptyset \to \emptyset) : f \text{ is surjective } \land \nexists n \in \emptyset [ f(n) = n ] \}| = 1\] \end{definition} \begin{proposition} \[D_n = n! - [ \sum^{n-1}_{k=2} \binom{n}{n-k} D_k ] -1\] \[D_n = n! - \sum^{n}_{k=1} \binom{n}{k} D_k \] \end{proposition} \begin{proposition} \[D_n = n! \sum^{n}_{k=0}\frac{(-1)^k}{k!}\] \end{proposition} This can be proven by using the inclusion-exclusion principle to count the amount of permutations with each $k$ being mapped to $k$, then minusing this from $n!$. Noting the similarity of this formula to the partial sums of the series for $e$, we can prove the following. \[ D_n = [ \frac{n!}{e}] \]