Let’s start with refreshing of an enumerative approach to a combinatorics. In such approach main question that’s being asked is “How many different arrangements or configurations are there for a given structure?” It’s important to note that there’s always finite amount of input elements and output configurations and values are non-negative integers. Sometimes it’s about some creative interpretation of inputs to arrive at a meaningful answer, most of the time it’s about arithmetic tricks and long derivations of the formulas.

It’s worth to be aware of The On-Line Encyclopedia of Integer SequencesÂ® (OEISÂ®) which contains information on known integer sequences and it’s possible to query it based on starting terms of a sequence.

Sequences inside OEIS are numbered in a convention Axxxxxx - for example Fibonnaci Sequence is: A000045

How many ways are there to put in a different order `$N$`

different things, for convenience it’s
easy to think about them being numbered from `$1$`

to `$N$`

. Answer being factorial denoted as `$N!$`

Initial values are: 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, …

OEIS entry: A000142

It’s often the case that different problems lead to same answer in terms of counting. Consider questions bellow:

- How many different subsets are there for a given
`$N$`

element set? - How many different strings of lengts
`$N$`

can be constructed from`$0$`

s and`$1$`

symbols?

In both cases the answer is `$2^N$`

, but it also requires some kind of interpretation.

- In case 1 it comes from two possibilities of either including or excluding an element in a subset.
- In case 2 it comes from having an option of putting
`$0$`

or`$1$`

in each of`$N$`

possible characters.

We can see that it’s easy to provide `$1-1$`

correspondence between the two constructions by assuming that putting
`$0$`

on `$N$`

th position means not including `$N$`

th element and conversely including for `$1$`

s.

Initial values are: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, …

OEIS entry: A000079

Binomial Coefficient can be interpreted as number of ways of drawing `$K$`

elements from collection of `$N$`

distinct
elements, it’s called Combination. It’s also worth noting that it’s related to Pascal Triangle.

Now since it’s a two variable object it’s difficult to interpret it as a sequence, but it’s possible to select some parts that are easily submitting to such interpretation. N-Simplex numbers are related to slices of Pascal Triangle and Simplex is a generalisation of triangle.

Forumla being:

$$ \binom{N}{k} = {N! \over {k! (N-k)!}} $$

Sequences:

- 1-Simplex - a line, it’s just a sequence of Natural Numbers A000027 values: 1, 2, 3, 4, 5, 6 …
- 2-Simplex - a triangle, it’s a sequence of Triangular Numbers A000217 values: 1, 3, 6, 10, 15, …
- 3-Simplex - a tetrahedron, it’s a seqnece of Tetrahedral Numbers A000292 values: 1, 4, 10, 20, 35, …

Fibonacci numbers are given by following recurrence relation:

$$
\begin{cases}
F_0 = 0 \\
F_1 = 1 \\
F_n = F_{n-1} + F_{n-2}
\end{cases}
$$

One way of obtaining Fibonacci Numbers is considering question the number of possible tilings
of a line segment with tiles of size `$1 = \bullet$`

and `$2 = \bullet \bullet$`

Well known in Computer Science are binary trees where counting is done by asking how many trees with `$N$`

internal nodes
are possible. The numbers are called Catalan Numbers

By marking `$Internal Node = \bullet$`

and `$External Node = \square$`

we can describe tree structure recursively, here
`$\times$`

denotes Cartesian Product (making a pair).

You start with symbol `$T$`

and then possible substitutions.

$$
\begin{cases}
T = \square \\
T = T \times \bullet \times T
\end{cases}
$$

Sequence A000108 captures the values, with starting values being: 1, 1, 2, 5, 14, 42, 132, …

Similarly, Binary-Unary (Motzkin) Trees can be defined recursively

Start with symbol `$M$`

and then possible substitutions are:

$$
\begin{cases}
M = \square \\
M = M \times \bullet \\
M = M \times \bullet \times M
\end{cases}
$$

Sequence A001006 captures the values, with starting values being: 1, 1, 2, 4, 9, 21, 51, 127, …