1
$\begingroup$

I've found a problem which gives 3 red beads, 3 green beads, and 3 blue beads. It asks how many arrangements there are of the 3 sets of beads on a necklace, given that the conditions that all 9 beads must be used, no 2 beads that are next to each other can be the same color, and any two arrangements that can be rotated/reflected to match each other are identical.

I'm trying to start by ignoring the 2 consecutive beads cannot be the same color condition, and finding the number of ways to arrange the beads without it. I know that if all 9 beads were distinct, then the answer would just be 9!/9, or 8!. I've tried dividing it by $3!^3$, since there are $3!$ ways to organize each 3 beads of the same color, but that gives a decimal which shouldn't be the answer. I'm not sure how to proceed from here, and then account for the reflections. Any ideas?

$\endgroup$
1

1 Answer 1

1
$\begingroup$

Let me contribute some material here to help you get started and initiate additional research. I must ask you to consult two previous posts, however, where essentially 100% of the answer to your question is already documented. These are

Using the notation from the above, for the rotations we must replace the count $P_d(k)$ by a generating function. By construction the $P_d(k)$ arise for permutations with $d$ cycles of length $n/d$ which owing to the coloring being proper requires a properly colored cycle of length $d$ call it $\beta$ with at most the given number of colors (the $d$ cycles are adjacent and monochrome by Burnside). This cycle is repeated around the bracelet. Therefore we have solved the problem if we can construct a generating function by colors of properly colored cycles, where symmetries are not taken into account. This is done recursively using a memoized algorithm that classifies generating functions of paths by the first and last color of the paths they represent, which are then used to build cycles. Now if a color appears on one of these cycles we must replace its variable $C$ in the generating function by $C^{n/d}$ because the cycle $\beta$ induces the colors of the $d$ cycles which make up the permutation. With the reflections which only contribute when $n$ is even where the axis of reflection passes through opposite vertices we need a generating function of properly colored paths with no symmetry and we take one of these to constitute the colors on one side and induce the ones on the other. This means we replace each variable from the generating function by its square, compensating for the two colors which appear on the fixed points, which contribute only once. This is basically all. Here is the generating function for proper non-isomorphic colorings of a nine-bracelet using at most three colors as requested by OP:

$${C_{{1}}}^{4}{C_{{2}}}^{4}C_{{3}}+3\,{C_{{1}}}^{4}{C_{{2} }}^{3}{C_{{3}}}^{2}+3\,{C_{{1}}}^{4}{C_{{2}}}^{2}{C_{{3}} }^{3}+{C_{{1}}}^{4}C_{{2}}{C_{{3}}}^{4}\\+3\,{C_{{1}}}^{3}{ C_{{2}}}^{4}{C_{{3}}}^{2}+8\,{C_{{1}}}^{3}{C_{{3}}}^{3}{C _{{2}}}^{3}+3\,{C_{{1}}}^{3}{C_{{2}}}^{2}{C_{{3}}}^{4}+3 \,{C_{{1}}}^{2}{C_{{2}}}^{4}{C_{{3}}}^{3}\\+3\,{C_{{1}}}^{2 }{C_{{2}}}^{3}{C_{{3}}}^{4}+C_{{1}}{C_{{2}}}^{4}{C_{{3}}} ^{4}.$$

Therefore the answer to the query is

$$\bbox[5px,border:2px solid #00A000]{8.}$$

Here is an excerpt for the case of a twelve-bracelet with at most $5$ colors:

$$\ldots +16\,C_{{1}}C_{{2}}{C_{{3}}}^{6} {C_{{4}}}^{2}{C_{{5}}}^{2}+10\,C_{{1}}C_{{2}}{C_{{3}}}^{6 }C_{{4}}{C_{{5}}}^{3}+3\,C_{{1}}C_{{2}}{C_{{3}}}^{6}{C_{{ 5}}}^{4}\\+15\,C_{{1}}C_{{2}}{C_{{3}}}^{5}{C_{{4}}}^{5}+153 \,C_{{1}}C_{{2}}{C_{{3}}}^{5}{C_{{4}}}^{4}C_{{5}}+408\,C_ {{1}}C_{{2}}{C_{{3}}}^{5}{C_{{4}}}^{3}{C_{{5}}}^{2}\\+408\, C_{{1}}C_{{2}}{C_{{3}}}^{5}{C_{{4}}}^{2}{C_{{5}}}^{3}+153 \,C_{{1}}C_{{2}}{C_{{3}}}^{5}C_{{4}}{C_{{5}}}^{4}+15\,C_{ {1}}C_{{2}}{C_{{3}}}^{5}{C_{{5}}}^{5}\\+3\,C_{{1}}C_{{2}}{C _{{3}}}^{4}{C_{{4}}}^{6}+153\,C_{{1}}C_{{2}}{C_{{3}}}^{4} {C_{{4}}}^{5}C_{{5}}+1014\,C_{{1}}C_{{2}}{C_{{3}}}^{4}{C_ {{4}}}^{4}{C_{{5}}}^{2}\\+1783\,C_{{1}}C_{{2}}{C_{{3}}}^{4} {C_{{4}}}^{3}{C_{{5}}}^{3}+\ldots$$

The Maple code for this is shown below. It includes a very basic enumeration routine that confirmed the results from Burnside for all examples that were examined.

with(combinat);
with(numtheory);

P := (d,k) -> (k-1)^d + (-1)^d*(k-1);

chr_bracelet_uniq :=
proc(n, k)
local res, d;

    res := 1/2/n*add(phi(n/d)*P(d,k),
                     d in divisors(n));

    if type(n, even) then
        res := res +
        1/4*k*(k-1)^(n/2);
    fi;

    res;
end;

chr_count :=
proc(gf)
local vars, v, sl;

    vars := indets(gf);
    sl := [seq(v=1, v in vars)];
    subs(sl, gf);
end;


chr_gf_rec :=
proc(len, cols, first, last)
option remember;
local c1, c2, res;

    if len = 1 then return 0 fi;
    if len = 2 then
        if first <> last then
            return C[first]*C[last]
        else
            return 0;
        fi;
    fi;

    res := 0;

    if len = 3 then
        for c1 to cols do
            if c1 <> first and c1 <> last then
                res := res +
                C[first]*C[c1]*C[last];
            fi;
        od;

        return res;
    fi;

    for c1 to cols do
        if c1 <> first then
            for c2 to cols do
                if c2 <> last then
                    res := res +
                    C[first]*C[last] *
                    chr_gf_rec(len-2, cols, c1, c2);
                fi;
            od;
        fi;
    od;

    expand(res);
end;

chr_gf_path :=
proc(len, cols)
local c1, c2;
    if len = 1 then
        return add(C[c1], c1=1..cols);
    fi;
    add(add(chr_gf_rec(len, cols, c1, c2),
            c2 = 1..cols), c1=1..cols);
end;

chr_gf_cycle :=
proc(len, cols)
local c1, c2;
    if len=1 then return 0 fi;
    add(add(`if`(c1 <> c2,
                 chr_gf_rec(len, cols, c1, c2), 0),
            c2 = 1..cols), c1=1..cols);
end;

chr_gf_bracelet_uniq :=
proc(n, k)
option remember;
local res, d, sl, q, c1, c2;

    res := 0;

    for d in divisors(n) minus {1} do
        sl := [seq(C[q] = C[q]^(n/d), q=1..k)];
        res := res +
        phi(n/d)*subs(sl, chr_gf_cycle(d, k))/2/n;
    od;

    if type(n, even) then
        sl := [seq(C[q] = C[q]^2, q=1..k)];

        for c1 to k do
            for c2 to k do
                res := res +
                expand(subs(sl, chr_gf_rec(n/2+1, k, c1, c2))
                       /C[c1]/C[c2]/4);
            od;
        od;
    fi;

    res;
end;

ENUM :=
proc(n, k)
option remember;
local orbits, rec, col, gf, term;

    orbits := table();

    rec :=
    proc(sofar)
    local orbit, rot, rseq, q, c;

        if nops(sofar) < n then
            for c to k do
                if sofar[-1] <> c then
                    rec([op(sofar), c]);
                fi;
            od;
            return;
        fi;

        if sofar[1] = sofar[-1] then
            return;
        fi;

        orbit := [];

        for rot from 0 to n-1 do
            rseq :=
            [seq(sofar[1+((q+rot) mod n)],
                 q=0..n-1)];
            orbit := [op(orbit), rseq];

            rseq :=
            [seq(rseq[n+1-q], q=1..n)];
            orbit := [op(orbit), rseq];
        end;

        orbits[sort(orbit)[1]] := 1;
    end;

    for col to k do rec([col]) od;

    gf := 0;

    for term in [indices(orbits, 'nolist')] do
        gf := gf +
        mul(C[col], col in term);
    od;

    gf;
end;
$\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.