n-digonos
Ignacio Larrosa Cañestro
polígono con 2n lados, teniendo cada dos de ellos la misma longitud,
distinta que la de cualquier otro par. Digamos que un n-dígono es canónico
si las longitudes de sus lados son precisamente 1, 2, ..., n. Entonces,
1) ¿Cuantos n-dígonos distintos hay? Considerando iguales a los obtenidos
unos de otros por rotación o reflexión. Se trata de una cuestión puramente
combinatoria, puede formularse con collares de 2n cuentas de n colores, un
par de cada. Hay dos 2-dígonos, la cometa y el paralelogramo, y si no me
confundo, once 3-dígonos, como el hexágono de Javier. Pero esto último no lo
he deducido, sino que los he enumerado. Me temo que la respuesta no sea
sencilla ...
2) ¿Que se puede decir del radio de un n-dígono canónico inscriptible? Para
n = 2, es rq(5)/2, para n = 3 es la raíz positiva de 2r^3 - 7r - 3 = 0, para
n = 4, 5, ... Asintóticamente es r(n) ~ n(n+1)/(2pi), ¿pero se puede decir
alguna otra cosa?
--
Saludos,
Ignacio Larrosa Cañestro
A Coruña (España)
ilarrosaQUIT...@mundo-r.com
georgesZ
Hola,
creo que, para n=3, la prueba que has dado da 2 radios para los dos
tipos de hexagonos insciptibles :
1) con lados de longitud que se siguen 1,2,3 (en cualquier modo) y el
radio es la raíz positiva de 2r^3 - 7r - 3 = 0
2) con lados de longitud que se siguen 1,1,2,2,3,3 (en cualquier modo)
y el radio es la raíz positiva de 2r^3 - 7r + 3 = 0
Amistades,
Georges
georgesZ
como calculastes el radio r = 2,0565.. exacto (con senos y arctg)?
Ignacio Larrosa Cañestro
¿Te refieres a que en el primer caso los lados se ordenan como [1, 2, 3, 1,
2, 3] y en el segundo como [1, 1, 2, 2, 3, 3]?
El radio es el mismo en ambos casos, así como en cualquiera de las otras
nueve configuraciones en que pueden colocarse los lados. No hay más que
partir de una cualquiera de ellas, dividir el hexágono en triángulos uniendo
los vértices con el centro de la circunferencia circunscrita, y reordenar
estos triángulos de cualquier forma. La suma de los ángulos centrales
siempre es 2pi, y los v´ñertices siempre están a la misma distancia del
centro ...
El valor
r = rq(42)sen(arctg(9rq(1329)/443)/3 + pi/3)/3
~= 2.056545292
lo obtuve resolviendo la cúbica 2r^3 - 7r - 3 = 0 con Derive, pero no debe
ser difícil llegar al mismo resultado resolviéndola a mano, utilizando el
método trigonométrico, ya que se trata del caso irreducible, con tres raíces
reales. Normalmente quedaría expresado como un coseno, pero por algún motivo
Derive decidió expresarlo en este caso como un seno.
Antonio González
> A propósito del último hexágono de Javier, definamos un n-dígono como un
> polígono con 2n lados, teniendo cada dos de ellos la misma longitud,
> distinta que la de cualquier otro par. Digamos que un n-dígono es canónico
> si las longitudes de sus lados son precisamente 1, 2, ..., n. Entonces,
>
> 1) ¿Cuantos n-dígonos distintos hay? Considerando iguales a los obtenidos
> unos de otros por rotación o reflexión. Se trata de una cuestión puramente
> combinatoria, puede formularse con collares de 2n cuentas de n colores, un
> par de cada. Hay dos 2-dígonos, la cometa y el paralelogramo, y si no me
> confundo, once 3-dígonos, como el hexágono de Javier. Pero esto último no lo
> he deducido, sino que los he enumerado. Me temo que la respuesta no sea
> sencilla ...
>
Haciendo que el Mathematica los enumere, con el programilla
n = 3; ltot = Permutations[Ceiling[Range[2n]/2]];
i = 0;
While[Length[ltot] > i,
i++;
ltot = Complement[ltot,
Complement[NestList[RotateLeft, ltot[[i]], 5], {
ltot[[i]]}]];
ltot =
Complement[
ltot,
Complement[NestList[RotateLeft,
Reverse[ltot[[i]]], 5], {ltot[[i]]}]];
];
Print[ltot];
Print[Length[ltot]]
Me salen
n = 2 2
n = 3 11
n = 4 374
n = 5 ???
(lleva un montón de tiempo calculando, más de media hora, y aún no ha
acabado)
--
Antonio
Antonio González
Ya está
n = 5 18047
Lo de 6, mejor dejarlo...
Por cierto, que no aparece en Encyclopedia. Igual sería cuestión de
introducirla.
Más en general, ¿cuál es el número de polígonos esencialmente diferentes
con lados iguales o diferentes, no necesariamente a pares?
--
Antonio
Ignacio Larrosa Cañestro
> El valor
>
> r = rq(42)sen(arctg(9rq(1329)/443)/3 + pi/3)/3
>
> ~= 2.056545292
>
> lo obtuve resolviendo la cúbica 2r^3 - 7r - 3 = 0 con Derive, pero no
> debe ser difícil llegar al mismo resultado resolviéndola a mano,
> utilizando el método trigonométrico, ya que se trata del caso
> irreducible, con tres raíces reales. Normalmente quedaría expresado
> como un coseno, pero por algún motivo Derive decidió expresarlo en
> este caso como un seno.
Veamoslo.
2r^3 - 7r - 3 = 0 ===>
r^3 - (7/2)r = 3/2
Teniendo en cuenta que
cos(3t) = 4cos^3(t) - 3cos(t)
Hacemos r = k*s,
k^3*s^3 - (7k/2 )s = 3/2
y escogemos k para que
k^3/(7k/2) = 4/3 ==> k = rq(42)/3
con lo que queda,
4s^3 - 3s = 9rq(42)/98
Haciendo s = cos(t), queda
cos(3t) = 9rq(42)/98 ===>
t = arccos(9rq(42)/98)/3 + 2pi*n/3, n = 0, 1, 2
s = cos(arccos(9rq(42)/98)/3 + 2pi*n/3)
r = (rq(42)/3)cos(arccos(9rq(42)/98)/3 + 2pi*n/3)
El único valor positivo se obtiene para n = 0, por lo que
r = (rq(42)/3)cos(arccos(9rq(42)/98)/3) ~= 2.056545292
Queda ver que
cos(arccos(9rq(42)/98)/3) = sen(arctg(9rq(1329)/443)/3 + pi/3)
Para ello pongamos el segundo miembro como
M = sen((arctg(9rq(1329)/443) + pi)/3)
Pero si
x = arctg(9rq(1329)/443)
tg(x) = 9rq(1329)/443 ==> cos(x) = +/- rq(6202)/98
(da igual tomar el signo + o el -)
M = sen((arccos(rq(6202)/98) + pi)/3)
= cos(pi/2 - (arccos(rq(6202)/98) + pi)/3)
= cos((pi/2 - arccos(rq(6202)/98))/3)
= cos(arccos(rq(1 - (rq(6202)/98)^2))/3)
= cos(arccos(9rq(42)/98)/3) (q.e.d.)
Derive probablemente empleé el mismo método para resolver la cúbica, pero
por alguna extraña razón, considera más simple la expresión con sen y arctg
...
georgesZ
> ¿Te refieres a que en el primer caso los lados se ordenan como [1, 2, 3, 1,
> 2, 3] y en el segundo como [1, 1, 2, 2, 3, 3]?
>
> El radio es el mismo en ambos casos, así como en cualquiera de las otras
> nueve configuraciones en que pueden colocarse los lados. No hay más que
> partir de una cualquiera de ellas, dividir el hexágono en triángulos uniendo
> los vértices con el centro de la circunferencia circunscrita, y reordenar
> estos triángulos de cualquier forma. La suma de los ángulos centrales
> siempre es 2pi, y los v´ñertices siempre están a la misma distancia del
> centro ...
Si, tienes razon, si se supone la convexidad. Si no lo es, quizas se
obtiene un radio mas pequeño. Pero entonces no lo da tu razonamiento,
porque supones a+b+c=pi, aunque lo utilizas solo con el coseno de los
angulos...
> El valor
>
> r = rq(42)sen(arctg(9rq(1329)/443)/3 + pi/3)/3
>
> ~= 2.056545292
>
> lo obtuve resolviendo la cúbica 2r^3 - 7r - 3 = 0 con Derive, pero no debe
> ser difícil llegar al mismo resultado resolviéndola a mano, utilizando el
> método trigonométrico, ya que se trata del caso irreducible, con tres raíces
> reales. Normalmente quedaría expresado como un coseno, pero por algún motivo
> Derive decidió expresarlo en este caso como un seno.
Gracias,
Georges
Ignacio Larrosa Cañestro
Me has sacado de un buen lío ... Estaba a punto de ponerme a enumeralos a
mano (para n = 4, que ya llega). En lugar de eso voy a intentar repasar el
Lema de Burnside, el Teorema de la Acción de Polya, que creo que debe ir por
ahí la cosa.
Para ello puede estar bien el documento de José H. Nieto:
http://mipagina.cantv.net/jhnieto/tac.pdf
especialmente para Antonio, pues parece que usa bastante el Mathematica.
> Por cierto, que no aparece en Encyclopedia. Igual sería cuestión de
> introducirla.
Si acaso después de lo anterior ...
> Más en general, ¿cuál es el número de polígonos esencialmente
> diferentes con lados iguales o diferentes, no necesariamente a pares?
¿Demasiado general, no?
Antonio González
>
>> Más en general, ¿cuál es el número de polígonos esencialmente
>> diferentes con lados iguales o diferentes, no necesariamente a pares?
>
> ¿Demasiado general, no?
>
diferentes, con todos sus lados diferentes.
Por ejemplo, para n = 4 son 3, y para n = 5 son 12
(Es que ya que he hecho el programilla, me es fácil adaptarlo :-) Por
ejemplo, para los cuadriláteros tenemos los siguientes casos:
aaaa ---> 1
aaab ---> 1
aabb ---> 2
aabc ---> 2
abcd ---> 3
Total: 9
)
--
Antonio
Ignacio Larrosa Cañestro
> Ignacio Larrosa Cañestro escribió:
>>
>>> Más en general, ¿cuál es el número de polígonos esencialmente
>>> diferentes con lados iguales o diferentes, no necesariamente a
>>> pares?
>>
>> ¿Demasiado general, no?
>>
> Bueno, empecemos entonces, por el número de polígonos esencialmente
> diferentes, con todos sus lados diferentes.
>
> Por ejemplo, para n = 4 son 3, y para n = 5 son 12
Esta es fácil: (n-1)!/2
Se trata de las permutaciones circulares de n elementos, (n-1)!, divididas
por 2 al tener en cuenta la simetría.
--
Saludos,
Ignacio Larrosa Cañestro
A Coruña (España)
ilarrosaQUIT...@mundo-r.com
Marko Riedel
Hola Ignacio, hola grupo,
usando el indice de ciclos del grupo dihedral D_{2n} y el teorema de
Polya, es decir,
[a1^2 a2^2 a3^2 ... an^2] Z(D_{2n})(a1, a2, a3, ... an)
me sale
1, 2, 11, 171, 5736, 312240, 24327000, 2554072920.
Algo no cuadra. Voy a esperar la solucion de JHN. ;-)
Un saludo.
Marko
--
+------------------------------------------------------------+
| Marko Riedel, EDV Neue Arbeit gGmbH, mri...@neuearbeit.de |
| http://www.geocities.com/markoriedelde/index.html |
+------------------------------------------------------------+
Dr. Wolfgang Hintze
Mi programa de Mathematica calcula los clases equivalentes
de las conjuntas de las permutaciones de forma
n=2 -> {1,1,2,2}, n=3 -> {1,1,2,2,3,3}, ...
Donde "equivalente" significa: invarinate bajo la rotación y la inversión
El programe me da
n=2
-> 2
{
{1, 1, 2, 2},
{1, 2, 1, 2}}
n=3 -> 15
{
{1, 1, 2, 2, 3, 3},
{1, 1, 2, 3, 2, 3},
{1, 1, 2, 3, 3, 2},
{1, 1, 3, 2, 2, 3},
{1, 2, 1, 2, 3, 3},
{1, 2, 1, 3, 2, 3},
{1, 2, 2, 1, 3, 3},
{1, 2, 2, 3, 1, 3},
{1, 2, 3, 1, 2, 3},
{1, 2, 3, 1, 3, 2},
{1, 2, 3, 2, 1, 3},
{1, 3, 2, 2, 1, 3},
{2, 3, 2, 1, 1, 3},
{3, 2, 1, 2, 1, 3},
{3, 2, 2, 1, 1, 3}}
n=5
-> 315
{
{1, 1, 2, 2, 3, 3, 4, 4},
{1, 1, 2, 2, 3, 4, 3, 4},
{1, 1, 2, 2, 3, 4, 4, 3},
{1, 1, 2, 2, 4, 3, 3, 4},
{1, 1, 2, 2, 4, 3, 4, 3},
{1, 1, 2, 2, 4, 4, 3, 3},
{1, 1, 2, 3, 2, 3, 4, 4},
...,
{3, 4, 3, 2, 1, 1, 2, 4},
{3, 4, 4, 1, 3, 2, 1, 2},
{3, 4, 4, 2, 1, 2, 1, 3},
{3, 4, 4, 2, 2, 1, 1, 3}}
Parece que algo me falta ya que los otros han hallado resultados
diferentes ...
Saludos,
Wolfgang
Antonio González
> Mi programa de Mathematica calcula los clases equivalentes
> de las conjuntas de las permutaciones de forma
>
> n=2 -> {1,1,2,2}, n=3 -> {1,1,2,2,3,3}, ...
> Donde "equivalente" significa: invarinate bajo la rotación y la inversión
>
> El programe me da
>
>
> n=2 -> 2
> {
> {1, 1, 2, 2},
> {1, 2, 1, 2}}
>
> n=3 -> 15
> {
> {1, 1, 2, 2, 3, 3},
> {1, 1, 2, 3, 2, 3},
> {1, 1, 2, 3, 3, 2},
> {1, 1, 3, 2, 2, 3},
> {1, 2, 1, 2, 3, 3},
> {1, 2, 1, 3, 2, 3},
> {1, 2, 2, 1, 3, 3},
> {1, 2, 2, 3, 1, 3},
> {1, 2, 3, 1, 2, 3},
> {1, 2, 3, 1, 3, 2},
> {1, 2, 3, 2, 1, 3},
> {1, 3, 2, 2, 1, 3},
> {2, 3, 2, 1, 1, 3},
> {3, 2, 1, 2, 1, 3},
> {3, 2, 2, 1, 1, 3}}
>
Comparando con las mías:
{1,1,2,2,3,3},
{1,1,2,3,2,3},
{1,1,2,3,3,2},
{1,1,3,2,2,3},
{1,2,1,2,3,3},
{1,2,1,3,2,3},
{1,2,2,1,3,3},
{1,2,2,3,1,3},
{1,2,3,1,2,3},
{1,2,3,1,3,2},
{1,2,3,2,1,3}}
vemos que te sobran las cuatro últimas: las tres últimas, porque todas
deben empezar por 1 en el orden "canónico", y la 4ª por la cola que es
una rotación y una inversión de {1,2,2,3,1,3}.
Mi programa también hace lo que el tuyo. He de decir que antes de llegar
al 11 a mí también me salieron varios resultados diferentes. Escribiendo
en forma más detallada:
While[Length[ltot] > i,
i++;
lista1 = Complement[
NestList[RotateLeft, ltot[[i]], 5], {ltot[[i]]}];
ltot = Complement[ltot,lista1];
lista2=Complement[NestList[RotateLeft, Reverse[ltot[[i]]], 5],
{ltot[[i]]}];
ltot = Complement[ltot,lista2];
];
Print[Short[ltot]];
Print[Length[ltot]]
lo que hace es primero crear una lista ltot con todas las permutaciones,
y luego irla recorriendo. Dado un elemento de ltot, ltot[[i]], creo una
lista con todas sus rotaciones, a la cual le sustraigo (con el
Complement) el propio elemento ltot[[i]]. Al principio me limitaba a
quitar el primer elemento, pero eso me dio problemas con listas como
123123 que al rotarlas dan igual a sí mismas. Luego hallo el complemento
de ltot con esa "lista1", de forma que elimino todas las rotaciones de
ltot[[ì]].
Más tarde invierto ltot[[i]] y hallo las rotaciones de la inversión.
Sustraigo el elemento ltot[[i]] por si acaso (al principio no lo hice
hasta que me fijé en listas como 123321 que son su propia inversa).
Luego hallo el complemento de ltot con esta "lista2".
Continúo el proceso con el siguiente elemento restante de ltot, hasta
que se acaba la lista, lo cual ocurre cuando el índice del bucle
coincide con la longitud de la lista ltot.
Pero...viendo mi resultado de 374 elementos
{{1,1,2,2,3,3,4,4},{1,1,2,2,3,4,3,4},{1,1,2,2,3,4,4,3},{1,1,2,2,4,3,3,
4},<<366>>,{4,1,3,1,4,3,2,2},{4,1,3,2,2,3,4,
1},{4,1,3,2,2,4,1,3},{4,1,3,2,3,2,4,1}}
observo que al final hay elementos que no empiezan por 1. A depurar, tocan.
--
Antonio
Antonio González
>
> Mi programa también hace lo que el tuyo. He de decir que antes de llegar
> al 11 a mí también me salieron varios resultados diferentes. Escribiendo
> en forma más detallada:
>
> While[Length[ltot] > i,
> i++;
> lista1 = Complement[
> NestList[RotateLeft, ltot[[i]], 5], {ltot[[i]]}];
> ltot = Complement[ltot,lista1];
> lista2=Complement[NestList[RotateLeft, Reverse[ltot[[i]]], 5],
> {ltot[[i]]}];
> ltot = Complement[ltot,lista2];
> ];
> Print[Short[ltot]];
> Print[Length[ltot]]
>
>
>
> {{1,1,2,2,3,3,4,4},{1,1,2,2,3,4,3,4},{1,1,2,2,3,4,4,3},{1,1,2,2,4,3,3,
> 4},<<366>>,{4,1,3,1,4,3,2,2},{4,1,3,2,2,3,4,
> 1},{4,1,3,2,2,4,1,3},{4,1,3,2,3,2,4,1}}
>
> observo que al final hay elementos que no empiezan por 1. A depurar, tocan.
>
¡Aaargh, ya he visto que solo rota 5 veces en cualquier caso, en lugar
de 2n-1 veces!
Una vez corregido, ya me salen 171 como a Marko.
Versión corregida:
n = 4; ltot = Permutations[Ceiling[Range[2n]/2]];
i = 0;
lcasos = {};
While[Length[ltot] > 0,
caso = ltot[[1]];
lcasos = Append[lcasos, caso];
ltot = Complement[ltot, NestList[RotateLeft, caso, 2n - 1]];
ltot = Complement[ltot, NestList[RotateLeft, Reverse[caso], 2n - 1]];
];
Print[lcasos];
Print[Length[lcasos]]
--
Antonio
Marko Riedel
> Antonio González escribió:
[...]
> ¡Aaargh, ya he visto que solo rota 5 veces en cualquier caso, en lugar
> de 2n-1 veces!
>
>
> Una vez corregido, ya me salen 171 como a Marko.
>
> Versión corregida:
>
> n = 4; ltot = Permutations[Ceiling[Range[2n]/2]];
> i = 0;
> lcasos = {};
> While[Length[ltot] > 0,
> caso = ltot[[1]];
> lcasos = Append[lcasos, caso];
> ltot = Complement[ltot, NestList[RotateLeft, caso, 2n - 1]];
> ltot = Complement[ltot, NestList[RotateLeft, Reverse[caso], 2n - 1]];
> ];
> Print[lcasos];
> Print[Length[lcasos]]
>
Hola de nuevo,
Aqui viene mi contribucion a la solucion algoritmica del problema. Se
trata de un programa que no es muy eficaz, pero que es suficiente para
calcular los primeros cinco valores:
1 1
2 2
3 11
4 171
5 5736
Esto es el programa:
#! /usr/bin/perl -w
#
sub fact {
my ($n) = @_;
return 1 if $n<2;
my $res = 1;
while($n>1){
$res *= $n;
$n--;
}
return $res;
}
sub permute {
my ($n, $d) = @_;
my (@result) = (1..$n, 1..$n);
$n *= 2;
while($n>1){
my $r = $d % $n;
my $tmp = $result[$r];
$result[$r] = $result[$n-1];
$result[$n-1] = $tmp;
$d = ($d-$r)/$n;
$n--;
}
return \@result;
}
sub digonos {
my ($n) = @_;
my $f = fact(2*$n);
my %seen;
for(my $i = 0; $i<$f; $i++){
my $p = permute($n, $i);
my $new = 1;
for(my $r=0; $r<4*$n; $r++){
if(defined($seen{join('-', @$p)})){
$new = 0;
last;
}
my $first = shift(@$p);
push @$p, $first;
if($r==2*$n-1){
$p = [ reverse(@$p) ];
}
}
if($new){
$seen{join('-', @$p)} = 1;
}
}
return scalar(keys(%seen));
}
MAIN: {
my ($upper) = shift || 6;
for(my $n=1; $n<=$upper; $n++){
print "$n " . digonos($n) . "\n";
}
}
Un saludo.
Antonio González
> Hola de nuevo,
>
> Aqui viene mi contribucion a la solucion algoritmica del problema. Se
> trata de un programa que no es muy eficaz, pero que es suficiente para
> calcular los primeros cinco valores:
>
> 1 1
> 2 2
> 3 11
> 4 171
> 5 5736
Por cierto, ya llegué al mismo 5736 para n = 5. Parece que ahora sí
estamos de acuerdo (y tú tenías razón).
Están bien estas cosillas, que ayudan a ejercitar la lógica de los
algoritmos (o como dijeron el otro día en telecinco, a "descifrar los
logaritmos").
--
Antonio
Ignacio Larrosa Cañestro
Marko Riedel <mri...@neuearbeit.de> escribió:
>> http://www.geocities.com/markoriedelde/index.html |
> +------------------------------------------------------------+
El programa de Antonio también da 5735 para n = 5. Definitivamente no esta
en la OEIS. Yo estaba intentando algo así como las permutaciones circulares
con repetición, y coger las simétricas más la mitad de las que no lo son.
Algo así como
(((2n)!/2^n - 2n*n!)/2 + 2n*n!)/(2n)
Pero debe faltar algo, pues da unos valores, aparte de no enteros,
ligeramente inferiores a los reales:
[0.75, 1.75, 10.5, 169.5, 5730, 312210, 24326820, 2554071660, 347351185440,
59397023498400]
En lugar de
[1, 2, 11, 171, 5736, ... ]
Seguire en ello ...
Marko Riedel
Es un problema divertido. A ver quien nos cuenta algo mas sobre la
aplicacion del teorema de Polya. Supongo que Matematica lo incluye como
funcion? En todo caso merece el esfuerzo implementarlo, para tenerlo
listo para problemas como este.
Antonio González
>
> Es un problema divertido. A ver quien nos cuenta algo mas sobre la
> aplicacion del teorema de Polya. Supongo que Matematica lo incluye como
> funcion? En todo caso merece el esfuerzo implementarlo, para tenerlo
> listo para problemas como este.
>
En el paquete Combinatorica tienes la función NumberOfNecklaces que
parece resolver precisamente este problema:
"NumberOfNecklaces[n, nc, Cyclic] returns the number of distinct ways in
which an n-bead necklace can be colored with nc colors, assuming that
two colorings are equivalent if one can be obtained from the other by a
rotation.
NumberOfNecklaces[n, nc, Dihedral] returns the number of distinct ways
in which an n-bead necklace can be colored with nc colors, assuming that
two colorings are equivalent if one can be obtained from the other by a
rotation or a flip. "
pero al aplicarlo se ve que considera que el número de cuentas con el
mismo color es variable, no es fijo en 2 como estamos suponiendo.
Seguiremos investigando.
--
Antonio
Marko Riedel
Hola grupo, hola Antonio,
no tengo acceso a Matematica, asi que no puedo mirarlo yo mismo, pero
me parece que estas dos funciones son implementaciones del lema de
Burnside, que es suficiente cuando no se clasifican las soluciones
segun su composicion.
No te parece un reto fascinate juntar esfuerzos con JHN para escribir
una implementacion del Teorema de Polya para Matematica y subirla a la
pagina de JHN, para luego hacerla disponible como software libre?
Ignacio Larrosa Cañestro
Ignacio Larrosa Cañestro <ilarrosaQUIT...@mundo-r.com> escribió:
> A propósito del último hexágono de Javier, definamos un n-dígono como
> un polígono con 2n lados, teniendo cada dos de ellos la misma
> longitud, distinta que la de cualquier otro par. Digamos que un
> n-dígono es canónico si las longitudes de sus lados son precisamente
> 1, 2, ..., n. Entonces,
> 1) ¿Cuantos n-dígonos distintos hay? Considerando iguales a los
> obtenidos unos de otros por rotación o reflexión. Se trata de una
> cuestión puramente combinatoria, puede formularse con collares de 2n
> cuentas de n colores, un par de cada. Hay dos 2-dígonos, la cometa y
> el paralelogramo, y si no me confundo, once 3-dígonos, como el
> hexágono de Javier. Pero esto último no lo he deducido, sino que los
> he enumerado. Me temo que la respuesta no sea sencilla ...
>
O mucho me confundo, lo que desde luego es posible e incluso probable, o
estamos algo desnortados. A mi teóricamente me salen 11 para n = 3, pero
solo 90 para n = 5 ... A ver si lo reviso y completo más dexpacio.
Ignacio Larrosa Cañestro
Vayamos pues más deSpacio, pues calculé bastante mal ... Aplicando
correctamente la teoría, me salen los mismos resultados que a Marko.
Tal teoría puede verse, por ejemplo, en
http://mipagina.cantv.net/jhnieto/tac.pdf o en el libro
http://mipagina.cantv.net/jhnieto/tc.pdf.
Para visualizar mejor el problema, podemos transformarlo en uno equivalente:
De cuantas formas pueden rotularse los 2n vértices de un polígono regular de
2n lados con n pares de letras.
Necesitamos el "Polinomio indicador de ciclos" del polígono regular de 2n
lados. Las transformaciones que lo dejan invariante y la descomposición en
ciclos de las permutaciones asociadas son:
i) n simetrias C respecto a las rectas que pasan por los centros de dos
caras opuestas. Se descomponen en n transposiciones (2-ciclos).
ii) n simetrías V respecto a las rectas que pasan por dos vértices opuestos.
Se descomponen en n-1 transposiciones y en dos 1-ciclo-
iii) 2n rotaciones rk, de ángulos k*2pi/n, k = 0, 1, ..., n-1. Esto es lo
más complicado, pues la descomposición en ciclos depende de la
descomposición de 2n en factores primos.
En total, 4n transformaciones
(Esto, como decía Marko, debe ser el grupo Diedríco 2n, o algo así)
Con esto se construye el citado polinomio, con 2n variables, en principio,
cada una para cada longitud posible de un ciclo, con un término para cada
transformación, con las variables correspondientes elevadas al número de
ciclos de esa longitud en que se descompone la permutación.
Veamos el caso de n = 3:
i) 3*x2^3
ii) 3*x1^2*x2^2
iii) r0 --> x1^6; r1, r5 --> 2*x6; r2, r4 --> 2*x3^2; r3 --> x2^3
Pg = (1/12)(x1^6 + 4*x2^3 + 3*x1^2*x2^2 + 2*x3^2 + 2*x6)
Si queremos todas las configuraciones con hasta todas las longitudes
distintas, debemos hacer todas las variables iguales a 6 (2n), con lo que
nos queda 4291, donde se incluye desde el hexágono regular a todos los
posibles con los seis lados distintos. Esta era una cuestión que planteó
Antonio el otro dia.
Pero si queremos saber cuantas configuraciones hay con 3 pares de longitudes
dierentes, o la formas de rotular los vértices con tres pares de letras, la
cosa es más complicado. Debemos sustituir cada xk en Pg por a^k + b^k + ...
+ z^k, donde las variables a, b, ...z, representan las distintas
posibilidades. En nuestro caso, quedaría
(1/12)((a+b+c)^6 + 4(a^2+b^2+c^2)^3 + 3(a+b+c)^2*(a^2+b^2+c^2)^2 +
2*(a^3+b^3+c^3)^2 + 2*(a^6+b^6+c^6))
= a^6 + a^5b + a^5c + 3a^4b^2 + 3a^4bc + 3a^4c^2 + 3a^3b^3 + 6a^3b^2c +
6a^3bc^2 + 3a^3c^3 + 3a^2b^4 + 6a^2b^3c + 11a^2b^2c^2 + 6a^2bc^3 + 3a^2c^4 +
ab^5 + 3ab^4c + 6ab^3c^2 + 6ab^2c^3 + 3abc^4 + ac^5 + b^6 + b^5c + 3b^4c^2 +
3b^3c^3 + 3b^2c^4 + bc^5 + c^6
El coeficiente de a^2b^2c^2 nos da el número de configuraciones con tres
pares de valores, 11 como ya sabíamos.
Para n = 4, tenemos
i) 4 simetrias C ---> 4*x2^4
ii) 4 simetrías V ---> 4*x1^2*x2^3
iii) r0 --> x1^8; r1, r3, r5, r7 --> 4*x8; r2, r6 --> 2*x4^2; r4 --> x2^4
Pg = (1/16)(x1^8 + 5*x2^4 + 4*x1^2*x2^3 + 2*x4^2 + 4*x8)
Ahora debemos sustituir xk = a^k + b^k + c^k + d^4, y hallar el coeficiente
de a^2b^2c^2d^2. No intervienen todos los términos, basta considerar los que
contienen solo x1 y x2:
(1/16)((a+b+c+d)^8 + 5(a^2+b^2+c^2+d^2)^4 + 4(a+b+c+d)^2(a^2+b^2+c^2+d^2)^3)
Y nos queda 171, como ya sabiamos.
Para n = p primo, tenemos
i) p simetrías C --> p*x2^p
ii) p simetrias V --> p*x1^2*x2^(p-1)
iii) r0 --> x1^(2p); rp --> x2^p; las otras 2p-2 --> (2p-2)x_2p
Pg = (1/(4p))(x1^(2p) + (p+1)*x2^p + p*x1^2*x2^(p-1) + (2p-2)*x^(2p))
(Para nuestro problema no es necesario considerar estas 2p-2 últimas)
Para p = 5,
Pg = (1/20)(x1^10 + 6*x2^5 + 5*x1^2*x2^4 + 8*x10)
Sustituyendo xk = a^k+b^k+c^k+d^k+e^k, el término en a^2b^2c^2d^2e^2 es
5736.
Realmente no se como pude obtener el 90 que mencionaba en mi anterior
mensaje ...
Para p = 7,
Pg = (1/28)(x1^14 + 8*x2^7 + 7*x1^2*x2^6 + 12*x14)
Y el coeficiente de a^2b^2c^2d^2e^2f^2g^2 es
(14!/2^7 + 8*7! + 7*7!)/28 = 24327000
En general, para p primo
((2p)!/2^p + (p+1)*p! + p*p!)/(4p)
Pensándolo bien, la parte que nos interesa de Pg tiene idéntica estructura,
tanto si p es primo como si no, por lo que en general será
D(n) = ((2n)!/2^n + (n+1)*n! + n*n!)/(4n)
= 1, 2, 11, 171, 5736, 312240, 24327000, 2554072920, 347351195520,
59397023589120, 12473374574505600, 3155763762320400000, ...
Nota: Este mensaje se transformó varias veces según se fué redactando, por
lo que no sería sorprendente que aparte de gazapos, hubiese alguna notoria
incoherencia.
Saludos, de uno que se siente palestino-libanés ...
Ignacio Larrosa Cañestro
Evidentemente, la fórmula se puede resumir un poco:
D(n) = ((2n)!/2^n + (2n+1)*n!)/(4n)
Pero además, se puede obtener directamente, tal y como intentaba hacer en mi
mensaje del dia 17. Olvidemos inicialmente las rotaciones. Debemos coger la
mitad de las configuraciones S'(n) no simétricas, más las S(n) simétricas.
De estas, debemos considerar las S1(n) que tienen simetría central, las
S2(n) que tienen simetría axial respecto a rectas que pasan por los puntos
medios de los lados, y las S3(n) que tienen simetría axial respecto a rectas
que pasan por vértrices opuestos. A su vez, S'(n) será igual al total T(n)
menos las simétricas. Finalmente, debemos dividir por 2n para tener en
cuenta las rotaciones. Será
D(n) = (S'(n)/2 + S(n))/(2n) = ((T(n) - S(n))/2 + S(n))/(2n) = (T(n) +
S(n))/(4n)
T = (2n)!/2^n
(permutaciones de 2n elementos en los que hay n pares iguales)
S(n) = S1(n) + S2(n) + S3(n)
S1(n) = n! (podemos colocar arbitrariamente un miembro de cada par en una de
las mitades del polígono)
S2(n) = n*n! (n posiciones para la recta y n! formas de colocarlos a un lado
de ella)
S3(n) = n*n*(n-1)! (n posiciones para la recta, n formas de elegir el
elemento por el que pasa la recta y (n-1)! de distribuir los demás a un lado
de ella)
En total,
S(n) = (2n+1)n!
y
D(n) = ((2n)!/2^n + (2n+1)n!)/(4n)
¡Al final, no era imprescindible toda la teoría de Burnside y Polya ...!
Pero para mi fue muy instructivo utilizarla.
Marko Riedel
> En el mensaje:4i7vcqF...@individual.net,
> Ignacio Larrosa Cañestro <ilarrosaQUIT...@mundo-r.com> escribió:
> >>> A propósito del último hexágono de Javier, definamos un n-dígono
> >>> como un polígono con 2n lados, teniendo cada dos de ellos la misma
> >>> longitud, distinta que la de cualquier otro par. Digamos que un
> >>> n-dígono es canónico si las longitudes de sus lados son precisamente
> >>> 1, 2, ..., n. Entonces,
> >>> 1) ¿Cuantos n-dígonos distintos hay? Considerando iguales a los
> >>> obtenidos unos de otros por rotación o reflexión. Se trata de una
> >>> cuestión puramente combinatoria, puede formularse con collares de 2n
> >>> cuentas de n colores, un par de cada. Hay dos 2-dígonos, la cometa y
> >>> el paralelogramo, y si no me confundo, once 3-dígonos, como el
> >>> hexágono de Javier. Pero esto último no lo he deducido, sino que los
> >>> he enumerado. Me temo que la respuesta no sea sencilla ...
> >>>
[...]
Hola Ignacio, hola grupo,
para resumirlo, el indice de ciclos del grupo dihedral D_{2n} es
Z(D_{2n}) =
1/(4n) ( sum_{d|2n} fi(d) a_d^{2n/d}
+ n a_2^n + n a_1^2 a_2^(n-1)).
El primer termino de la derecha representa las rotaciones, el segundo,
las reflexiones en las rectas que pasan por los centros de dos caras
opuestas, y el tercero, las reflexiones en las rectas que pasan por
dos vertices opuestos.
El termino buscado es entonces
[t_1^2 t_2^2 t_3^2 ... t_n^2] Z(D_{2n})(t_1, t_2, t_3, ... t_n).
La suma que representa las rotaciones contribuye (d = 1)
[t_1^2 t_2^2 ... t_n^2] (t_1 + t_2 + ... + t_n)^2n = (2n)!/2^n
y (d = 2)
[t_1^2 t_2^2 ... t_n^2] (t_1^2 + t_2^2 + ... + t_n^2)^n = n!.
El segundo termino contribuye
n [t_1^2 t_2^2 ... t_n^2] (t_1^2 + t_2^2 + ... + t_n^2)^n = n n!
y el tercero
n [t_1^2 t_2^2 ... t_n^2] (t_1 + t_2 + ... + t_n)^2
(t_1^2 + t_2^2 + ... + t_n^2)^(n-1) = n n (n-1)! = n n!
lo que da finalmente
((2n)!/2^n + (2n+1)n!)/(4n)
que es el resultado que descubriste tu.
Como te parece, deberia estar esta secuencia en la OEIS?
Me gustaria saber si Derive es capaz de soportar una implementacion
generalizada del Teorema de Polya (es decir, donde uno puede trabajar
con grupos y indices de ciclos diferentes). Aun espero que alguien
presente una implementacion en Matematica. Otra cosa es que resulta
dificil creer que no este presente en Matematica todavia.
Mi problema "1501202096154112" del 20 de febrero queda por solucionar
(el enlace es http://groups.google.com/group/es.ciencia.matematicas/\
browse_thread/thread/ea6afcf56d9f1d97/e0be5335302b20df?lnk=st&q=\
&rnum=8&hl=en#e0be5335302b20df).
gamo
...
> tanto si p es primo como si no, por lo que en general será
>
> D(n) = ((2n)!/2^n + (n+1)*n! + n*n!)/(4n)
>
> = 1, 2, 11, 171, 5736, 312240, 24327000, 2554072920, 347351195520,
> 59397023589120, 12473374574505600, 3155763762320400000, ...
>
1 1
2 2
3 11
4 171
5 5736
6 312240
7 24327000
8 2554072920
9 347351195520
10 59397023589120
11 12473374574505600
12 3155763762320400000
13 946729128624509260800
14 332301924146113021900800
15 134914581203304233287756800
16 62735280259536165098353536000
17 33124227977035089658775531520000
18 19708915646335878241332275109888000
19 13126137820459694906598505966030848000
20 9726468124960633925744484233677590528000
Por si quieres añadir algunos dígitos más para el oeis o como se llame.
Saludos
--
http://www.telecable.es/personales/gamo/
perl -e 'print 111_111_111**2,"\n";'
Ignacio Larrosa Cañestro
Marko Riedel <mri...@neuearbeit.de> escribió:
La deducción que emplea el polinomio indicador de ciclos es correcta, aunque
estaba poco formalizada, muy bien tu resumen. Pero la directa, creo que está
un poco coja, por decirlo suavemente ...
> Como te parece, deberia estar esta secuencia en la OEIS?
Lo envié anoche, pero como la persona que mantiene el sitio, Neil J.A.
Sloane, concluye hoy precisamente una estancia de un mes fuera, supongo que
tardará bastante tiempo en procesar todo el trabajo pendiente, que no debe
ser poco.
> Me gustaria saber si Derive es capaz de soportar una implementacion
> generalizada del Teorema de Polya (es decir, donde uno puede trabajar
> con grupos y indices de ciclos diferentes). Aun espero que alguien
> presente una implementacion en Matematica. Otra cosa es que resulta
> dificil creer que no este presente en Matematica todavia.
Que yo sepa en Derive no hay nada, aunque posiblemente pueda programarse.
Por parte de quien sepa, claro; mis habilidades programando Derive son
absolutamente rudimentarias.
En cuanto a Mathematica, me limito a usarlo interactivamente para confirmar
los resultados de Derive o cuando este no da respuesta. Creo que le saco muy
poco partido, es una asignatura que tengo pendiente ( y me temo que seguiré
teniendo ...)
> Mi problema "1501202096154112" del 20 de febrero queda por solucionar
> (el enlace es http://groups.google.com/group/es.ciencia.matematicas/\
> browse_thread/thread/ea6afcf56d9f1d97/e0be5335302b20df?lnk=st&q=\
> &rnum=8&hl=en#e0be5335302b20df).
A primera vista parce más complicado. El sábado me marcho 12 dias a Madeira,
así que si sobrevivo al aterrizaje en el aeropuerto de Funchal (creo que es
toda una experiencia), intentaré echarle un vistazo a la vuelta. Pero casi
mejor vuelve a enviarlo, lo verá más gente.