Counting $n$ disjoint triangles in a regular $3n$-gon I have been practising for a retake on combinatorics (and graph theory) and I am stuck on the following question:

Suppose we have a regular $3n$-gon, numbered $0$ through $3n-1$. Suppose $P_n$ counts the number of ways we can form  precisely $n$ triangles that do not share any vertices.
  We define $p_0=1$, we realise $p_1=1$ since a triangle is already a triangle. Furthermore, $p_2=3$, $p_3=12$. 

Below are two of the ways we can draw triangles for $n=3$, so a regular $9$-gon.

Prove the following result holds:

$$ p_n = \sum_{a+b+c=n-1}p_a p_b p_c$$
   Hint: Observe that the triplet that contains zero, must be of the form $\{0, 3x+1, 3y+2 \}$.

In the hint I realise that $x,y \in \{0, 1, \dots n-1 \}$, indeed this is simply the statement that the three points do not overlap, or am I missing something here? I am not sure how the sum follows, I don't see how is being counted.  I feel like we can decompose this sum into the product of the form:
$$ \left(\sum_{a=0}^{\dots} p_{a} \right) \left(\sum_{b=0}^{\dots} p_{b} \right) \left(\sum_{c=0}^{\dots} p_{c} \right)  $$
 A: I am inferring from the diagrams and the values of $p_n$ given that the partition must be into non-overlapping triangles...apologies if this is not the case. With this assumption, consider a partition $P$ and let $\{0,x,x+y\}$ be the triangle of $P$ containing $0$. Since the triangles must be non-overlapping, every other triangle in $P$ must have all of its vertices in one of these three sets:


*

*$\{1 \ldots x-1\}$

*$\{x+1 \ldots x+y-1\}$

*$\{x+y+1 \ldots 3n-1\}$
Note that for some values of $x,y$ one or more of these sets may be empty. Conversely, each of these three subsets must be either empty or fully covered by triangles in $P$, which implies in particular that each must have size divisible by 3. Let the cardinality of the first be $3a$, the second $3b$, and the third $3c$, from which it is not hard to see that $a+b+c=n-1$.
The triangles in $P$ whose vertices are contained in the first set are in 1-to-1 correspondence with the partitions of a $3a$-gon, so there are $p_a$ such partitions. Similarly there are $p_b$ and $p_c$ possible ways to pick the triangles of $P$ whose vertices are contained in the second and third sets, respectively. So the number of partitions on the $3n$-gon containing the triangle $\{0,x,x+y\}$ is exactly $p_ap_bp_c$. Varying $x$ and $y$ over all legal values gives the claimed summation.
