Suppose we have both a group $G$ of permutations of $D$ and another group $H$ of permutations of $C$. We assume also that there are at least two colours, that is, $\# C > 1$ - otherwise there's only one colouring so nothing to count. Two colourings $f_{1},f_{2}\in C^D$ are said to be $H^G$-equivalent if there are permutations $g \in G$ and $h \in H$ such that $f_{1}(g(d))= h (f_{2}(d)), \quad d \in D.$That is, we are allowed not only to permute the elements of $D$ by some element of $G$ but also to permute the colours by some element of $H$. It takes a routine check to see that this relation is indeed an equivalence relation. We denote its quotient space by $C^D/H^G$. Equivalently, $C^{D}/H^G$ can be seen as the set of orbits in $C^D$ under the following right group action of the direct product $G \times H$: $(g,h)*f = h^{-1} \circ f \circ g, \quad (g,h) \in G\times H.$Note that this (and, in fact, any) group action can be seen as a homomorphism of groups: $\begin{align} \phi:G\times H &\to \text{Sym}(C^D) \\ (g,h) &\mapsto \pi_{(g,h)} : f \mapsto (g,h)*f, \quad f\in C^D \end{align}$($\pi_{(g,h)}$ is indeed bijective - one can check that its inverse is the obvious choice $\pi_{(g^{-1}, h^{-1})}$). The fact that $\phi$ is a homomorphism is a direct consequence of the group action axioms. The group $\text{Im}(\phi)$ is what Harary ^[2] calls the *power group* of $H$ and $G$, denoted $H^G$. Moreover, we claim that $\phi$ is injective, implying that $H^G$ is isomorphic to $G \times H$. To prove injectivity, suppose $h_{1} \circ f \circ g_1=h_{2} \circ f \circ g_{2}, \quad f\in C^{D}, g_{1},g_{2}\in G, h_{1},h_{2}\in H\tag{1}$(since $h_{i}$ is arbitrary, we can replace $h_{i}$ with $h_{i}^{-1}$ without loss of generality). If $g_{1}\neq g_{2}$ then there exists $d\in D$ such that $g_{1}(d)\neq g_{2}(d)$. Now either $h_{1}=h_{2}$ or $h_{1}\neq h_{2}$. If $h_{1}=h_{2}$ then the we can we choose a colouring $f\in C^D$ so that $g_{1}(d),g_{2}(d)$ are different colours, that is, $f(g_{1}(d))\neq f(g_{2}(d))$. But $(1)$ yields $f(g_{1}(d))) = f(g_{1}(d))$ contradicting our choice of $f\in C^D$. On the other hand, if $h_{1} \neq h_{2}$ then there exists a colour $c\in C$ such that $h_{1}(c) \neq h_{2}(c)$. Choose a colouring $f\in C^D$ such that $f(g_{1}(d))=c=f(g_{2}(d))$ then $h_{1}(f(g_{1}(d)))\neq h_{2}(f(g_{1}(d)))$ contradicting $(1)$. So we must have $g_{1}=g_{2}$. Now $(1)$ reduces to $h_{1}\circ f=h_{2}\circ f$ for all $f\in C^D$ which gives $h_{1}=h_{2}$ since otherwise we can choose $f\in C^D$ such that $h_{1}(f(d))\neq h_{2}(f(d))$ for all $d\in D$. Observe that $H^G$-equivalent functions may have different weights if we obtain the weights of $f\in C^D$ from the weights of colours $c\in C$ like before. Nonetheless, we assign each function a weight such that $H^G$-equivalent functions have the weight. Then, similar to [[Pólya's Enumeration Theorem]], by applying Burnside's lemma we get $\sum_{F\in C^{D}\text{/}H^{G}}W(F) =\frac{1}{\#G \cdot \# H} \sum_{g\in G} \sum_{h\in H} \sum_{f\in \text{Fix}((g,h))} W(f).$ Using this, De Bruijn ^[1, Theorem 5.4] proves the following formula for the number of orbits in $C^{D}/H^G$: $\# (C^D/H^{G})=\left.Z_G\left(\frac{\partial}{\partial z_1}, \frac{\partial}{\partial z_2}, \frac{\partial}{\partial z_3}, \cdots\right) Z_H\left(e^{z_1+z_2+z_3+\cdots}, e^{2\left(z_2+z_4+z_6+\cdots\right)}, e^{3\left(z_3+z_6+z_9+\cdots\right)}, \ldots\right)\right\rvert_{z_{i=0}}$ For example, let $n$ be the number of two-coloured necklaces of four beads, where we may also interchange the two colours to get an equivalent colouring. Thus $Z_G=\frac{1}{4}\left(z_1^4+z_2^2+2 z_4\right)$ and $Z_H=\frac{1}{2}\left(z_1^2+z_2\right)$. Hence $\begin{aligned} n & =\left.\frac{1}{4} \cdot \frac{1}{2}\left(\frac{\partial^4}{\partial z_1^4}+\frac{\partial^2}{\partial z_2^2}+2 \frac{\partial}{\partial z_4}\right)\left(e^{2\left(z_1+z_2+z_3+\cdots\right)}+e^{2\left(z_2+z_4+z_6+\cdots\right)}\right)\right|_{z_i=0} \\ & =\left.\frac{1}{8}\left(\frac{\partial^4}{\partial z_1^4}+\frac{\partial^2}{\partial z_2^2}+2 \frac{\partial}{\partial z_4}\right)\left(\frac{\left(2 z_1\right)^4}{4!}+\frac{\left(2 z_2\right)^2}{2!}+\frac{2 z_4}{1!}+\frac{\left(2 z_2\right)^4}{4!}+\frac{2 z_4}{1!}\right)\right|_{z_i=0} \\ & =\frac{1}{8}(16+4+4+4+4) \\ & =4. \end{aligned}$ Harary provides several applications of this theorem to graphical enumeration (see ^[3]). # References ^[1]. N. G. de Bruijn. Pólya’s theory of counting, **Theorem 5.4.** In E. F. Beckenbach, editor, Applied Combinatorial Mathematics, pages 144–184. Wiley, New York, N.Y., 1964. ^[2]. Frank Harary and Ed Palmer. The power group enumeration theorem. Journal of Combinatorial Theory, 1(2):157–173, 1966.