Catalan Numbers

Sat Feb 06, 2010 10:18 am, by isabella2296

Let's say you've got a bunch of parentheses - n, to be exact. And these are really awesome parentheses, too. They're so awesome, you simply can't separate a pair. So for each (, you must have a corresponding ). A valid sequence would be something like (()()(())), but ))()( isn't.

Here's the problem: How many groupings do we have for the values of n?

Well, then. What first? How about making this problem all nice and math-y?

We can say that a group of parentheses is valid if the number of ( equals the number of ) [darn that looks funny, and I will henceforth be making all parenthetical comments in brackets for clarity] and that as we read from left to right, we add 1 for each ( and subtract 1 from each ), and the final number should be nonnegative.

There. All math-ed up.

Hmm. We still don't have much a lead, so let's try listing out all the possibilities for, say, n = 0 through n = 4.

n = 0: Obviously, we have exactly 1 way to do this.
n = 1: () = 1 way
n = 2: ()(), (()) = 2 ways
[from here on out, I won't list the combinations, just the number of ways, because this is highly painful to type]
n = 3: 5 ways
n = 4: 14 ways

Let's see: 1, 1, 2, 5, 14. You might recognize these numbers! But for those of you that don't...

Tune in next week for part 2!

Interesting Resource

Sun Jan 31, 2010 10:48 am, by isabella2296

www.mathsnet.net

There are actually some pretty interesting applets in there. Have fun.

Mr. Holbrook

Sat Jan 23, 2010 5:46 am, by isabella2296

This is the first non-mathematical entry of this blog, commemorating Mr. Holbrook, the greatly esteemed coach of the AAST math team. You devoted so much of your time and money for us, and we were all shocked when you died, to the point that I thought Fanfan was making a cruel joke...

Rest in peace.

Image

Image

Page 1 of 107 [321 Entries]

Goto page: 1, 2, 3, ..., 105, 106, 107 Next

Shoutbox

Shouts

  • contrib?

    By Demosthenes, on Sat Jan 16, 2010 4:29 pm

  • Yeah, sure.

    By isabella2296, on Thu Jan 14, 2010 1:32 pm

  • contrib?

    By abcak, on Thu Jan 14, 2010 7:29 am

  • Sure!

    By isabella2296, on Sat Jan 09, 2010 6:36 am

  • contrib?

    By Thunder365, on Thu Jan 07, 2010 6:28 pm

1350 Shouts

Goto page 1, 2, 3, ..., 268, 269, 270 Next

Copyright

All text, ideas, problems, examples, and anything else in this online encyclopedia, unless otherwise stated, belongs to isabella2296. Nothing may be copied without explicit consent from the stated owner/author, isabella2296, and no one may speak for isabella2296 except isabella2296. Contributors may use their own entries for whatever use they like, but only whatever they write, nothing more, nothing less, without explicit consent. All rights reserved 2009.

About owner

  • Joined: 21 Mar 2008
  • Location: Bleh.
  • Occupation: A Nerdy 13-Year-Old
  • Interests: Guess.

Blog details

  • Blog started: 25 Jul 2008
  • Total entries: 342
  • Total visits: 891951

RSS Feed

RSS Feed