Let $f(n+1)$ be the number of non-crossing partitions without singletons of $\{1,2,\dots,n+1\}$. There is a well known bijection between the non crossing-partitions (counting also those with singletons) and the Dyck paths by putting $UD^{\lambda_1}UD^{\lambda_2}\dots UD^{\lambda_{n+1}}$, where $$\lambda_i = \begin{cases} \text{the cardinality of the block}, & \text{if $i$ is maximal in its block} \\ 0, & \text{otherwise} \end{cases}$$

an example from https://www.researchgate.net/publication/1888140_Catalan%27s_intervals_and_realizers_of_triangulations/figures?lo=1

The number of Dyck paths of half-length $n+1$ is given by the famous Catalan numbers recurrence: $$C_{n+1}=\sum_{k=0}^nC_kC_{n-k}$$

Now, I want to find a recurrence for $f(n+1)$ which will be not that far from the Catalan decomposition, since we can see the non-crossing partitions of $\{1,2,\dots,n+1\}$ as a subset of the Dyck paths:

to do this, starting from $(0,0)$, I can set the very first step that is required to be a $U$, similarly I can fix the first step, to the right of $(0,0)$, at which the path hits the $x$-axis. Between those two steps I can settle a Dyck path of half-length $k$, with $k = 0, 1, \dots , n$ (and I have $f(k)$ ways to do that with paths which are images of non-crossing partitions without singletons), the remaining path of half-length $n-k$ will be covered in $f(n-k)$ ways. By adding for all of the possible values of $k$ I have found again the Catalan decomposition: $$\sum_{k=0}^nf(k)f(n-k)$$

To have $f(n+1)$ I must subtract $1$ from that sum when $n$ is even and I must add $1$ whenever $n$ is odd, resulting in: $$f(n+1)=- (-1)^n+\sum_{k=0}^nf(k)f(n-k)$$

however, I can't see how to justify that in a combinatorial way, any idea?


1 Answer 1


$f$ generates the Riordan numbers, OEIS A005043, and the combinatorial proof of their Catalan-like recurrence below is adapted from Bernhart's Catalan, Motzkin and Riordan numbers listed as a reference there.

Bernhart defines a short bush as a rooted ordered tree that is either trivial ($0$) or where all internal vertices have at least two children. If $b(n)$ is the number of such bushes with $n$ edges, $b(n)$ satisfies the same Catalan-like recurrence as $f(n)$ through the following almost-bijection between short bushes with $n+1$ edges and ordered pairs of short bushes with $n$ total edges:

Descend into the leftmost child of each vertex from the root $r$ of a short bush $B$ until encountering

  • a vertex $v$ with at least $3$ children: If $v\ne r$, $v$ has exactly one sibling $w$; shift the subtree rooted at $v$ except its leftmost branch, denoted $S$ and itself a non-trivial short bush, to $w$ and contract the resulting degree-$2$ vertex to produce another short bush $B'$. $B$ then maps to $(B',0)$. If $v=r$, $B$ instead maps to $(C,S)$ where $S$ is defined above and $C$ is the subtree rooted at $v$'s leftmost child (also a short bush, but may be trivial).
  • a vertex $v$ with $2$ children, the right one of which is not a leaf: Merge that right child with $v$ to get $B'$; $B$ maps to $(B',0)$.
  • a leaf: $B$ in this case is not mapped to anything, and must be a binary tree where all right children are leaves, hence an even number $2k$ of edges. There is only one such tree $B_{2k}$ for each even number.

There exists an inverse to this map, but $(B_{2k},0)$ has no inverse. The existence of these unmatchable objects adds $1$ to $b(n)$ when $n$ is even and subtracts $1$ when it is odd, thus showing the Catalan-like recurrence.

$b(n)$ is in turn equivalent to the number of "feasible" non-crossing partitions of $n$ objects, where no part uses two consecutive items when the items form a circle, and from there equivalent to $f(n)$ through the following bijections:

Postorder-traverse the edges, using unbroken paths under this order as part labels. Then preorder-traverse the edges and write the part labels in this order around a circle – since we started with a short bush, it is easy to prove that the resulting partition is feasible non-crossing.

Now given a feasible non-crossing partition, form its dual by interlacing new items between the old ones and grouping them into new parts using the old partitions as boundaries. The aforementioned property guarantees that the dual partition is non-crossing with no singletons (which would arise iff a part of the old partition used consecutive items), completing the $b(n)=f(n)$ proof.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.