1
$\begingroup$

I would like to count the number of inequivalent ways to arrange $2N$ colored beads on a ring if there are $N$ colors and $2$ beads of each color.

By "inequivalent' I mean inequivalent under (1) rotating the ring (2) flipping the ring (3) exchanging any two beads of the same color.

$\endgroup$
2
$\begingroup$

We can answer this quite easily using the Polya Enumeration Theorem and the cycle index $Z(D_{2N})$ of the dihedral group. We will not derive this cycle index here but it can be worked out from first principles without too much difficulty. We then have for the answer

$$[A_1^2 A_2^2 \cdots A_N^2] Z(D_{2N}) \left(A_1+A_2+\cdots+A_N\right).$$

The cycle index is

$$Z(D_{2N}) = \frac{1}{4N} \sum_{d|2N} \varphi(d) a_d^{2N/d} + \frac{1}{4} a_1^2 a_2^{N-1} + \frac{1}{4} a_2^N.$$

where we have contributions from the cycle index of the cyclic group and from two types of reflections (axis passes through opposite slots or edges).

As we only have two instances of each color and we substitute $a_d = A_1^d + A_2^d + \cdots + A_N^d$ the contribution reduces to

$$\frac{1}{4N} \varphi(1) a_1^{2N} + \frac{1}{4N} \varphi(2) a_2^{N} + \frac{1}{4} a_1^2 a_2^{N-1} + \frac{1}{4} a_2^N$$

which works out to

$$\frac{1}{4N} a_1^{2N} + \frac{N+1}{4N} a_2^{N} + \frac{1}{4} a_1^2 a_2^{N-1}.$$

Do the substitution to get

$$\frac{1}{4N} (A_1+A_2+\cdots+A_N)^{2N} + \frac{N+1}{4N} (A_1^2+A_2^2+\cdots+A_N^2)^{N} \\ + \frac{1}{4} (A_1+A_2+\cdots+A_N)^2 (A_1^2+A_2^2+\cdots+A_N^2)^{N-1}.$$

Extracting coefficients now yields

$$\frac{1}{4N} {2N\choose 2,2,\ldots, 2} + \frac{N+1}{4N} {N\choose 1,1,\ldots, 1} + \frac{1}{4} {N\choose 1} {N-1\choose 1,1,\ldots, 1}.$$

This simplifies to

$$\frac{1}{4N} \frac{(2N)!}{2^N} + \frac{N+1}{4} (N-1)! + \frac{1}{4} N!$$

and we obtain the closed form

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{4N} \frac{(2N)!}{2^N} + \frac{2N+1}{4} (N-1)!.}$$

This yields the sequence

$$1, 2, 11, 171, 5736, 312240, 24327000, 2554072920, \\ 347351195520, 59397023589120, \ldots $$

which points us to OEIS A120445 where additional material awaits (and the above result is confirmed). (Observe that they use the term necklace when we actually have a bracelet.)

The following memory efficient Perl script can be used to compute the first six values of the sequence (output matches result from PET).

#! /usr/bin/perl -w
#

sub recurse {
    my ($n, $slots, $sofar, $orbref) = @_;

    my $rest = scalar(@$slots);

    if($rest == 0){
        my @perm = (-1) x (2*$n);

        my $color = 1;

        map {
            $perm[$sofar->[2*$_]-1] = $color;
            $perm[$sofar->[1+2*$_]-1] = $color;

            $color++;
        } (0..$n-1);

        my (%orbit, $key);

        for(my $rot = 0; $rot < 2*$n; $rot++){
            my @rotact = ();

            push @rotact, 
            @perm[$rot..(2*$n-1)],
            @perm[0..($rot)-1];

            $key = join('-', @rotact);
            $orbit{$key} = 1;

            if($rot % 2 == 0){
                my @reflact1 = reverse @rotact;

                $key = join('-', @reflact1);
                $orbit{$key} = 1;

                my @reflact2; 

                push @reflact2, 
                @reflact1[1..(2*$n-1)],
                $reflact1[0];

                $key = join('-', @reflact2);
                $orbit{$key} = 1;
            }
        }

        $key = join('|', sort(keys(%orbit)));
        $orbref->{$key} = 1;

        return;
    }

    for(my $p=0; $p < $rest; $p++){
        for(my $q = $p+1; $q < $rest; $q++){
            push @$sofar, $slots->[$p], $slots->[$q];

            my @data;

            push @data, 
            @$slots[0..$p-1],
            @$slots[$p+1..$q-1],
            @$slots[$q+1..$rest-1];

            recurse($n, \@data, $sofar, $orbref);

            splice @$sofar, -2, 2;
        }
    }

    1;
}

 MAIN: {
     my $n = shift || 5;

     my %orbits;

     recurse($n, [1..2*$n], [], \%orbits);

     print scalar(keys(%orbits));
     print "\n";

     1;
}

Addendum. We can also do this from first principles without using PET. Introduce the total count of bracelets before applying symmetry and call it $D_N.$ Let $R_N$ be the bracelets that have rotational symmetry, $F_N$ the ones that have reflectional symmetry with an axis passing through opposite slots, $G_N$ the ones that have reflectional symmetry with an axis passing through opposite edges. Put $U_N$ for the ones with no symmetry. We are thus interested in the quantity

$$E_N = R_N + F_N + G_N + U_N.$$

It is not difficult to see that with $N$ sufficiently large the bracelets with rotational symmetry do not have reflectional symmetries which would otherwise require inclusion-exclusion.

Now we have $R_N = \frac{1}{2} \frac{1}{N} N!$ and $F_N = \frac{1}{2} N \times (N-1)!$ and $G_N = \frac{1}{2} N!.$

Observe also that when computing the sizes of the orbits we find

$$D_N = {2N\choose 2,2,\ldots,2} = 2 N R_N + 2 N F_N + 2 N G_N + 4 N U_N$$

which implies

$${2N\choose 2,2,\ldots,2} = 2N \times \frac{1}{2} (1 + 2N) (N-1)! + 4 N U_N \\ = (1+2N) \times N! + 4 N U_N $$

so that

$$E_N = \frac{1}{2} (1+2N) (N-1)! + \frac{1}{4N} {2N\choose 2,2,\ldots,2} - \frac{1+2N}{4} (N-1)! \\ = \frac{1}{4N} \frac{(2N)!}{2^N} + \frac{1+2N}{4} (N-1)!$$

as before.

A reference for this technique may be found at the following MSE link.

$\endgroup$
  • $\begingroup$ I can't single out your mistake, but my numerics agrees with the result of KaliMa, and with oeis.org/A137729 $\endgroup$ – Jennifer Nov 22 '16 at 1:08
  • $\begingroup$ Look carefully at that entry -- it says it counts symmetries up to rotations. As you say you require flips in your post I took it to mean symmetries up to rotations and reflections, which is what I computed. (Flips are a form of reflections.) Considering what I presented above doing rotations only is very straightforward -- use the cycle index of the cyclic group which omits the two terms for the two types of reflections and has $2N$ permutations. $\endgroup$ – Marko Riedel Nov 22 '16 at 1:18
0
$\begingroup$

HINT Start by considering the ways to arrange your beads in a straight line.

Then it will become easier to know how to avoid counting repeated combinations.

$\endgroup$
0
$\begingroup$

First imagine the beads in a straight line.

There are $(2N)!$ ways to arrange the beads if we don't care about duplicates, mirrors, etc.

But now we want to divide out the stuff we don't want.

Every pair of beads that have the same color have been double-counted. In other words (Green1) (Green2) is the same as (Green2) (Green1). So for each pair of colors we divide by $2$. There are $N$ colors so we divide by $2^N$.

At this point we add $N!$ for a reason I am not sure about yet. Maybe someone else can offer an explanation in a separate answer.

Now we divide by $2$ to account for the fact that any layout can be flipped over into a mirror layout.

Finally we divide by $N$ to account for the fact that we could start the chain in $N$ different spots, but we want to consider all of these as being the same ring.

$$\frac{\frac{(2N)!}{2^N} + N!}{2N}$$

Also see https://oeis.org/A137729

This is also a specific case ($n=2$) of "Number of distinct $k$-colored necklaces with $n$ beads per color" where

$$ A(n,k) = \sum_{d | n} \frac{\phi(n/d)(kd)!}{(d!)^kkn}$$

$\endgroup$
  • $\begingroup$ That was my answer too, but it fails for $N=2$ (in fact, it doesn't even resolve to an integer in this case). Should probably divide by $N$ instead of by $2N$, though not quite sure how to explain why. $\endgroup$ – barak manos Nov 21 '16 at 16:57
  • $\begingroup$ @barakmanos I wrote a program to compute the result directly and the numbers lead to oeis.org/A137729 with equation $a(n) = ((2n)!/2^n + n!) / (2n)$ which means after removing the color-pair duplicates, $n!$ is added first before we divide by $2$ for mirrors and $N$ for rings. $\endgroup$ – KaliMa Nov 21 '16 at 17:05
  • $\begingroup$ For some configurations, rotation/flipping gives the same result one would get from exchanging all pairs of same-colored beads. If we shift "green1 red1 green2 red2" by 2, for instance, we get "green2 red2 green1 red1", which we would also get by exchanging the two beads of each pair. Same if we flip "green1 red1 red2 green2". Maybe the + n! in your numerator takes this into account? $\endgroup$ – Jennifer Nov 21 '16 at 17:54

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.