Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
    
I wish I could upvote this twice; it's perfect. –  MJD May 22 '13 at 0:59
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.