\chapter{Combinatorial numbers}


\section{Applications of number theory in combinatics}

Many integer sequences arise from problems in combinatorics. There are also integer sequences studied in number theory that have applications in combinatorics. To complicate matters, number theorists occasionally study combinatorial numbers from a number theory perspective. It has been a challenge to decipher which types of numbers should be ascribed to Enumerative Combinatorics or Elementary Number Theory; the philosophy I've taken is that any sequence that has historical recognition as combinatorial or is conventionally studied in a combinatorial perspective rather than a number theoretic one shall be listed under this chapter. There are a few points of contention on what I have included, however if the reader should be interested in a holistic view of integer sequences, please do read Elementary Number Theory; the two books go hand in hand in many respects.

Before defining and studying the main combinatorial numbers, we shall look at combinatorial applications from particular sequences from Elementary Number Theory. Familiarity with such sequences will be assumed, so their definitions will not be listed here.



\section{Fibonacci sequence}

The Fibonacci sequence is the familiar recurrence relation below.

\[ F_n = F_{n-1} + F_{n-2},F_0 = 0,F_1 = 1\]

It is studied as an integer sequence in its own right in number theory, however we will focus on the combinatorial aspects of this sequence. Using the definition of Fibonacci numbers

\[\sum^{\infty}_{n=0} F_n x^n = \frac{x}{1-x-x^2}\]

\subsection{Sums of 1 and 2}

\begin{example}
	\[ \mathbf{F_n} = |\{ (a_k)_{k\in \mathbb{N}} :  a_k \in \{1,2\} \land \sum^{m}_{k=1} a_k = n \}| \]
\end{example}

1	1
2	11,2
3	111,12,21
5	1111,112,121,211,22
8	11111,1112,1121,1211,2111,122,212,221

This combinatorial problem is solved by noting that one can calculate the terms recursively by considering sequences starting with  '2' next to any sequence adding up to $n-2$, or '1' next to any sequence adding up to $n-1$. 
The combinatorial problem can be solved in another way, giving rise to the following formula.

\[ \mathbf{F_n} = \sum^{\lfloor \frac{n-1}{2} \rfloor}_{k=0} \binom{n-k-1}{k}\]
\[ \mathbf{F_n} = \sum^{\lfloor \frac{n-1}{2} \rfloor}_{k=0} \binom{n-k-1}{k}\]

Deriving new closed forms in this way is an example of the power of double counting in combinatorics. It would be possible (but messy) to derive this using real analysis to calculate the Taylor series for the Fibonacci number's generating function, although the method of double counting generally appeals better to the intuition and may be considered more elegant.


\subsection{Rabbit problem}

This problem is really the same as the former; they can be mapped to one another.


\section{Catalan numbers}



We will take the following as the definition of the Catalan numbers, this is known as Senger's recurrence relation.
\begin{definition}[Catalan numbers]
\[ C_{n} = \sum_{k=1}^{n} C_{k-1} C_{n-k} \]
\end{definition}


By substituting this definition into the generating function series and keeping in mind that we want $C_0 =1$, we can use our definition to deduce the generating function of the Catalan numbers.

\begin{proposition}
\[ \sum^{\infty}_{n=0} C_{n} x^{n} = \frac{1-\sqrt{1-4x}}{2x}\]
\end{proposition}

One can use methods from real analysis to find a Taylor series of $\frac{1-\sqrt{1-4x}}{2x}$ and in doing so, find a closed form for the Catalan numbers.

\begin{proposition}
\[ C_n = \frac{1}{n+1} \binom{2n}{n} \]
\end{proposition}

This is a rather modern, mechanical approach combinatorics permits to evaluate a closed form of an integer sequence, however combinatorial beauty is found by studying the nature of specific counting problems in which this sequence appears.

We will now see the motivation of this definition by looking at various counting problems where it has historically arisen, starting with Dyck words (what an unfortunate name).

\subsection{Dyck words}
The problem of Catalan numbers arises in the counting of balancing brackets, or Dyck words.
1	()
2	(()),()()
5	((())),(()()),()(()),(())(),()()()
14	(((()))),((()())),(()(())),((())()),(()()()),()((())),()(()()),(())(()),()()(()),((()))(),(()())(),()(())(),(())()(),()()()()


\[ C_n = \binom{2n}{n} - \binom{2n}{n+1} \]

\subsection{Mountain ranges}
\subsection{Lattice paths}


\section{Eulerian numbers}


\section{Stirling numbers}
\section{Bell numbers}

Their history traces back to medieval Japan, being represented as chapter symbols in the 'tale of Genji'.

	\[B_n = |\{ X \subseteq \mathcal{P}(\mathbb{N}\cap [1,n]) : X \text{ is a partition of } \mathbb{N}\cap[1,n] \} | \]

	\[ B_n = \sum^{n-1}_{k=0} \binom{n-1}{k}B_{n-k-1} \]

\subsection{Dobiński's formula}


\section{Counting partitions}

The partition function is an arithmetic function, studied in number theory. nevertheless