For the first problem you need to look at Catalan numbers.
Added: Let $t_n$ be the number of triangulations of an $(n+2)$-gon for $n\ge 2$. Clearly $t_1=1$ and $t_2=2$; we’ll worry about $t_0$ when we need to. Now let $P$ be an $(n+2)$-gon for some $n>2$, say. Call one edge of $P$ the bottom edge, and label its vertices $A$ and $B$. Suppose now that I have a triangulation $T$ of $P$. There is a unique vertex $C$ of $P$ such that $\triangle ABC$ is one of the triangles of $T$. Think of $P$ now as composed of three polygons: the triangle $\triangle ABC$ and the two polygons on either side of it. Let $L$ be the polygon to the left of the triangle, and $R$ the polygon to the right of the triangle. The rather sloppy figure below shows two examples. (In the second $L$ is degenerate: it’s just the $2$-gon $AC$.)

Altogether the polygons $L$ and $R$ have $n+1$ of the original $n+2$ sides of $P$, plus the new edges $AC$ and $BC$, for a total of $n+3$ sides. Let $\ell$ and $r$ be the numbers of sides of the polygons $L$ and $R$, respectively, so that $\ell+r=n+3$. There are $t_{\ell-2}$ ways to triangulate $L$ and $t_{r-2}$ ways to triangulate $R$, so there are altogether $t_{\ell-2}t_{r-2}$ triangulations of $P$ that include the triangle $\triangle ABC$.
As $C$ moves around $P$ from just left of $A$ to just right of $B$, $\ell$ runs from $2$ up to $n+1$, and $r$ runs from $n+1$ down to $2$. Thus, $\ell-2$ runs from $0$ up to $n-1$, and $r$ runs from $n-1$ down to $0$. Recall that $\ell+r=n+3$, so $(\ell-2)+(r-2)=n-1$ and we can write $t_n=\sum_{k=0}^{n-1}t_kt_{n-1-k}\;,$ provided that we set $t_0=1$. This is perhaps easier to read with the index shifted: $t_{n+1}=\sum_{k=0}^nt_kt_{n-k}\;.\tag{1}$
But it’s well-known that the Catalan numbers $C_n$ satisfy the recurrence $C_{n+1}=\sum_{k=0}^nC_kC_{n-k}$ with initial condition $C_0=1$, so $t_n=C_n$ for all $n\in\Bbb N$.
Added2: For the second problem, the number of ways to put $m$ distinguishable marbles into $b$ distinguishable boxes in such a way that each box receives at least one marble is $\left\{m\atop b\right\}b!$, where $\left\{m\atop b\right\}$ is a Stirling number of the second kind. Now consider the original problem. If $0\le k and any fixed set of $k$ of the boxes there are $\binom{3n}kk!$ ways to put exactly one ball into each of the $k$ boxes and $\left\{3n-k\atop n-k\right\}(n-k)!$ ways to assign the remaining $3n-k$ balls to the remaining $n-k$ boxes in such a way that each box receives at least one ball. Thus, by a standard inclusion-exclusion argument the desired number is
$\sum_{k=0}^{n-1}(-1)^k\binom{n}k\binom{3n}kk!\left\{3n-k\atop n-k\right\}(n-k)! =n!\sum_{k=0}^{n-1}(-1)^k\binom{3n}k\left\{3n-k\atop n-k\right\}\;.\tag{2}$
Unfortunately, I’ve not so far been able to obtain a closed form for $(2)$. One can get rid of the Stirling number at the cost of introducing a double summation, which can then be manipulated in a variety of ways, e.g.
$\begin{align*} n!\sum_{k=0}^{n-1}&(-1)^k\binom{3n}k\left\{3n-k\atop n-k\right\}\\ &=n!\sum_{k=0}^{n-1}(-1)^k\binom{3n}k\frac1{(n-k)!}\sum_{i=0}^{n-k}(-1)^{n-k-i}\binom{n-k}ii^{3n-k}\\ &=n!\sum_{k=0}^{n-1}\sum_{i=0}^{n-k}\frac{(-1)^{n-i}}{(n-k)!}\binom{3n}k\binom{n-k}ii^{3n-k}\\ &=n!\sum_{i=0}^n(-1)^{n-i}i^{2n}\sum_{k=0}^{n-i}\frac{i^{n-k}}{(n-k)!}\binom{3n}k\binom{n-k}i\\ &=n!\sum_{i=0}^n(-1)^{n-i}i^{2n}\sum_{k=i}^n\frac{i^k}{k!}\binom{3n}{n-k}\binom{k}i \end{align*}$
and various further transformations, but in all forms I found the inner summation pretty intractable. Perhaps someone with more experience with such monstrosities can do better.