Ok, now consider joining $2n$ points on a circle using $n$ nonintersection chords.
How do I prove that the number of ways to join the points equals then $n$-th Catalan number $C_n$?
Thanks!
Combinatorics – Number of Ways to Join the Points
combinatorics
Related Solutions
First of all, I need to remark that the current formulation of the question doesn't seem to be quite right, since the fact that you're working on a circle isn't really used. It also isn't very clear what you mean by "joining into pairs.
However, if I read this question in the following way, it seems to work: We choose $2n$ arbitrary points on a circle. How many ways are there of drawing $n$ lines between $2$ points, such that there are no intersections between these lines inside the circle?
How to prove this? It is easiest to follow what's going on by drawing a few examples and keeping these nearby while reading this. We will denote the number of possibilities given $n$ as $Q_n$.
Now suppose we have $n$ fixed, as well as $2n$ points on a circle. We will fix one point $p_1$ and then give names clockwise: the first point one encounters when walking along the circle, starting from $p_1$, is called $p_2$, etc. The first thing now is to consider to which points $p_1$ may be connected. We remark that if we draw a line between $p_1$ and $p_i$, this divides the remaining points in the sets $X_1=\{p_2,\ldots,p_{i-1}\}$ and $X_2=\{p_{i+1},\ldots,p_{2n}\}$, each corresponding to the points on one side of the line. Since no two lines may intersect within the circle, this imposes a restriction on the possible points $p_1$ may be connected to. Namely, this needs be done in such a way that both sets $X_i$ have an even number of points. That is, we may connect the point $p_1$ to each point $p_{2j}$ with $1\leq j \leq n$. This can easily be seen in a drawing.
Now, what happens when we join up the point $p_1$ with one such point? We have a set $X_1$ of $2n_1$ points lying on a circle that need to be pairwise connected in such a way that no lines intersect, while the same holds for the $2n_2$ points in $X_2$. We therefore notice that if we connect the point $p_1$ to $p_i$, the remaining number of possible line configurations becomes $Q_{n_1}Q_{n_2}$.
The result can now be obtained by adding the numbers of possible configurations corresponding to each line from $p_1$ to some $p_i$. What we get, is that $Q_n = Q_{n-1} + Q_1Q_{n-2}+...+Q_{n-2}Q_1+Q_{n-1}$. It is best to first write it this particular way to avoid any problems `in the middle' when $n$ is odd. If we define $Q_0$ as $1$ (one could argue that there is exactly one way not to draw any lines inside a circle at all), we can express every $Q_n$ by the recurrence relation
$Q_0=1,\qquad Q_n=\sum_{j=0}^{n-1}Q_jQ_{(n-1)-j}.$
I don't know how Catalan numbers have been defined in your case, but this recurrence relation describes them. If you don't know this yet, there must be plenty of sources out there to prove it for you.
My first suggestion would have been to better ask this question on https://math.stackexchange.com/ , but then I just spent some time researching a possible answer. By the way, I found the original quote on Google Books, and also the referenced paper by Selinger 79.
Of course, the factorial indicates the formular describes a problem in combinatorics, but
I was intrigued by the expression (2*(n-1))! as I could not figure out what the 2*(n-1) would refer to.
If we take n as the number of tables ("relations" in database theory language), then n-1 is the number of JOINs. But how should the double of the number of JOINS be relevant for the result?
As it turned out, the formula (2*n)!/n! is related to Catalan numbers (see section Quadruple factorial):
In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects.
From the application
Cn is the number of different ways n + 1 factors can be completely parenthesized (or the number of ways of associating n applications of a binary operator)
I conclude, that if we take a JOIN as binary operator, then the number of alternatives in OP is Cn * number of combinations of tables.
Best Answer
André has sketched one of the two natural approaches. Here’s one of the more straightforward versions of the other.
If you know that $C_n$ is the number of strings of $n$ pairs of correctly matched parentheses, you can try to find a bijection between ways of joining your $2n$ points and correctly matched strings of $n$ pairs of parentheses.
Label the points $1,2,\dots,2n$ clockwise around the circle. Each chord then corresponds to a pair of distinct numbers in $\{1,\dots,2n\}$. Use the chords to lay out a row of $2n$ parentheses, $p_1,p_2,\dots,p_{2n}$, according to the following rule. If the points $k$ and $\ell$ are connected by a chord, and $k<\ell$, make $p_k$ a left parenthesis and $p_\ell$ a right parenthesis.
Show that the resulting string of parentheses is correctly matched. (The fact that the chords don’t cross one another is important here.)
Show that the proceduce is reversible: given a correctly matched string of $n$ pairs of parentheses, there’s a way to reconstruct a set of non-intersecting chords that give rise to it.