Non-crossing Partition I'm trying to solve following problem, and I got stuck.
Let be $[n]=\{1,...,n\}$.
Def. A partition $\pi$ of $[n]$ is called non-crossing, if $a$ and $b$ belong to one block and $x$ and $y$ to another, they are not arranged in the order $a<x<b<y$.
Def. We call singleton a block that contains only one element.
Let be $f(n)$ number of non-crossing partitition of [n], that contains no singletons. Find a recurrence for f(n).
I'll indicate $\Pi$, set of non-crossing partition of $[n]$. If $A\subseteq \Pi$, then $A^c=\Pi ∖ A$.
My idea was the following, let be $A_j=\{\text{non-crossing partitions of $[n]$, such that the block, containing $j$, is a singleton}\}$. I know that the number of non-crossing partition of $[n]$ is $n^th$ Catalan's number($C_n$). So that $|A_j|=C_{n−1}$, because if i remove j, remaining elements must be partitioned in "non-crossing way".
So $f(n)=|\bigcap_{j∈[n]}A^c_j|$, and by applying Inclusion-Exclusion's Principle, I got formula:
$$f(n)=\sum_{k=0}^n\binom{n}{k}(−1)^{n−k}C_k$$
which is far from the reccurrence I'm looking for.
I'm wondering if there is a way to obtain a reccurence from that formula, or I have to choose a different approach.
Thanks in advantage
PS: according to [http://oeis.org/A005043], formula, that I've found is correct, and recurrence is $$f(n+1)+(-1)^n=f(0)f(n)+f(1)f(n-1)+\dots +f(n)f(0)$$ or $$f(n)=\frac{n−1}{n+1}(2f(n−1)+3f(n−2))$$.
 A: Here's a simple combinatorial argument giving a positive recurrence (though not precisely the recurrence you asked for):
Consider the number of singleton-free noncrossing partitions of $[n + 1]$ in which the smallest element in the same block with $n + 1$ is $i + 1$.  Since $n + 1$ is not a singleton, $0 \leq i \leq n - 1$.  Obviously any such partition restricts to a singleton-free noncrossing partition on $[i]$, and there are $f(i)$ of these.  To complete the partition, we have two possibilities (independent of our choice on $[i]$): either $\{i + 1, n + 1\}$ is a complete block, or there are other entries in the block.  In the first case, the partition restricts to a singleton-free noncrossing partition on $\{i + 2, \ldots, n\}$, and there are $f(n - i - 1)$ choices here.  In the second case, "restrict to $\{i + 1, \ldots, n + 1\}$ and then delete $n + 1$" is a bijection with singleton-free noncrossing partitions on $\{i + 1, \ldots, n\}$, and there are $f(n -i)$ of these.  Putting this together, we have that for $n \geq 0$,
$$
f(n + 1) = \sum_{i = 0}^{n - 1} f(i) \cdot (f(n - i -1) + f(n - i)).
$$
