Integer sequences
Today I had use for the On-Line Encyclopedia of Integer Sequences.
ID Number: A000108 (Formerly M1459 and N0577)
URL: http://www.research.att.com/projects/OEIS?Anum=A000108
Sequence: 1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,
2674440,9694845,35357670,129644790,477638700,1767263190,
6564120420,24466267020,91482563640,343059613650,
1289904147324Name: Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!). Also called Segner numbers.
Comments: Schroeder’s first problem. A very large number of combinatorial interpretations are known - see references, esp. Stanley Volume 2.
Number of ways to insert n pairs of parentheses in a word of n+1 letters. E.g. for n=3 there are 5 ways: ((ab)(cd)), (((ab)c)d), ((a(bc))d),
(a((bc)d)), (a(b(cd)).
Shifts one place left when convolved with itself.
For n >= 1 a(n) is also the number of rooted bicolored unicelluar maps
of genus 0 on n edges. - Ahmed Fares (ahmedfares(AT)my-deja.com), Aug
15 2001
Ways of joining 2n points on a circle to form n nonintersecting chords.
It makes me happy that that’s out there. For more fun, look up the terms, e.g., Catalan Numbers, on MathWorld.
OK- you got my curiousity going. How did you encounter the Catalan numbers?
Posted by Brian on September 2 2004 19:56
The current Perl Quiz-of-the-Week is to, for an integer n, enumerate the strings of length 2n of balanced parentheses (the equivalent problem of enumerating the binary bracketings of n+1 variables.)
I already had a solution before I went hunting on the web. Everyone showed how to count them; no one I found had an algorithm to enumerate them.
I've got a new solution I think will be hard to beat... it's iterative and has no wasted steps -- each loop produces one string.
Do you know any clever ways to enumerate binary bracketings, Brian?
Posted by Zed on September 2 2004 20:44
Yep- see Stanton and White, "Constructive Combinatorics." This book is one of the best
sources on algorithms for listing combinatorial objects. The older book by Nijenhuis and Wilf is
also useful.
Posted by Brian on September 2 2004 22:14
Cool, thanks. The UC Berkeley Math Library has them both on the shelf -- I'll go look at them tomorrow. (Cal generally allows the public stack access without borrowing privileges.)
Posted by Zed on September 2 2004 23:11
No luck with those or any of the combinatorics texts I looked it (well, within the limits of my superficial browsing and my ability to read the math.) Those lazy combinatorialists only care about coming up with clever ways to count sequences to avoid having to enumerate them!
Posted by Zed on September 5 2004 04:16
Hmmm. I took a look at Stanton and White when I got back to the office this morning, and your right that they don't give an algorithm for listing these, but just give the bijections between the various structures in the Catalan family. There's an obvious backtracking algorithm for constructing these, but I can't think of anything better.
One thing that might be causing problems in your search for information on this is terminology. In combinatorics, "enumeration" means counting, not listing.
Posted by Brian on September 7 2004 09:06
Here is a recent paper that gives an algorithm for this problem.
Tadao Takaoka, "O(1) Time Algorithsm for Combinatorial Generation by Tree Traversal" The Computer Journal 42(5):400-408, 1999.
I got it from the URL:
http://www3.oup.co.uk/computer_journal/hdb/Volume_42/Issue_05/pdf/420400.pdf
Posted by Brian on September 7 2004 09:21
The obvious backtracking solution being generating all strings of the right length with equal numbers of parentheses and testing them for balanced-ness? Given how fast the Catalan numbers grow, that would quickly become unfeasible.
Thanks for the terminology correction. And thanks for the paper! I implemented its algorithm in Perl, and it's fast. It's faster than mine, which surprises me to look at them.
Posted by Zed on September 7 2004 12:23
The obvious backtracking algorithm is a bit more sophisticated than that. You construct the string from left to right, backtracking whenver you get to a point with more right parens than left parens (since this is illegal). At each position you'll first try "(", and then later when the algorithm backtracks to that position, you'll try ")". Every time that you get a full string of length n, you'll also have to check for balance.
In any case, the algorithm given in the paper is much better than this, generating successive strings in O(1) time.
Posted by Brian on September 7 2004 18:42
Brian said on September 2, 2004 10:14 PM
"... The UC Berkeley Math Library .... (Cal generally allows the public stack access without borrowing privileges.)"
Hot button alert! You've hit a hot botton!
It is true the Math lib allows you browse, but the Main library and Moffit don't without a card. Which pisses me off because Cal is a public university, owned by the public, paid for with public taxes, so it should be open to the public.
(There are some ways to access it. Problem for th e reader.)
Just don't let them get away with making everyone think that they OWN it, those regents. Everybody owns it.
Especially when they try to privatize it. (Just wait.)
Posted by asdfasdfdfd on September 8 2004 13:43