Problem: In how many ways can brackets be placed around a sequence of n
+ 1 letters so that there are two letters inside each pair of brackets?
Example: ab = (ab) = 1 way
Example: abc = (ab)c, a(bc) = 2 ways
Example: abcd = (ab)(cd), a((bc)d), ((ab)c)d, a(b(cd)), (a(bc))d = 5 ways
Extensions: Find a formula for the nth term.
Note: You will discover what is known as Catalan Numbers. This also can
find how many ways a regular n-gon can be divided into n - 2 triangles if
different orientations are counted separately. This is also the way for
determining how many ways can n votes be cast between 2 candidates so that
the one chosen candidate is never behind in the counting