A partition of $[n]$ is non-crossing if whenever four distinct elements $1\le a < b < c < d \le n $ are s.t. $a, c$ are both in one block and $b, d$ are both in another one, then the two blocks coincide.
I have showed that the number of non-crossing partitions (by dividing when $k$ and $n+1$ are connected and when they are disjointed) is:
$$ f(n+1) = \sum_{k=1}^{n+1} f(k-1)f(n+1-k) $$
Which is the recurrence formula for the Catalan's numbers as $f(0) = 1 = C_0$.
How to find a recurrence for the number of non-crossing partitions of $[n]$ without singletons? I have not found a good line of reasoning yet.
Count the number $f(n)$ by cases of how many singletons the partition has. Let's denote by $g(n)$ the number of noncrossing partitions of $[n]$ without singletons. We have
$$f(n) = \sum_{j=0}^n {n \choose j}g(n-j)$$
because we can choose the $j$ singletons out of $n$ numbers and then the rest forms a non-crossing partition of $[n-j]$ without singletons.
We can express this as a matrix equation $f = Ag$ where $A = [{i \choose j}]_{ij}$.
Now (see for example here)
$$A^{-1} = [(-1)^{i+j}{i \choose j}]_{ij}$$
So we have a formula for the vector $g$ (since we know $f(n)=\frac{1}{n+1} { {2n} \choose n}$ are the Catalan numbers):
$$g(n) = \sum_{j=0}^n \frac{(-1)^{n+j}}{j+1} { {n} \choose j} { {2j} \choose j}. $$
EDIT:
These are the Riordan numbers (a more general OEIS-sequence was already linked by Jean Marie)
In the paper: link the following generating function equation is given and used to derive a recursion.
If we put $y = \sum g(n)x^n$, then
$$y = \frac{1}{1+x} + xy^2.$$
Implicit differentiation and arduous algebraic manipulation of the equations leads to
$$1 - x(1+x)(1-3x)y' = (1-3x^2)y.$$
From this the recursion
$$g(n) = \frac{n-1}{n+1}\left(2g(n-1)+3g(n-2)\right)$$
can be read.