For a triangle, there can be 3, 2 or 1 color(s) making up the figure.
There are C(n,3) ways of choosing 3 colors, but any set of three can be set in either clockwise or counterclockwise order, so the threecolor triangles contribute 2*C(n,3) = (n^33*n^2+2*n)/3 to the total.
For two colors, there are n ways of choosing the one that occurs on two sides, and (n1) ways left of choosing the remaining side, for n^2n ways.
There are n ways of choosing a onecolor triangle.
Adding the terms and simplifying we get (n^3+2n)/3
For squares there are P(n,4) possible sequences of four colors, but since rotations do not count separately, that has to be divided by 4. So fourcolor squares account for P(n,4)/4 of the total.
With a threecolor square, there are two possibilities: the duplicated color is on two adjacent sides or two opposite sides. If the former, there are n ways of choosing the duplicated color, n1 ways of choosing the one clockwise from it and n2 ways of choosing the one remaining. If the duplicated color is on opposite sides, there's still n ways of choosing it, but only C(n1,2) = (n1)(n2)/2 ways of choosing the other two, as clockwise or counterclockwise doesn't matter.
With only two colors, they can be either 3 of one and one of another, with n(n1) ways of choosing first the 3 and then the 1 (or the other way around if you like), or there can be two of each, in which case there are C(n,2) ways of choosing the two, but then this must be multiplied by two to reflect the fact that the like colors can be adjacent or opposite.
Of course there are still n ways of choosing a singlecolor square.
That makes P(n,4)/4 + (3/2)(n(n1)(n2)) + 2n(n1) + n, or
n(n1)(n2)(n3)/4 + (3/2)(n(n1)(n2)) + 2n(n1) + n.
That leaves only simplification.

Posted by Charlie
on 20040910 15:08:51 