You can add to get to any Number

Let \( a, b \in \mathbb{ Z } \), then there exists some \( k \in \mathbb{ Z } \) such that \( a + k = b \)

If we want the equation to hold true, we require some \( k \in \mathbb{ Z } \) such that \( k = b - a \), since the integers are closed under subtraction, this value works as verfied by the fact that \( a + \left( b - a \right) = b \)

Numbers from Zero to K

Let \( k \in \mathbb{ N } _ 0 \) and define the set \( X _ k := \left\{ x \in \mathbb{ N } _ 0 : 0 \le x \le k \right\} \), then \( |X _ k| = k + 1 \)

We prove the claim by induction, for the base case if \( k = 0 \), then \( X _ k = \left\{ 0 \right\} \) thus \( |X _ k| = 1 = 0 + 1 = k + 1 \) as needed.

Let \( n \in \mathbb{ N } _ 1 \), and assume the claim holds for this value, now we want to prove it holds true for \( n + 1 \). We can see that \( X _ (n + 1) = \left\{ x \in \mathbb{ N } ^ 0 : 0 \le x \le n + 1 \right\} = X _ n \cup \left\{ n + 1 \right\} \), thus \( |X _ (n + 1)| = |X_n| + 1 = n + 1 \) as needed.

The Number of Integers between Two Integers Inclusive

Let \( a, b \in \mathbb{ Z } \) such that \( a \le b \) , then \( |\left\{ x \in \mathbb{ Z } : a \le x \le b \right\}| = b - a + 1 \)

We know that there is some \( k \in \mathbb{ Z } \) such that \( b = a + k \), therefore we're looking at the set \( \left\{ x \in \mathbb{ Z } : a \le x \le a + k \right\} \), this set is in clear bijection with the set \( \left\{ x \in \mathbb{ Z } : 0 \le x \le k \right\} \) through the function \( f \left( x \right) = x - a \), therefore our original set has \( k + 1 \), elements. Moreover \( k = b - a \) which completes the proof.

Pigeon Hole Principle

Suppose that \( f : X \to Y \) is between two finite sets and that \( |X| > |Y| \), then there exists some \( y \in Y \) and \( a \neq b \in X \) such that \( f \left( a \right) = f \left( b \right) = y \)

Catalan Numbers

Let \( n \in \mathbb{ N } _ 0 \), then the number of lattice paths from \( \left( 0, 0 \right) \) to \( \left( n, n \right) \) which never go above then line \( y = x \) is said to be the \( n \)-th Catalan Number

Formula For the \( n \)-th Catalan Number

\[
C \left( n \right) = \frac{1}{n + 1} \binom{2n}{n}
\]

Bracket String

A bracket string is a finite tuple \( \left( a _ 1, \ldots a _ k \right) \) such that \( a _ i \in \left\{ \mathtt{(}, \mathtt{)} \right\} \)

Valid Bracket String

A bracket string \( \left( a _ 1, \ldots , a _ k \right) \) is said to be valid by considering the mapping \( f : \left\{ \mathtt{(}, \mathtt{)} \right\} \to \left\{ -1, 1 \right\} \) such that for any \( j \in \left[ 1, \ldots k \right] \)
\[
\sum _ { i = 1 } ^ j f \left( a _ i \right) \le 0 \text{ and } \sum _ { i = 1 } ^ k f \left( a _ i \right) = 0
\]

Bijection Between Valid Bracket Strings and Lattice Paths

For every valid bracket string involving \( n \) pairs of brackets, this corresponds to exactly one lattice path from \( \left( 0, 0 \right) \) to \( \left( n, n \right) \) which never crosses the diagonal.

Consider the construction of a lattice path \( l \) from a valid bracket string

- If \( a _ i = \mathtt{(} \) then \( l _ i = R\)
- If \( a _ i = \mathtt{)} \) then \( l _ i = U\)

Number of Valid Bracketings is Equal to the \( n \)-th Catalan Number

The number of distinct arrangement of \( n \) pairs of left-right parenthesis which close is equal to \( C \left( n \right) \)

This is true because we constructed a bijection valid bracket arrangments and lattice paths, the latter of which we know has size equal to \( C \left( n \right) \) as needed.

Counting Stars

Let \(S\) be a nonempty set, and \(*\) a binary operation on \(S\), called a star. If \(*\) is not known to be associative, the expression "the star of \(a, b, c\) " (for some \(a, b, c \in S\) ) is ambiguous. It could have one of 12 distinct interpretations:
\[
\begin{array}{llll}
(a * b) * c & a *(b * c) & (a * c) * b & a *(c * b) \\
(b * a) * c & b *(a * c) & (b * c) * a & b *(c * a) \\
(c * a) * b & c *(a * b) & (c * b) * a & c *(b * a) .
\end{array}
\]
For every \(n \in \mathbb{Z}^{+}\), let \(M(n)\) denote the number of distinct interpretations of the expression "the star of \(a_1, a_2, \ldots, a_n\) " (where \(a_1, a_2, \ldots, a_n\) are arbitrary elements in \(S\) ). Show that
\[
M(n)=\frac{(2 \left( n - 1 \right) )!}{\left( n - 1 \right) !}
\]

One can count \( M \left( n \right) \) by first fixing a valid bracket arrangement and then permuting elements with that valid bracket arrangement, moreover note that the star of \( a _ 1, \ldots a _ n \) contains \( n - 2 \) bracket pairs.