Using Burnside's Lemma; understanding the intuition and theory

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.

For the sake of brevity and by way of an incentive to learn more about this wonderful theory, here is a solution using the Polya Enumeration Theorem. All we need here is to calculate the cycle index $Z(G)$ of the symmetry group $G$ of the edges of a square, substitute our $N$ colors into the cycle index and extract coefficients. We get for the first question that the answer is $${N\choose 4}[C_1 C_2 C_3 C_4]Z(G)(C_1+C_2+C_3+C_4)$$ and for the second question, $$Z(G)(C_1+C_2+\cdots+C_N)_{C_1=1, C_2=1, \ldots C_N=1}.$$ Let us now compute the cycle index by enumerating the permutations of $G$. There is the identity, which contributes $$a_1^4.$$ There are the rotations by $90$ degrees and $270$ degrees which together contribute $$2 a_4.$$ The rotation by $180$ degrees contributes $$a_2^2.$$ The two reflections about a diagonal contribute $$2 a_2^2$$ and the reflections about horizontal / vertical axes passing through the center of the square contribute $$2 a_1^2 a_2.$$ Summing these contributions we obtain that $$Z(G) = \frac{1}{8} \left(a_1^4 + 2a_4 + 3 a_2^2 + 2 a_1^2 a_2\right).$$ Hence the substituted cycle index becomes $$Z(G)(C_1+C_2+\cdots+C_N) = \frac{1}{8} \left((C_1+\cdots+C_N)^4 + 2(C_1^4+\cdots+C_N^4) \\+ 3 (C_1^2+\cdots+C_N^2)^2 + 2 (C_1+\cdots+C_N)^2 (C_1^2+\cdots+C_N^2)\right).$$ In answering the first question (no repeated colors) we see that all terms in the sum except the first use a color at least twice (a phenomenon that generalizes to generic permutation groups), so we have $${N\choose 4}[C_1 C_2 C_3 C_4] Z(G) = {N\choose 4}[C_1 C_2 C_3 C_4] \frac{1}{8} (C_1+C_2+C_3+C_4)^4.$$ Expanding the power we get $$(C_1+C_2+C_3+C_4) \times (C_1+C_2+C_3+C_4) \\ \times (C_1+C_2+C_3+C_4) \times (C_1+C_2+C_3+C_4).$$ It now becomes evident that there are $24$ ways to obtain the product $C_1 C_2 C_3 C_4,$ for a final answer of $${N\choose 4} \frac{1}{8} \times 24 = 3{N\choose 4}.$$ We obtain the answer to the second question by setting $C_1=C_2=\cdots=C_N=1$ in the substituted cycle index, for a result of $$\frac{1}{8} \left(N^4+2N+3N^2+2N^3\right) = \frac{1}{8} \left(N^4+2N^3+3N^2+2N\right).$$ This is sequence A002817 from the OEIS.

This MSE link points to a chain of similar calculations.