# Two combinatorics problems

I have two problems I can't cope with:

Problem 1. How many are ways to divide $n$-convex polygon into triangles using non-intersecting diagonals?

Problem 2. We have $3n$ different balls and $n$ different boxes. How many are ways to put all balls in boxes and in every box there is at least two balls?

I have no ideas for first one. I'm wondering if it wasn't easier, in second problem, to count situations in which there exists box with one or zero balls and subtract them from $n^{3n}$. But I don't know how to count them.

-
1 is basically Catalan numbers –  Henry Aug 9 '12 at 10:54
So according to wiki the answer for Problem1. is ${2(n-2)\choose n-2}$, but unfortunately I completely don't know why. I think to solve this problem I should give an explanation that number if these ways satisfy reccurence for Catalan numbers (shifted), but I don't know how to substantiate it. –  ray Aug 9 '12 at 12:40
The number of ways to put $m$ different balls into $n$ different boxes so each box has at least one ball is the number of onto functions from an $m$-set to an $n$-set. It's counted by the Stirling numbers, q.v., and you use inclusion-exclusion to get a formula. The two ball problem should be similar, but more complicated; once you understand how the onto functions are counted, you'll be on your way. –  Gerry Myerson Aug 9 '12 at 12:49
You should post Problem 2 as a separate question. –  Austin Mohr Aug 14 '12 at 6:16

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<n$ 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.

-
Unfortunately it isn't that simple. Both balls and boxes are distinguishable. I thought I wrote it: "different balls and n different boxes". Forgive me if I wasn't enough specific, I still learn English. –  ray Aug 9 '12 at 11:26
@ray: What you wrote is fine, though in problems like this it’s always best to be extra specific, just in case; still, I should have realized what you meant. I’ll think about it a bit more. –  Brian M. Scott Aug 9 '12 at 11:33
Your $(2)$ tantalizingly looks like a convolution... –  Guess who it is. Aug 14 '12 at 10:39