More generally, one can look for expressions of the form
$f(k) = \sum_{j=1}^{\lfloor(n-1)/2\rfloor} a_j f(j) f(n+1-j)$. It seems to work for all odd $k$. For example:
$$\eqalign{f \left( 3 \right) &= \left( f \left( 1 \right) \right) ^{2}\cr
f \left( 5 \right) &=4\,f \left( 1 \right) f \left( 3 \right) -3\,
\left( f \left( 2 \right) \right) ^{2}\cr
f \left( 7 \right) &=6\,f \left( 1 \right) f \left( 5 \right) -15\,f
\left( 2 \right) f \left( 4 \right) +10\, \left( f \left( 3 \right)
\right) ^{2}\cr
f \left( 9 \right) &=8\,f \left( 1 \right) f \left( 7 \right) -28\,f
\left( 2 \right) f \left( 6 \right) +56\,f \left( 3 \right) f \left(
5 \right) -35\, \left( f \left( 4 \right) \right) ^{2}\cr
f \left( 11 \right) &=10\,f \left( 1 \right) f \left( 9 \right) -45\,f
\left( 2 \right) f \left( 8 \right) +120\,f \left( 3 \right) f
\left( 7 \right) -210\,f \left( 4 \right) f \left( 6 \right) +126\,
\left( f \left( 5 \right) \right) ^{2}\cr
}$$
Hmm, looks like $$f(2k+1) = \frac{1}{2}\sum_{j=1}^{2k-1} (-1)^{j+1} {2k \choose j} f(j) f(2k-j) $$
Ought to be easy to prove...
EDIT: yes, it is. By the binomial theorem
$$ \sum_{j=1}^{2k-1} \sum_{q=1}^n \sum_{r=1}^n (-1)^{j+1} {2k \choose j} q^j r^{2k-j}
= \sum_{q=1}^n \sum_{r=1}^n \left(r^{2k} + q^{2k} - (r-q)^{2k}\right)$$
and note that $$\sum_{q=1}^n \sum_{r=1}^n (r-q)^{2k} = \sum_{s=1}^n 2 (n-s) s^{2k} =
2 n f(2k) - 2 f(2k+1)$$