A bracelet has $n$ $ϵ$ $Z_+$ colored beads. Show that the number of different bracelets with at most $λ$ different colors on the beads is given by

Question

A bracelet (circle) has $n$ $ϵ$ $Z_+$ colored beads. Show that the number of different bracelets (taking into consideration all symmetries) with at most $λ$ different colors on the beads and no beads of the same color next to each other is given by:
$\frac{1}{2n}*(\sum_{d|n}phi(d)((λ-1)^{\frac{n}{d}}+(-1)^{\frac{n}{d}}(λ-1))+0)$ if $n$ is even $\frac{1}{2n}*(\sum_{d|n}phi(d)((λ-1)^{\frac{n}{d}}+(-1)^{\frac{n}{d}}(λ-1))+{\frac{n}{d}}λ(λ-1)^{\frac{n}{d}})$ if $n$ is odd
where $\sum_{d|n}phi(d)$ is the sum over positive $d$ that divides $n$ and $phi()$ is Euler's totient function.

Hi everyone, I'm completely lost on this one. Do anyone know how to get the wanted result?

Thanks for all the help.

Answer 1

The solution for cyclical symmetries only has already appeared at this MSE link and was found to be (notation from link)

$$\frac{1}{n}\sum_{d|n} \varphi(n/d) P_d(k)$$

where $$P_d(k) = (k-1)^d + (-1)^d \times (k-1).$$

Now we just need to account for reflections which constitute the rest of the dihedral group. Note that when $n$ is odd these reflections fix one bead and the two adjacent beads just opposite end up on the same cycle, which is not a proper coloring, for a contribution of zero or for $n$ odd

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2n}\sum_{d|n} \varphi(n/d) P_d(k).}$$

On the other hand for $n$ even there are two types of reflections, the first about an axis passing through midpoints of opposite edges. These place the beads on those edges on two-cycles and since they are adjacent we get no proper colorings. The other type of reflection fixes two opposite beads. There are $n/2$ of these reflections and the left side determines the right and vice versa. We have $n/2+1$ beads for $k\times (k-1)^{n/2}$ colorings. Hence we get for $n$ even

$$\frac{1}{2n} \sum_{d|n} \varphi(n/d) P_d(k) + \frac{1}{2n} \frac{n}{2} \times k \times (k-1)^{n/2}$$

which is

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2n} \sum_{d|n} \varphi(n/d) P_d(k) + \frac{k}{4}(k-1)^{n/2}.}$$

There is also a Perl script that verifies these two formulae by enumeration.

#! /usr/bin/perl -w
#

MAIN : {
    my $mx = shift || 10;
    my $k = shift || 2;

    my @res = ($k);

    for(my $n=2; $n <= $mx; $n++){
        my %orbits;

        for(my $ind = 0; $ind < $k ** $n; $ind++){
            my ($pos, $idx, @d);

            for(($pos, $idx) = (0, $ind); 
                $pos < $n; $pos++){
                my $digit = $idx % $k;

                push @d, $digit;
                $idx = ($idx-$digit) / $k;
            }

            for($pos=0; $pos < $n; $pos++){
                last if $d[$pos] == $d[($pos+1) % $n];
            }

            if($pos == $n){
                my %orbit;
                for(my $shft = 0; $shft < $n; $shft++){
                    my (@rot) =
                        (@d[$shft..$n-1], @d[0..$shft-1]);

                    my $str = join('-', @rot);
                    $orbit{$str} = 1;

                    $str = join('-', reverse(@rot));
                    $orbit{$str} = 1;
                }

                my $orbstr = (sort(keys %orbit))[0];
                $orbits{$orbstr} = 1;
            }
        }

        push @res, scalar(keys %orbits);
    }

    print join(', ', @res);
    print "\n";

    1;
}