1
$\begingroup$

It is a classical combinatorial problem to count the number of wheels with n black or white points under rotation (action of the group $\mathbb{Z}/\mathbb{Z} n$). It can be modeled as orbits under the action of $\mathbb{Z}/\mathbb{Z} n$ on $\{0,1,...,n-1 \}$ mapping to $\{0,1 \}$ (black or white). Is the following problem considered somewhere and is there a nice closed formula? This time we have more than one wheel where $\mathbb{Z}$ acts simultaously. A model should look as follows: Let $n_1 , ... , n_l \geq 1$ be natrual numbers and let $k:=$smallest common multiple of those integers. Then $\mathbb{Z}/ \mathbb{Z}k$ acts on $\{0,1,...,n_1 -1 \} \times ... \times \{0,1,...,n_l-1 \}$ mapping to $\{0,1 \}$ (or we also might look here at more coulours than black or white). What is the number of orbits? Exact questions: With the natural action of $G=\mathbb{Z}/ \mathbb{Z}k$ on $N=\{0,1,...,n_1 -1 \} \times ... \times \{0,1,...,n_l-1 \}$, what is the number of orbits of the induced action of $G$ on $Hom(N, \{0,1 \})$ (or more generaly $Hom( N, \{0,1,...,r \})$? (The case $l=1$ corresponds to the classical case of one wheel and $l \geq 1$ should model the case of several wheels with black or white points which are rotated simultanously by the action)

$\endgroup$
  • $\begingroup$ It is difficult to follow what your exact question is, but it appears that you are asking for a reference to burnside's lemma. $\endgroup$ – JMoravitz Mar 16 '17 at 22:59
  • $\begingroup$ I added some more things, this lemma does not make it look too easy to get an explicit formula directly. $\endgroup$ – Mare Mar 16 '17 at 23:04
  • $\begingroup$ I agree with @JMoravitz that this question is a bit unclear. Are you asking about necklaces? $\endgroup$ – Brian Tung Mar 16 '17 at 23:12
  • $\begingroup$ The case of one necklace as in the link corresponds to l=1. At the end of my questions , I tried to make it mathematicaly precise. $\endgroup$ – Mare Mar 16 '17 at 23:14
1
$\begingroup$

With this problem we start by enumeration in order to get an idea of the task at hand and also obtain some backup data to help verify an eventual solution. We evidently require the cycle index of the cyclic group generated by the set of cycles or wheels that are given, which form the decomposition into disjoint cycles of a permutation, which we shall call $\alpha$. Enumeration is very simple here, we apply the single rotation to the data $k$ times (with $k=\mathrm{LCM}(n_1, n_2, \ldots, n_\ell)$) and factor all of the results into cycles. Add and divide by $k$ to get the cycle index that answers the problem. We check these by computing some singleton cycle indices (i.e. $\ell=1$) which have the well-known closed form. We get e.g.

$$Z(C_6) = 1/6\,{a_{{1}}}^{6}+1/6\,{a_{{2}}}^{3} +1/3\,{a_{{3}}}^{2}+1/3\,a_{{6}}$$

and

$$Z(C_8) = 1/8\,{a_{{1}}}^{8}+1/8\,{a_{{2}}}^{4} +1/4\,{a_{{4}}}^{2}+1/2\,a_{{8}}$$

and we see that the routine is working. We can now compute some cycle indices for groups generated by permutations that contain more than one cycle. E.g. we obtain (subscript gives lengths of cycles)

$$Z(C_{2,3}) = 1/6\,{a_{{1}}}^{5}+1/6\,a_{{2}}{a_{{1}}}^{3}+1/3\,{a_{{1}}}^{2}a_{{3}} +1/3\,a_{{2}}a_{{3}}$$

or

$$Z(C_{4,6,12}) = 1/12\,{a_{{1}}}^{22}+1/12\,{a_{{2}}}^{8}{a_{{1}}}^{6} +1/6\,{a_{{1}}}^{4}{a_{{3}}}^{6} \\+1/6\,{a_{{4}}}^{4}{a_{{2}}}^{3} +1/6\,{a_{{2}}}^{2}{a_{{3}}}^{2}{a_{{6}}}^{2} +1/3\,a_{{4}}a_{{6}}a_{{12}}$$

or finally

$$Z(C_{5,10}) = 1/10\,{a_{{1}}}^{15}+1/10\,{a_{{1}}}^{5}{a_{{2}}}^{5} +2/5\,{a_{{5}}}^{3}+2/5\,a_{{5}}a_{{10}}.$$

At this point we consult the experts and discover a simple indeed nearly trivial formula that even though it iterates over the set of rotations ($k$ iterations) does not involve factoring permutations and works with basic arithmetic. In fact on page 163 section 7.2 of Harary and Palmer's Graphical Enumeration we find the formula

$$\bbox[5px,border:2px solid #00A000]{\Large \frac{1}{k} \sum_{q=1}^k \prod_{p=1}^\ell a_{n_p/\gcd(q, n_p).}^{\gcd(q, n_p)}}$$

The proof of this is immediate. The value $q$ indicates how often we have traversed the directed arcs of the cycles of the permutation $\alpha,$ completing several traversals of individual cycles if necessary until everyone is back at the start position at the same time. The value of $\gcd(q, n_p)$ tells us what the GCD is of the current position (corresponding to $q$) and the length $n_p$ of the cycle $p.$ This has the effect of only retaining the position on $p$, discarding any contribution from eventual prior rotations that completed some number of entire traversals of cycle $p.$ This is as it should be as a cycle does not remember the history of its traversals, only the current position. The rest is simple. The cycle $p$ splits into a set of cycles (possibly a singleton). The GCD gives the number of elements in this set and hence $n_p/\gcd(q, n_p)$ their length. The sub-cycles are obtained from one another by the rotation that takes a slot to the one adjacent to it and repeat after GCD steps. Observe that when we have a single cycle of length $m$ we obtain

$$\frac{1}{m} \sum_{q=1}^m a_{m/\gcd(q,m)}^{\gcd(q,m)} = \frac{1}{m} \sum_{d|m} \sum_{q=1,\gcd(q,m)=d}^m a_{m/d}^d \\ = \frac{1}{m} \sum_{d|m} a_{m/d}^d \sum_{q=1,\gcd(q,m/d)=1}^{m/d} 1 = \frac{1}{m} \sum_{d|m} a_{m/d}^d \varphi(m/d) \\ = \frac{1}{m} \sum_{d|m} \varphi(d) a_{d}^{m/d}$$

which is the usual result. We are now ready to answer the OPs question concerning colorings with at most $N$ colors (colorings with exactly $N$ colors are obtained from these by inclusion-exclusion). By Burnside the colors must be constant on the cycles and we obtain

$$\bbox[5px,border:2px solid #00A000]{\Large \frac{1}{k} \sum_{q=1}^k \prod_{p=1}^\ell N^{\gcd(q, n_p)}.}$$

We get for three cycles of length two, three and five the closed form

$$1/30\,{N}^{10}+1/30\,{N}^{9}+1/15\,{N}^{8}+1/15\,{N}^{7} \\+2/15\,{N}^{6}+2/15\,{N}^{5}+{\frac {4\,{N}^{4}}{15}} +{\frac {4\,{N}^{3}}{15}}$$

which yields the sequence

$$1, 96, 3366, 49920, 424575, 2489760, 11218844, 41564160, \\ 132409485, 374149600, 959030754, 2267396352, \ldots$$

Similarly for cycles of length four, six and twelve we obtain

$$1/12\,{N}^{22}+1/12\,{N}^{14}+1/6\,{N}^{10} \\+1/6\,{N}^{7}+1/6\,{N}^{6}+1/3\,{N}^{3}$$

with the sequence

$$1, 351096, 2615497218, 1466038051520, 198682659520875, \\ 10968481860668136, 325818477281074596, \ldots$$

The Maple code that was used to explore the above ideas was the following.

with(combinat);
with(numtheory);

pet_autom2cycles :=
proc(src, aut)
local numa, numsubs;
local marks, pos, cycs, cpos, clen;

    numsubs := [seq(src[k]=k, k=1..nops(src))];
    numa := subs(numsubs, aut);

    marks := Array([seq(true, pos=1..nops(aut))]);

    cycs := []; pos := 1;

    while pos <= nops(aut) do
        if marks[pos] then
            clen := 0; cpos := pos;

            while marks[cpos] do
                marks[cpos] := false;
                cpos := numa[cpos];
                clen := clen+1;
            od;

            cycs := [op(cycs), clen];
        fi;

        pos := pos+1;
    od;

    return mul(a[cycs[k]], k=1..nops(cycs));
end;


pet_cycleind_gcyclicENUM :=
proc(alpha)
option remember;
local res, k, all, src, autom, q, len, rot, cyc, base;

    res := 0; k := lcm(seq(c, c in alpha));
    all := add(c, c in alpha);

    rot := []; base := 1;
    for len in alpha do
        rot :=
        [op(rot), seq(base+p, p=1..len-1), base];
        base := base + len;
    od;

    src := [seq(p, p=1..all)];
    autom := [seq(p, p=1..all)];

    for q to k do
        res := res +
        pet_autom2cycles(src, autom);

        autom :=
        [seq(autom[rot[p]], p=1..all)];
    od;

    res/k;
end;

pet_cycleind_cyclic :=
n -> add(phi(d)*a[d]^(n/d), d in divisors(n))/n;

pet_cycleind_gcyclic :=
proc(alpha)
option remember;
local k, res, len, term, inst, q;

    k := lcm(seq(c, c in alpha));
    res := 0;

    for q to k do
        term := 1;
        for len in alpha do
            inst := gcd(q, len);
            term := term * a[len/inst]^inst;
        od;

        res := res + term;
    od;

    res/k;
end;

COLORS :=
alpha ->
subs([seq(a[q]=N, q=1..add(p, p in alpha))],
     pet_cycleind_gcyclic(alpha));
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.