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...

3 comments:

rohedi said...

Oh my GOD, the Catalan Formula is very difficult to be calculated. Yeah, the two irrational numbers pi and square root collect together. If calculators are not available until now, o.o.o indeed very tiring to calculate the Cn value.

Denaya Lesa said...

Apologise Mr.Pat, Denaya late in saying happy Pi Day for you and all visitors here.

We know that Pi Day has been commonly associated with the birth of Einstein that known as the greatest scientists on the 20th century. Denaya believes there are so-many people are inspired to becomes great scientist like him. According to my father Mr.Rohedi, the photoelectric effect that given Nobel prize for Einstein have proved the existence of Planck constant as indicated previously on the formula of spectral density of black-body radiation. Hehehehe.. here Denaya invites you all to visit this link

http://eqworld.ipmnet.ru/forum/viewtopic.php?f=2&t=34&start=30

to read the performance of a smart method called as SMT (shortenned from Stable Modulation Technique) in creating Planck Formula for the spectral density of black-body radiation in two forms, where the pi number exists on the New Planck Formula.

Thanks you for your attention,
Best Regards,
Denaya Lesa.

Anonymous said...

iKendu is a new Sudoku like logic puzzle game now available for the iPhone and iPod touch.

Click here to check out iKendu

If you like Sudoku, you'll love iKendu!