Making Heads or Tails out of Recursion and Combinatorial Math

2017-11-09 Programming Math Python

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!