First hint.
Consult this MSE
link to learn how a
closely related problem was solved.
Second hint.
There is a Perl script that computes the first six proper colorings of
an $2n$-gon using two instances of $n$ different colors, with
rotational symmetries being taken into account and not being taken
into account. The data that were obtained go like this: for no symmetries
we find
$$0, 2, 24, 744, 35160, 2394720, \ldots$$
and with rotational symmetries taken into account
$$0, 1, 5, 96, 3528, 199620, \ldots $$
The reader may use these to check their computational results.
Third hint.
The relevant cycle index is
$$Z(C_{2n}) = \frac{1}{2n} \sum_{d|2n} \varphi(d) a_d^{2n/d}.$$
Can you determine the number of proper colorings fixed by each shape
of permutation and apply Burnside? There are only three cases, a
trivial one, one that can be solved by inspection and one that yields
to a simple argument by inclusion-exclusion. Substitute these into the
cycle index to obtain the second sequence, you will have encountered
the first one at this point. You should now have a simple formula that
lets you compute enough of these two sequences to qualify for a query
of / a new entry in the OEIS, where it appears the second one is not
included yet. The first one provides a particularly relevant entry.
For consultation.
The Perl script goes like this.
#! /usr/bin/perl -w
#
sub choose2n {
my ($n, $slots, $sofar, $func, @fargs) = @_;
my $len = scalar( @{ $sofar } );
if($len == $n){
my @data = (0) x (2*$n);
for(my $val = 0; $val < $n; $val++){
$data[$sofar->[$val]->[0]] = $val;
$data[$sofar->[$val]->[1]] = $val;
}
&$func(\@data, @fargs);
return;
}
my $rest = 2*$n - 2*$len;
for(my $p=0; $p < $rest; $p++){
for(my $q=$p+1; $q < $rest; $q++){
my ($pos1, $pos2) =
($slots->[$p], $slots->[$q]);
next if $pos1 + 1 == $pos2 ||
($pos1 == 0 && $pos2 == 2*$n-1);
splice @$slots, $q, 1;
splice @$slots, $p, 1;
push @$sofar, [$pos1, $pos2];
choose2n($n, $slots, $sofar,
$func, @fargs);
pop @$sofar;
splice @$slots, $p, 0, $pos1;
splice @$slots, $q, 0, $pos2;
}
}
}
sub account {
my ($dref, $n, $orbref, $nosymref) = @_;
$$nosymref++;
my %orbit;
for(my $shft = 0; $shft < 2*$n; $shft++){
my $str =
join('-',
@$dref[$shft..2*$n-1],
@$dref[0..$shft-1]);
$orbit{$str} = 1;
}
my $orbstr = (sort(keys %orbit))[0];
$orbref->{$orbstr} = 1;
}
MAIN : {
my $mx = shift || 10;
my $k = shift || 2;
my @nosymres = (0); my @res = (0);
for(my $n=2; $n <= $mx; $n++){
my %orbits = (); my $nosym = 0;
my @src = (0..(2*$n-1));
choose2n($n, \@src, [],
\&account, $n, \%orbits, \$nosym);
push @nosymres, $nosym;
push @res, scalar(keys %orbits);
}
print join(', ', @res);
print "\n";
print join(', ', @nosymres);
print "\n";
1;
}
More hints as per request
Web resources to consult are
How to compute with the cycle index. Consider the $\varphi(d)$
permutations with cycle shape $a_d^{2n/d}$ where $d|2n.$ We apply
Burnside and ask how many of the proper colorings are fixed by these
permutations. Note however that no coloring can be constant on a cycle
of length $d$ where $d\gt 2$ because there are only two instances of
each color, for a zero contribution. This leaves $d=1$ and $d=2.$ The
latter case has permutation shape $a_2^n.$ In order to be constant on
these $n$ two-cycles we must place a permutation of the two instances
of each color on the two-cycles which can be done in $n!$ ways.(This
automatically ensures that two identical colors are never next to each
other.) We are left to ask how many colorings are fixed by the
identity permutation. These are precisely the proper colorings of the
$2n$-gon with no symmetries and we can compute these with
inclusion-exclusion. The nodes $P$ of the poset here represent
colorings where the colors in $P$ are next to each other, plus
possibly some more pairs that are also next to each other. The weight
of such a node is $(-1)^{|P|}.$ This means that the colorings with no
identical neighbors are only included when $P$ is the empty set, for a
weight of one. Colorings with exactly $p$ colors next to each other
are included in all nodes $Q$ that are subsets of these $p$ colors $P$
for a contribution of
$$\sum_{q=0}^p {p\choose q} (-1)^q = 0$$
because $p\ge 1$ for a total weight of zero. Now to actually count the
elements of $P$ we have two possibilities. First, none of the pairs of
colors are placed on the special wrap-around slot pair that connects
the last element to the first. This gives
$\frac{(2n-2p+p)!}{2^{n-p}}$ or $$\frac{(2n-p)!}{2^{n-p}}$$
possibilities. Second, one of the pairs is located on the bridge
slot. That means we must choose the pair, for a factor of $p$ and
permute the rest, for a contribution of
$p\frac{(2n-2p+p-1)!}{2^{n-p}}$ or $$p\frac{(2n-p-1)!}{2^{n-p}}.$$ We
thus obtain for colorings with no symmetries taken into account by
inclusion-exclusion for $n\ge 2$
$$\sum_{p=0}^n {n\choose p} \frac{(-1)^p}{2^{n-p}}
((2n-p)! + p(2n-p-1)!).$$
This is the following sequence, which is now easy to calculate:
$$2, 2, 24, 744, 35160, 2394720, 222712560, 27154350720,
\\ 4205374225920, 806700010233600, 187793061031699200,
\\ 52162131258836121600,\ldots$$
Substituting this into the cycle index we obtain for rotational
symmetries taken into account
$$\bbox[5px,border:2px solid #00A000]{\frac{1}{2} (n-1)! +
\frac{1}{2n} \sum_{p=0}^n {n\choose p} \frac{(-1)^p}{2^{n-p}}
((2n-p)! + p(2n-p-1)!).}$$
We may thus compute the sequence under rotational symmetries,
confirming and extending the values from the Perl script, which used
enumeration. We obtain
$$1, 1, 5, 96, 3528, 199620, 15908400, 1697149440, 233631921600,
\\ 40335000693120, 8536048230528000,
\\ 2173422135804796800,\ldots$$
Solving the case of dihedral symmetry
We get for the cycle index
$$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.$$
Observe that the permutations with shape $a_2^n$ swap adjacent beads
(those immediately to the left and the right of the axis of
reflection) which would have to be the same color as they are on the
same two-cycle. This is impossible so this term does not
contribute. On the other hand for the shape $a_1^2 a_2^{n-1}$ we must
place pairs of colors on the two-cycles, leaving two identical colors
on the slots that are fixed and are situated on the axis of
reflection. This yields $n\times (n-1)!$ possibilities. We get for our
answer
$$\bbox[5px,border:2px solid #00A000]{\frac{1}{4} (n-1)! +
+ \frac{1}{4} n! +
\frac{1}{4n} \sum_{p=0}^n {n\choose p} \frac{(-1)^p}{2^{n-p}}
((2n-p)! + p(2n-p-1)!).}$$
This yields the following sequence.
$$0, 1, 4, 54, 1794, 99990, 7955460, 848584800, 116816051520,
\\ 20167501253760, 4268024125243200, 1086711068022148800,\ldots $$
The Perl code for this version has a different function to do the
accounting.
sub account {
my ($dref, $n, $orbref, $nosymref) = @_;
$$nosymref++;
my %orbit;
for(my $shft = 0; $shft < 2*$n; $shft++){
my (@data) =
(@$dref[$shft..2*$n-1],
@$dref[0..$shft-1]);
my $str = join('-', @data);
$orbit{$str} = 1;
for(my $swap = 0; $swap < $n; $swap++){
my $tmp = $data[$swap];
$data[$swap] = $data[2*$n-1-$swap];
$data[2*$n-1-$swap] = $tmp;
}
$str = join('-', @data);
$orbit{$str} = 1;
}
my $orbstr = (sort(keys %orbit))[0];
$orbref->{$orbstr} = 1;
}
