Okay, so here's an interesting question regarding web forums. Let's say you have a typical forum, such as the comments section on a blog, or whatnot. Viewers can post comments in response to either the initial blog post (in which case the post appears at the bottom of the list), or as replies to any previously existing comments (in which case the post appears below the comment they're replying to, indented). Nothing revolutionary, you've seen it on hundreds of websites before.
Here's the question. After N comments have been posted, how many topologically unique arrangements can there be for the comments in the forum? What I mean is, if you were to look at the shape of the posts in the thread (ignoring their content and time of posting), how many unique arrangements can there be? This means that for 3 posters, A, B, and C, the following cases are equivalent:
A A
└─B └─C
C B
So for N = 3, the total number of arrangements is 5:
A A A A A
B B └─B ├─B └─B
C └─C C └─C └─C
If it weren't for the topologically unique restriction, the answer would be simply f(N-1) * N, or N!. For N < 3, this actually holds; f(0) = f(1) = 1, and f(2) = 2. The first poster has no choice of where to post, and the second can reply to either the initial blog or to the first poster. But from then on, it gets more complicated. f(3) would be 3! or 6 if it weren't for that duplicate case. For higher N's, there are more and more equivalent cases. Can anyone come up with a simple formula that will cover this for any N?
The anser is the Catalan number $C(n)=\frac{(2n)!}{n!(n+1)!}$, which is also "the number of ordered rooted trees with $n$ nodes, not including the root" (cf. OEIS). Here, the not included root is "the forum itself".