# From problem to generating functions

I am trying to understand how I can derive a generating function for the following problem:

Given are $2n$ points $\{1, ... ,2n \}$ arranged on a line. Now each points gets connected to exactly one other point by an arc. But the arrangement of arcs need to be connected, this means that each two arcs can be connected by a chain of crossing arcs, where two arcs $\{a,b\}$ and $\{c,d\}$ cross iff $a<c<b<d$. The goal is to count $c_n$, i.e. the number of ways to arrange $n$ connected arcs among $2n$ points.

Here is the argument how to come up with a generating function:

In order to get a hand onto it one removes the arc $\{1,a\}$. Thus the arrangement falls into $k$ non empty connected components $X_1, ... , X_k$, where $X_i$ consists of $n_i$ many arcs. Furthermore, all of $X_1, ... , X_k$ are nested, meaning that $X_{i+1}$ lies in one of the $2n_i-1$ many spaces between consecutive elements of $X_i$. Furthermore, $a$ lies in one of the $2n_k-1$ consecutive elements of $X_k$.

The part mentioned above is absolutely clear to me.

But what I don't understand is why it is so easy to now conclude that the generating function $A$ for $c_n$ follows the equation $A= x\sum_{k \geq 0} (2xA'-A)^k$.

I can see some resemblance but I am far from understanding how to derive this equation for $A$.

-

[The sequence $c_n$ is number A000699 in the OEIS. Also, see Flajolet and Noy, Analytic Combinatorics of Chord Diagrams (INRIA research report #3914), $\S1$, p. 2, and the earlier question From generating functions to recurrence on this sequence.]

Let $I_n:=\{1,\ldots,2n\}$. Suppose that, in a connected arrangement of arcs on $I_n$, we mark one of the segments $[i,i+1]$, where $i\in\{1,\ldots,2n-1\}$. Call the number of marked arrangements $d_n$; obviously $d_n=(2n-1)c_n$. Let $B:=\sum_{n>0} d_n x^n$ be the generating function for $d_n$.

By the argument you give above, given a connected arrangement of arcs on $I_n$, after removing $\{1,a\}$, we get a sequence of connected arrangements of arcs on subsets of $I_n$, and if we renumber the vertices of each arrangement in an order-preserving manner, we get a sequence $X_1$, $\ldots$, $X_k$ of connected arrangements of arcs on $I_{n_1}$, $\ldots$, $I_{n_k}$, where $n_1+\cdots+n_k=n-1$. Since the sequence we started with is nested, for $i=1$, $\ldots$, $k-1$, we can mark the segment in each $I_{n_i}$ which, in the original arrangement, would be expanded to contain $X_{i+1}$; in the case $i=k$, mark the segment which is expanded to contain $a$. This gives a sequence $X'_1$, $\ldots$, $X'_k$ of marked connected arrangements of arcs on $I_{n_1}$, $\ldots$, $I_{n_k}$ from which the original connected arrangement of arcs on $I_n$ can be recovered. Therefore, there is a bijective correspondence between

• connected arrangements of arcs on $I_n$

and

• sequences of marked connected arrangements of arcs on $I_{n_1}$, $\ldots$, $I_{n_k}$, where $n_1+\cdots+n_k=n-1$. ($k$ may be zero, in which case the sequence is empty.)

So, $$c_n=\sum_{k\ge 0} \sum_{n_1+\cdots+n_k=n-1} d_{n_1}\cdots d_{n_k}.\qquad (1)$$ To turn (1) into an equality of generating functions, multiply each side of (1) by $x^n$ and sum over $n$. Doing this to the left-hand side gives $A$, the generating function for $c_n$. If we fix some $k$ in the right-hand side and then perform the multiplication and summation, we get $$\sum_{n>0} \sum_{n_1+\cdots+n_k=n-1} d_{n_1}\cdots d_{n_k} x^{n}$$ $$= \sum_{n>0} \sum_{n_1+\cdots+n_k=n-1} d_{n_1}\cdots d_{n_k} x^{n_1+\cdots+n_k+1}$$ $$= x \sum_{n_1,\ldots,n_k} d_{n_1}\cdots d_{n_k} x^{n_1+\cdots+n_k},$$ which is equal to $$x B^k.$$ Therefore, reinserting the summation over $k$ gives $$A=x \sum_{k\ge 0} B^k.\qquad (2)$$ But, since $$A=\sum_{n>0} c_n x^n$$ and $$2xA^\prime = \sum_{n>0} 2nc_n x^n$$ we have $$2xA^\prime-A = \sum_{n>0} (2n-1)c_nx^n = \sum_{n>0} d_n x^n=B.\qquad (3)$$ Combining (2) and (3) gives $$A=x \sum_{k\ge 0} (2xA'-A)^k,$$ as desired.

-
Thank you very much for the nice answer. The only thing I don't understand is why $n_1+...+n_k=n−1$ and not $n_1+...+n_k=2n-2$ – stefan Feb 2 '12 at 16:10
It's because the $n_i$s count arcs, rather than points. – David Moews Feb 2 '12 at 17:05