In this note, we give two simple bijections between compositions over groups and colorings of cycles. These bijections immediately imply the formulas for the number of \(m\)-compositions over a finite group.
Throughout this note, \(G\) denotes a finite additive group with \(r\ge 2\) elements, and 0 denotes the identity element of \(G\). We follow the standard notation in the literature and use \(+\) for the group operation keeping in mind that \(+\) may not be commutative. An \(m\)-composition of \(g\in G\) is a sequence \(g_1,g_2,\ldots,g_m\) of nonzero elements from \(G\) such that \(g_1+g_2+\cdots+g_m=g\). Since \(G\) may not be abelian, the addition is performed from left to right. Let \(c_m(g)\) be the number of \(m\)-compositions of \(g\). The following formulas are known [5, 3, 4]:
We remark that these were first established by Muratović-Ribić and Wang [5], for the case when \(G\) is a finite field. Gao, MacFie and Wang [3] later extended these findings to all finite abelian groups. Subsequently, Gao and Zhang [4] generalized the results to all finite groups using somewhat indirect correspondences between compositions. In this note, we rederive (1) and (2). Our bijections provide much shorter proofs of these two formulas by establishing a connection between the seemingly unrelated combinatorial topics of compositions and graph colorings.
Let \({\cal C}_m\) denote the cycle graph with \(m\) vertices labeled clockwise as \(1,2,\ldots,m\). We include \({\cal C}_2\) here and note that the chromatic polynomial of \({\cal C}_2\) is the same as that of the path graph with two vertices. A \(G\)-coloring of \({\cal C}_m\) is a mapping \(c:\{1,2,\ldots,m\}\mapsto G\) such that \(c(j)\ne c(j+1)\) for each \(1\le j\le m-1\) and \(c(1)\ne c(m)\). It is well-known (see, e.g. [1, Ex. 14.7.5], [2, Ch. 8]) that the number of \(G\)-colorings of \({\cal C}_m\) is given by the chromatic polynomial
Thus, the formulas (1) and (2) can be rewritten as
The above formulas follow immediately from the following bijections.
Theorem 2.1. Let \(g_1,g_2,\ldots,g_m\) be a sequence of nonzero elements of \(G\). Define \(s_0=0\) and
(a) For each \(h\in G\), the mapping
is a bijection between \(m\)-compositions of \(0\) and \(G\)-colorings of \({\cal C}_m\) in which vertex \(m\) receives color \(h\).
(b) For each \(g\in G\setminus\{0\}\) and each \(h\in G\), the mapping
is a bijection between \(m\)-compositions of \(g\) and \(G\)-colorings of \({\cal C}_{m+1}\) in which vertex \(1\) receives color \(h\) and vertex \(m+1\) receives color \(h+g\).
Proof. We first note \(s_j=s_{j-1}+g_j\ne s_{j-1}\) for each \(1\le j\le m\). For \(h\in G\) we shall use \(-h\) to denote the inverse of \(h\). We have
We note that only the associativity of the group operation is used in establishing (5).
(a) For each \(m\)-composition \((g_1,g_2,\ldots,g_m)\) of 0, we have \(s_m=0\). Thus, \(h+s_m=h\ne h+s_1\) and \(h+s_j\ne h+s_{j-1}\) for all \(1\le j\le m\). It follows that \((h+s_1,h+s_2,\ldots,h+s_{m-1},h+s_m)\) is a \(G\)-coloring of \({\cal C}_m\). In all of these colorings vertex \(m\) receives color \(h\).
On the other hand, let \((c_1,c_2,\ldots,c_m)\) be a \(G\)-coloring of \({\cal C}_m\) with \(c_m=h\). We show that there is a unique \(m\)-composition \((g_1,g_2,\ldots,g_m)\) of 0 such that \(\phi(g_1,g_2,\ldots,g_m)=(c_1,c_2,\ldots,c_m)\), that is,
From (6) and \(c_m=h\), we obtain \(s_m=0\) and \(s_j=-h+c_j,\ 1\le j\le m\). It follows that
Since \(c_1\ne c_m\) and \(c_j\ne c_{j-1}\) for each \(2\le j\le m\), we have \(g_j\ne 0\) for all \(1\le j\le m\). Thus, \((g_1,g_2,\ldots,g_m)\) is the unique \(m\)-composition of 0 satisfying \(\phi(g_1,g_2,\ldots,g_m)=(c_1,c_2,\ldots,c_m)\). This completes the proof of (a).
(b) The proof of part (b) is similar to that of part (a). Since \(s_1=g_1\ne 0\), \(s_m=g\ne 0\), it is clear that \((h,h+s_1,h+s_2,\ldots,h+s_{m-1},h+s_m)\) is a \(G\)-coloring of \({\cal C}_{m+1}\) such that vertex 1 receives color \(h\) and vertex \(m+1\) receives color \(h+g\).
Now we show that \(\psi\) is invertible. For each \(G\)-coloring \((c_1,c_2,\ldots,c_{m+1})\) of \({\cal C}_{m+1}\) with \(c_1=h\) and \(c_{m+1}=h+g\), we want to find the unique \(m\)-composition \((g_1,g_2,\ldots,g_m)\) of \(g\) such that
The above equations give
Thus (noting that \(s_0=0\)),
This completes the proof of (b). \(\square\)
In Theorem 2.1(a), each \(h\in G\) gives a different \(G\)-coloring of \({\cal C}_m\), and therefore \(P({\cal C}_m,r)=rc_m(0)\), which is (3).
For \(a,b\in G\) with \(b\ne a\), let \({\cal P}_{a,b}({\cal C}_{m+1})\) denote the set of \(G\)-colorings of \({\cal C}_{m+1}\) such that vertex 1 receives color \(a\) and vertex \(m+1\) receives color \(b\). We note that the permutation \((a,a’)(b,b’)\) (which swaps \(a\) with \(a’\) and \(b\) with \(b’\)) is a bijection between \({\cal P}_{a,b}({\cal C}_{m+1})\) and \({\cal P}_{a’,b’}({\cal C}_{m+1})\). This is because a proper coloring of \({\cal C}_{m+1}\) only requires that adjacent vertices receive different colors, which is independent of the group operation. Thus
Since there are \(r(r-1)\) choices of \((a,b)\) with \(a,b\in G\) and \(a\ne b\), it follows that, for any \(h\in G\) and \(g\in G\setminus\{0\}\),
It follows from Theorem 2.1(b) that, for each \(g\in G\setminus\{0\}\),
It would be interesting to see whether the ideas presented here and the unexpected connection to graph colorings have further applications in the theory of compositions over groups.