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:
$N$ element set?$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.
$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:
Sequences:
Fibonacci numbers are given by following recurrence relation:
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.
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:
Sequence A001006 captures the values, with starting values being: 1, 1, 2, 4, 9, 21, 51, 127, …
