Pairs of Beads on a Ring

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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}$$