Primera pista.
Consulte este MSE enlace para saber cómo se resolvió un problema estrechamente relacionado.
Segunda pista.
Hay un Perl script que calcula las seis primeras coloraciones propias de un $2n$ -gon utilizando dos instancias de $n$ diferentes colores, con simetrías rotacionales que se tienen en cuenta y no se en cuenta. Los datos obtenidos son los siguientes: para ninguna simetría encontramos
$$0, 2, 24, 744, 35160, 2394720, \ldots$$
y teniendo en cuenta las simetrías rotacionales
$$0, 1, 5, 96, 3528, 199620, \ldots $$
El lector puede utilizarlos para comprobar sus resultados computacionales.
Tercera pista.
El índice de ciclo correspondiente es
$$Z(C_{2n}) = \frac{1}{2n} \sum_{d|2n} \varphi(d) a_d^{2n/d}.$$
¿Puedes determinar el número de coloraciones propias fijadas por cada forma de permutación y aplicar Burnside? Sólo hay tres casos, uno trivial, uno que se puede resolver por inspección y otro que cede a un argumento simple por inclusión-exclusión. Sustituyendo estos en el índice de ciclos para obtener la segunda secuencia, te habrás encontrado con la primera en este punto. Ahora deberías tener una fórmula sencilla que le permite calcular una cantidad suficiente de estas dos secuencias para calificar una consulta de / una nueva entrada en la OEIS, donde parece que la segunda no está incluida todavía. La primera proporciona una entrada especialmente relevante.
Para consultar.
El Perl script va así.
#! /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;
}
Más pistas según la petición
Los recursos web que se pueden consultar son
Cómo calcular con el índice de ciclo. Considere la $\varphi(d)$ permutaciones con forma de ciclo $a_d^{2n/d}$ donde $d|2n.$ Aplicamos Burnside y preguntamos cuántas de las coloraciones apropiadas son fijadas por estas permutaciones. Nótese, sin embargo, que ninguna coloración puede ser constante en un ciclo de longitud $d$ donde $d\gt 2$ porque sólo hay dos instancias de cada color, para una contribución nula. Esto deja $d=1$ y $d=2.$ El Este último caso tiene forma de permutación $a_2^n.$ Para ser constante en estos $n$ dos ciclos debemos colocar una permutación de las dos instancias de cada color en los dos ciclos, lo que puede hacerse en $n!$ maneras.(Esto garantiza automáticamente que dos colores idénticos no estén nunca al lado del otro. entre sí). Nos queda preguntar cuántas coloraciones están fijadas por la permutación de identidad. Estas son precisamente las coloraciones propias del $2n$ -gon con ninguna simetría y podemos calcularlas con inclusión-exclusión. Los nodos $P$ del poset representan aquí coloraciones donde los colores en $P$ se encuentran junto a la otra, además de posiblemente algunos pares más que también están al lado del otro. El peso de este nodo es $(-1)^{|P|}.$ Esto significa que las coloraciones sin vecinos idénticos sólo se incluyen cuando $P$ es el conjunto vacío, para un peso de uno. Las coloraciones con exactamente $p$ los colores junto a los otros se incluyen en todos los nodos $Q$ que son subconjuntos de estos $p$ colores $P$ para una contribución de
$$\sum_{q=0}^p {p\choose q} (-1)^q = 0$$
porque $p\ge 1$ para un peso total de cero. Ahora, para contar realmente los elementos de $P$ tenemos dos posibilidades. En primer lugar, ninguno de los pares de colores se colocan en el par de ranuras especiales envolventes que conectan el último elemento con el primero. Esto da $\frac{(2n-2p+p)!}{2^{n-p}}$ o $$\frac{(2n-p)!}{2^{n-p}}$$ posibilidades. En segundo lugar, uno de los pares se encuentra en el puente ranura. Eso significa que debemos elegir el par, por un factor de $p$ y permutar el resto, para una contribución de $p\frac{(2n-2p+p-1)!}{2^{n-p}}$ o $$p\frac{(2n-p-1)!}{2^{n-p}}.$$ Nosotros obtenemos así, para coloraciones sin simetrías tomadas en cuenta por inclusión-exclusión para $n\ge 2$
$$\sum_{p=0}^n {n\choose p} \frac{(-1)^p}{2^{n-p}} ((2n-p)! + p(2n-p-1)!).$$
Se trata de la siguiente secuencia, que ahora es fácil de calcular:
$$2, 2, 24, 744, 35160, 2394720, 222712560, 27154350720, \\ 4205374225920, 806700010233600, 187793061031699200, \\ 52162131258836121600,\ldots$$
Sustituyendo esto en el índice de ciclo obtenemos para las simetrías rotacionales simetrías rotacionales tomadas en cuenta
$$\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)!).}$$
Así, podemos calcular la secuencia bajo simetrías rotacionales, confirmando y ampliando los valores del Perl script, que utilizaba la enumeración. Obtenemos
$$1, 1, 5, 96, 3528, 199620, 15908400, 1697149440, 233631921600, \\ 40335000693120, 8536048230528000, \\ 2173422135804796800,\ldots$$
Resolver el caso de la simetría diédrica
Obtenemos para el índice del ciclo
$$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.$$
Obsérvese que las permutaciones con forma $a_2^n$ intercambiar las cuentas adyacentes (las que están inmediatamente a la izquierda y a la derecha del eje de reflexión) que tendrían que ser del mismo color ya que están en el mismo ciclo de dos. Esto es imposible, por lo que este término no contribuye. En cambio, para la forma $a_1^2 a_2^{n-1}$ debemos colocar pares de colores en los dos ciclos, dejando dos colores idénticos en las ranuras que son fijas y están situadas en el eje de reflexión. Esto da como resultado $n\times (n-1)!$ posibilidades. Obtenemos por nuestra respuesta
$$\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)!).}$$
Esto da lugar a la siguiente secuencia.
$$0, 1, 4, 54, 1794, 99990, 7955460, 848584800, 116816051520, \\ 20167501253760, 4268024125243200, 1086711068022148800,\ldots $$
El código Perl para esta versión tiene una función diferente para hacer la contabilidad.
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;
}
