Basics

You can add to get to any Number

Let

a, b \in ℤ

, then there exists some

k \in ℤ

such that

a + k = b

If we want the equation to hold true, we require some

k \in ℤ

such that

k = b - a

, since the integers are closed under subtraction, this value works as verfied by the fact that

a + (b - a) = b

Numbers from Zero to K

Let

k \in ℕ_{0}

and define the set

X_{k} : = {x \in ℕ_{0} : 0 \leq x \leq k}

, then

| X_{k} | = k + 1

We prove the claim by induction, for the base case if $k = 0$ , then $X_{k} = {0}$ thus $| X_{k} | = 1 = 0 + 1 = k + 1$ as needed.

Let $n \in ℕ_{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)} = {x \in ℕ^{0} : 0 \leq x \leq n + 1} = X_{n} \cup {n + 1}$ , thus $| X_{(n + 1)} | = | X_{n} | + 1 = n + 1$ as needed.

The Number of Integers between Two Integers Inclusive

Let

a, b \in ℤ

such that

a \leq b

, then

| {x \in ℤ : a \leq x \leq b} | = b - a + 1

We know that there is some $k \in ℤ$ such that $b = a + k$ , therefore we're looking at the set ${x \in ℤ : a \leq x \leq a + k}$ , this set is in clear bijection with the set ${x \in ℤ : 0 \leq x \leq k}$ through the function $f (x) = 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 (a) = f (b) = y

Catalan Numbers

Let

n \in ℕ_{0}

, then the number of lattice paths from

(0, 0)

(n, n)

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 (n) = \frac{1}{n + 1} (\binom{2 n}{n})

Bracket String

A bracket string is a finite tuple

(a_{1}, \dots a_{k})

such that

a_{i} \in {(,)}

For example "())))(" is a bracket string.

Valid Bracket String

A bracket string

(a_{1}, \dots, a_{k})

is said to be valid by considering the mapping

f : {(,)} \to {- 1, 1}

such that for any

j \in [1, \dots k]

\sum_{i = 1}^{j} f (a_{i}) \leq 0 and \sum_{i = 1}^{k} f (a_{i}) = 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

(0, 0)

(n, n)

which never crosses the diagonal.

Consider the construction of a lattice path

l

from a valid bracket string

If $a_{i} = ($ then $l_{i} = R$
If $a_{i} =)$ then $l_{i} = U$

We can prove that this is a lattice path not crossing the diagonal by the definition of valid bracket string.

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 (n)

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 (n)

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{matrix} (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{matrix}

For every

n \in ℤ^{+}

, let

M (n)

denote the number of distinct interpretations of the expression "the star of

a_{1}, a_{2}, \dots, a_{n}

" (where

a_{1}, a_{2}, \dots, a_{n}

are arbitrary elements in

S

). Show that

M (n) = \frac{(2 (n - 1))!}{(n - 1)!}

One can count

M (n)

by first fixing a valid bracket arrangement and then permuting elements with that valid bracket arrangement, moreover note that the star of

a_{1}, \dots a_{n}

contains

n - 2

bracket pairs.