# How many ways to colour a tetrahedron with monochromatic triangles.

I'm trying to find how many different ways there are to colour the edges of a regular tetrahedron with n colours such that there are no monochromatic triangles.

Certainly for one triangle there must be n choose 3 ways but I'm not quite sure how to generalise this to a tetrahedron.

Any help would be much appreciated!

• is monochromatic one solid colour ie not all faces could be blue? – Ben May 21 '13 at 15:58
• You mean coloring the edges? – ccorn May 21 '13 at 16:46
• Colouring the edges yes, sorry. Monochromatic triangle would mean every edge is the same colour. Have edited the question now. – Wooster May 21 '13 at 17:44

Consider the three edges $e_1$, $e_2$, $e_3$ emanating from the top vertex $v_0$.

(i) You can color $e_1$, $e_2$, $e_3$ using three different colors in $n(n-1)(n-2)$ ways. For each of these colorings you can color the three bottom edges $e_4$, $e_5$, $e_6$ arbitrarily, but not all of them equal. This gives $n(n-1)(n-2)(n^3-n)$ admissible colorings of type (i).

(ii) You can color $e_1$, $e_2$, $e_3$ using two different colors in $3n(n-1)$ ways. The bottom edges then can be colored in $n^2(n-1)-(n-1)$ ways, where the $-(n-1)$ term again discounts the monochromatic bottom triangles. This gives $3 n(n-1)(n^2-1)(n-1)$ admissible colorings of type (ii).

(iii) You can color $e_1$, $e_2$, $e_3$ using a single color in $n$ ways. The bottom edges then can be colored in $(n-1)^3-(n-1)$ admissible ways. This gives $n(n-1)\bigl((n-1)^2-1\bigr)$ admissible colorings of type (iii).

Adding it all up we obtain $N:=n^6-4n^4+6n^2-3n$ admissible colorings.

For one triangle there are actually $n^3-n$ edge colourings, including reflections and rotations.

There are $6$ edges in a tetrahedron, $n^6$ ways to colour the edges, $4$ triangles, $n^4$ colourings with any given triangle monocromatic, $6$ pairs of triangles, $n^2$ colourings with any given pair of triangles both monochromatic, 4 ways to pick $3$ triangles, $n$ colourings with $3$ triangles, hence all triangles, monochromatic, $1$ way to pick $4$ triangles and $n$ colourings with $4$ triangles monochromatic.

The number of $n$-colourings without monochromatic triangles is then $n^6-4n^4+6n^2-3n$.

• I wish I could upvote this twice; it's perfect. – MJD May 22 '13 at 0:59
• @MJD: I tried several times, but I didn't arrive at understanding this answer, even though the result is correct. That's why I posted my own. Can you shed some light on it? – Christian Blatter May 22 '13 at 16:35
• I agree that it is highly abbreviated. I had to read carefully before I understood. Does it help if I explain that it's an application of the inclusion-exclusion formula, or should I provide more detail? – MJD May 22 '13 at 16:50