Since we are painting the edges of squares, we assume that these four colorings are all considered the same, and should not be counted separately:
(It should be clear that painting triangular wedges is the same as painting edges, since there is a natural bijection between wedges and edges.)
It's not completely clear in the question, but we should probably also assume that the squares can be flipped over, so that these two colorings should also be considered the same:
That is the crucial question that decides whether to use $C_4$ or $D_4$: Are those two different colorings, or are they the same coloring? If they are the same coloring, then we say we are allowed to flip over the square, and flipping becomes part of the group we consider in applying the theorem. If they are different colorings, then reflections are not part of the group.
To apply the Cauchy-Frobenius-Burnside-Redfield-Pólya lemma, we begin by observing that our squares have the symmetry group $D_4$, which includes the four reflections. Then we count the number of colorings that are fixed points of a coloring under action by each element of $D_4$. Let $x$ be such an element, and suppose that $x$'s action on the square partitions the set of edges into $o(x)$ orbits. Then for a coloring to be fixed by $x$, all the edges in each orbit must be the same color. If there are $N$ different colors, then $N^{o(x)}$ are left fixed by the action of $x$.
The 8 elements of $D_4$ can be classified as follows:
- 2 orthogonal reflections, which divide the edges into 3 orbits ($2N^3$)
(For example, reflecting the square horizontally puts the left and right edges in one orbit, the top edge in a second orbit, and the bottom edge in a third orbit)
- 2 diagonal reflections, which divide the edges into 2 orbits ($2N^2$)
(For example, reflecting the square on the topleft-bottomright axis puts the top and left edges in one orbit, the bottom and right edges in the other)
- 2 quarter-turns, which put all the edges in a single orbit ($2N$)
- the half-turn, which divides the edges into 2 orbits ($N^2$)
- the identity, which leaves each edge in its own orbits ($N^4$)
The number of colorings with $N$ colors is the sum of the terms for each of these, divided by 8, the order of the symmetry group. Adding up the contributions from these we get $$\chi_{D_4}(N) = \frac18(N^4+2N^3+3N^2+2N).$$
This formula gives $\chi_{D_4}(0)=0, \chi_{D_4}(1)=1$ as we would hope. Hand enumeration of the $N=2$ case quickly gives 6 different colorings (four red edges; three red edges; two opposite red edges; two adjacent red edges; one red edge; no red edges) which agrees with the formula.
If reflections are not permitted, we delete the corresponding terms ($2N^3 + 2N^2$) from the enumeration, and divide by 4 instead of 8, as the symmetry group now has 4 elements instead of 8, obtaining instead $$\chi_{C_4}(N) = \frac14(N^4+N^2+2N).$$
This happens to have the same value as $\chi_{D_4}$ for $N<3$; this is because every coloring of the square with fewer than 3 colors has a reflection symmetry. The simplest coloring that has no reflection symmetry requires 3 colors:
You asked “I am to include rotations?” The answer is probably yes, or the question would not have specified the edges of a square, which has a natural rotational symmetry. But suppose you wanted to consider to be different colorings. Then rotations of a coloring are not allowed, and the group you consider should be one that omits the rotation elements. In the extreme case, we can consider every coloring different, and then the group is the trivial group, and the same analysis says to omit all the terms except the $N^4$ contributed by the identity element, and we get $$\chi_{C_1}(N) = N^4$$ which is indeed the correct number of colorings.
Best Answer
For the triangle case, the symmetry group will still be $D_3$ (of six elements), and not of that a hexagon. The reason is you cannot bring the vertex to an edge. With that in mind, we consider $D_3$ acting on $X$, all possible colorings of vertices and edges with $n$ colors, so $|X| = n^6$ (before considering symmetries). Applying Burnside's theorem, we have the number of orbits $|X/D_3|$ to be $$|X/D_3| = \frac{1}{|D_3|} \sum_{g\in D_3} |Fix(g)|,$$ where $Fix(g)$ is set of colorings fixed by $g$. Now we analyze this a bit, with $D_3 = \{1,r,r^2 , f_1,f_2,f_3\}$, where $r^i$ are the rotations and $f_j$ are the flips. Then
$|Fix(1)| = n^6$;
$|Fix(r)| = |Fix(r^2)| = n^2$ (one color choice for the vertices, and another color choice for the edges);
$|Fix(f_j)|=n^4$ (one color choice for the vertex where the line of symmetry goes through, one color choice for the edge where the line of symmetry goes across, one color choice for the pair of vertices across the line of symmetry, and one color choice for the pair of edges across the line of symmetry).
Hence $|X/D_3| = \frac{1}{6}(n^6+ 2n^2 + 3n^4)=\frac{1}{6}n^2(n^4+2+3n^2)=\frac{1}{6}n^2(n^2+2)(n^2+1)$. Here I factor it to see that indeed we get an integer as $n^2(n^2+2)(n^2+1)$ is a multiple of 6.
For the square case you similarly consider the symmetry of a square $D_4$ with eight element, and not of an octagon for the same reason that we cannot bring a vertex onto an edge.