Sunday, 15 March 2009

Catalan Asymptotic Function

I have written before about the Catalan Functions, named for Eugene Catalan of Belgium (1814-1894). I recently came across a note on the "God Plays Dice" blog that gave an asymptotic function for the Catalan Numbers (an Asymptotic function gives you a value it approaches as N gets larger and closer to infinity).. The value is given as
The nice part of this is that if n is pretty big, you can ignore all the stuff in parentheses. For example the 6th Catalan number is 132, and the value outside the parentheses is about 157.. ok, a little high, but as you work your way up, the error is smaller and smaller (at least percentage wise)... and always an upper bound (too much)....
There was also a cute joke of the kind that only a matematician could appreciate, "identify the sequence "una, dues, cinc, catorze, quaranta-dues, cent trenta-dues, quatre-cent vint-i-nou,...", which are the Catalan numbers 1, 2, 5, 14, 42, 132, 429... in the Catalan language."

Catalan Numbers first appeared in disguise in a problem Euler first proposed to Christian Goldbach in 1751. The problem is now called "Euler's Polygon Division Problem", and asks, in how many ways may a plane convex polygon of n+2 sides be divided into triangles by diagonals. The answer, of course, is the nth Catalan number.

The numbers in the Catalan sequence also answer questions such as the following. In how many paths can you move from the origin of a coordinate axis to the point (n,n) if each move consists of either an upward move or a move to the right one unit between two lattice points and you cannot cross the line y=x . Another application answers the question in how many ways can 2N beans (for an application, think votes) be divided into two containers if one container can never have less than the second?

The numbers can be found from Pascal's triangle by taking (2n Choose n) - (2n Choose n+1). These are two adjacent numbers in each even numbered row (2-1; 6-4; 20-15; etc...
Post a Comment