article

Action executed in 0.000

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)))
 \ \ \/
  \ \/
   \/
        

Comments

Math Puzzle

tags: Dave, math, puzzle
This was inspired by Dave asking me this question. Given 1 5 6 7, how do you use them each once, and the operations + - * / to get the number 21?
parent post: Catalan Numbers
notify me: yes

Catalan Numbers

C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42, C_6 = 132, ... Catalan Number
parent post: Catalan Numbers
notify me: yes

Post a Comment

* indicates a required field
anonymous (If you want to identify yourself, please sign in first.)
required This field is required.

Max size is 2 MB, aspect ratio 3:4 width:height
required This field is required.
Please include a short description.
required This field is required.

480 characters remaining.
is public

(Use this field if you have to. 3000 characters remaining.)
1 dime, 2 pennies, 2 nickels + 100

Trackback URL

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

form