# Making Heads or Tails out of Recursion and Combinatorial Math

### GNU — GNU’s Not Unix

I thought I’d take a look at two topics at once and make some fun by mashing them together. Today’s topic
is **recursion**. In computer science (and in math, although we call the equation a
recurrence relation) recursion is an often misunderstood concept causing lots of
panic and anxiety. In reality - it’s pretty easy once you wrap you head around the idiom.

## What is recursion?

When we define a function in such a way that it calls itself, we’ve defined a recusive function. The most basic example is the
Factorial function, $f(n)=n!$. We define the function *recursively* by defining it
in reference to itself. So, recursively, we define $f(n)$ as:

$n!=n*(n-1)!\text{, for } n > 0, \text{and } 1, \text{when } n = 0$.

For example 5! = 5*4!, and 4! = 4 * 3! … and 0! = 1. Or, $f(5)=\prod_{i=1}^ni$

## Lot’s of functions can easily be defined recursively

In addition to the factorial function, there are lots of other natural relationships that are conveniently defined recursively.

Let’s take a closer look at the last one as they are of interest in combinatorical mathematics as well as computer science.

## Catalan numbers

Simply put, catalan numbers are natural numbers that often appear in counting problems (combination and permutations of enumerated sets).

We define the sequence of numbers, starting with index zero, as:

$$C_n = \dfrac{1}{n+1}\dbinom{2n}{n}\text{, for }n \ge0$$

For those not familiar with the notation, $\dbinom{a}{b}$, it defines a combination such that:

$$\dbinom{a}{b} = \frac{a!}{b!(a-b)!}$$

So, we can use our factorial function above and we can calculate the catalan numbers starting with $C_0 = 1$. The next numbers in the sequence are:

$1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670$, …

As you can see they get large rather fast. Catalan numbers can also be defined recursively. Instead of computing them with our formula above, we can define a recurrence relation as:

$$C_0=1\text{, and }C_{n+1}=\sum_{i=0}^nC_i C_{n-i}\text{ for }n\ge0$$

Given the above recurrence relationship, we can define a recursive function that computes $C_{n+1}$ from $C_n$, etc all the way down the line to our non-recursive definition of $C_0=1$.

So what’s the big deal about these seemingly random numbers generated either explicitly or recursively? It turns out that there are many applications where the corresponding $C_n$ counts a particular property. For example, Given $n$ pairs of parentheses, how many ways can we count correctly-matched open and closed parentheses in a string?

Say $n=3$ we can count $C_3=5$ correctly matched parentheses-strings:

- ((()))
- ()(())
- ()()()
- (())()
- (()())

Another example comes from geometry. Given a convex polygon with $n+2$ sides, $C_n$ is the number of different ways the polygon can be cut into triangles by connecting verticies with non-crossing line segments.

So for example a six-sided polygon can be cut $C_4=14$ ways.

Turns out there’s another interesting property of catalan numbers. We can construct a special matrix of catalan values, such that the $H_{i,j}=C_{i+j-2}$.

$$H=\begin{bmatrix} 1 & 1 & 2 & 5 \\ 1 & 2 & 5 & 14 \\ 2 & 5 & 14 & 42 \\ 5 & 14 & 42 & 132 \\ \end{bmatrix}$$

A cool property of $H$ is that regardless of how large we make it, the $\text{det(}H\text{) = }\lvert H \rvert$ is always $1$.

Let’s turn all this into some python code and use **numpy** to play with our arrays and see if this is indeed the case.

I’ll define two functions, **catalan(x)**, and **hankel(n)**. (Hankel is the name of Matrix that has the catalan numbers in the associated $H_{i,j}$ indicies.)

```
import math
import numpy as np
def catalan(x):
if x == 0:
return 1
else:
return int(2*(2*x+1)/(x+2)*catalan(x-1))
def hankel(n):
l = n*n
h = np.zeros([n,n], dtype=int)
for i in range(n):
for j in range(n):
h[i,j] = catalan(i+j)
d = np.linalg.det(h)
print("h = \n", h)
print("the determinant of the matrix is ", int(d+0.5))
hankel(5)
hankel(3)
```

Running our program shows:

```
h =
[[ 1 2 5 14 42]
[ 2 5 14 42 132]
[ 5 14 42 132 429]
[ 14 42 132 429 1430]
[ 42 132 429 1430 4862]]
the determinant of the matrix is 1
h =
[[ 1 2 5]
[ 2 5 14]
[ 5 14 42]]
the determinant of the matrix is 1
```

Notice that we create both a $H_{5 x 5}$ and a $H_{3 x 3}$ Matrix and each one has a $\text{det(}H\text{)} = 1$

Rather than define our function **catalan(x)** explicitly, can you write a recursive function (using the recurrence relation definition at the top of the section)?

Drop me a note if you need help! Or see the answer below.

```
def catalan(n):
if n <=1:
return 1
sum = 0
for i in range(n):
sum += catalan(i)*catalan(n-i-1)
return sum
# print out the first 15 catalan numbers
for i in range(15):
print(catalan(i))
```

Enjoy!