If I’ve understood correctly the way you’re using the term $n$- _valent tree_ , the number of $4$-valent rooted plane trees with $n$ internal nodes is
$$\frac1{2n+1}\binom{3n}n\;;$$
this is OEIS A001764.
More generally, let $a_n^{(m)}$ be the number of $(m+1)$-valent rooted plane trees with $n$ internal vertices; these numbers satisfy the recurrence
$$a_n^{(m)}=[n=0]+\sum_{k_1+\ldots+k_m}a_{k_1}^{(m)}a_{k_2}^{(m)}\ldots a_{k_m}^{(m)}\;,$$
where the first term is an Iverson bracket. **Example** $\mathbf5$ in **Section** $\mathbf{7.5}$ of Graham, Knuth, and Patashnik, _Concrete Mathematics_ , shows that the solution to this recurrence is
$$a_n^{(m)}=\frac1{mn+1}\binom{mn+1}n=\frac1{(m-1)n+1}\binom{mn}n\;.\tag{1}$$
For the $3$-valent case we have $m=2$, so that $(1)$ does indeed yield the Catalan numbers.
The OEIS entry has many more applications/interpretations of this sequence.