### Catalan Numbers

I'm sure you've heard of the Fibonacci numbers, but have you heard of the Catalan numbers?

I'm sure you've heard of the Fibonacci numbers, but have you heard of the Catalan numbers?

Among other things the Catalan numbers are the number of ways to apply binary operations on an ordered set of items. For example suppose your set is 4 numbers and your operation is subtraction. Then you can have ((1 - 2) - (3 - 4)), or (1 - ((2 - 3) - 4)), etc.

A set with n elements has C_(n-1) structures. Here are the structures for 4 elements or C_3.

a b c d (((a b) c) d) \/ / / \/ / \/ a b c d ((a (b c)) d) \ \/ / \/ / \/ a bc d ((a b) (c d)) \/ \/ \ / \/ a b c d (a ((b c) d)) \ \/ / \ \/ \/ a b c d (a (b (c d))) \ \ \/ \ \/ \/

C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42, C_6 = 132, ... Catalan Number

notify me: yes

http://derocher.org/~brian//trackback.php?ParentId=153

## Math Puzzle

notify me: yes