miércoles, 30 de octubre de 2013

Piezas para cuadrados


En la entrada anterior formamos curiosos números triangulares concatenando un número con otros relacionados con él, como n//n, n+1//n, 2n//n y otros. Vamos hoy a intentarlo con cuadrados. Este tema está más estudiado, y ya hay más casos publicados en OEIS. Los recorremos:

n//n

Es difícil que un número concatenado consigo mismo produzca un cuadrado. Los pocos casos que aparecen ya están publicados:

1322314049613223140496, 2066115702520661157025, 2975206611629752066116, 4049586776940495867769, 5289256198452892561984,… http://oeis.org/A092118

La razón de que se descubran tan pocos es la siguiente: el número concatenado n//n es en realidad n*(10^c+1), siendo c el número de cifras de n, por lo que n<10^c. Por ejemplo, 7878=78*(10^2+1)=78*101. Si deseamos que n//n sea un cuadrado, 10^c+1 ha de contener algún cuadrado como factor, porque si es libre de cuadrados, es imposible que n aporte los factores que quedan para completar un cuadrado, puesto que es menor que 10^c.

Habrá que buscar números del tipo 10^k+1 que no sean libres de cuadrados.

Si factorizamos, por ejemplo, desde 11 hasta 10^50+1, descubrimos que sólo en cuatro casos  contiene un cuadrado (copiamos la tabla parcialmente)

100000000001=11^2*23*4093*8779
1000000000000000000001=7^2*11*13*127*2689*459691*909091
1000000000000000000000000000000001=7*11^2*13*23*4093*8779*599144041* 183411838171
1000000000000000000000000000000000000001=7*11*13^2*157*859*6397*216451*1058313049* 388847808493.

Para completar un cuadrado como el que se pide, n deberá contener los factores primos que no figuran al cuadrado (la parte libre) y además, si acaso, otros factores adicionales elevados al cuadrado. Ya vimos en su día que si multiplicamos N por la parte libre de N conseguiremos el mínimo múltiplo cuadrado de N

(http://hojaynumeros.blogspot.com.es/2011/12/emparedado-de-cuadrados-2.html).

Cumplido esto, deberá tener el número de cifras adecuado. Por ejemplo, en el primer caso
N=23*4093*8779*k^2 y si queremos que tenga 11 cifras, el valor mínimo de k es 4, con lo que nos da la primera solución: n=23*4093*8779*16=13223140496, que engendra el cuadrado

1322314049613223140496, primer término de http://oeis.org/A092118

Si tomamos k=5 obtenemos el segundo término: n=20661157025, que engendra el segundo cuadrado 2066115702520661157025

Para k=6 se engendra el tercer cuadrado: 2975206611629752066116 y para k=7, 8 o 9 se engendran los términos cuarto a sexto. A partir de este valor se sobrepasan las cifras.

Así que el caso 100000000001 engendra seis términos.

Pasamos al siguiente:

1000000000000000000001=7^2*11*13*127*2689*459691*909091

El valor adecuado de n será del tipo n=11*13*127*2689*459691*909091*k^2

Para k=1 y k=2 no se llega al número de cifras mínimo. Para k=3 nos resulta el séptimo término: 183673469387755102041183673469387755102041. No están publicados más términos. Para k=4, 5 y 6 nos resultan términos inéditos:

326530612244897959184326530612244897959184
510204081632653061225510204081632653061225
734693877551020408164734693877551020408164

No deseamos marear a nuestros lectores, por lo que no abordamos los siguientes casos. Sólo dejamos una muestra:

132231404958677685950413223140496132231404958677685950413223140496

2n//n

Se puede seguir el mismo razonamiento y descomponer en factores los números del tipo 2*10^c+1 que contienen cuadrados

20000000000000000001=3*7^2*83*1663*985694468327
2000000000000000000000000000000001=3*43^2*245169227*1470638299531951365929

Con el primero

32653061224489795921632653061224489796
73469387755102040823673469387755102041
130612244897959183686530612244897959184

Con el segundo

216333153055705786911844240129800108166576527852893455922120064900
261763115197404002163331530557058130881557598702001081665765278529
311519740400216333153055705786912155759870200108166576527852893456
365603028664142779881016765819362182801514332071389940508382909681
424012979989183342347214710654408212006489994591671173607355327204
486749594375338020551649540292050243374797187669010275824770146025
553812871822606814494321254732288276906435911303407247160627366144
625202812330989724175229853975122312601406165494862087614926987561
700919415900486749594375338020552350459707950243374797187669010276
780962682531097890751757706868578390481341265548945375878853434289
865332612222823147647376960519200432666306111411573823688480259600

Los primeros están publicados en http://oeis.org/A115529

n//2n

No explicamos ya el procedimiento. Los candidatos son:

12=2^2*3
100000000000000000000002=2*3*7^2*19961*17040030781111603
10000000000000000000000000000000000000000000000000000000002=2*3*89^2* 353891*184629530872289*3220312754723112768886882952137673

Con el primero obtenemos el 36=6^2

Con el segundo:

816326530612244897959216326530612244897959184
1836734693877551020408236734693877551020408164
3265306122448979591836865306122448979591836736

Y con el tercero, verdaderos gigantes:

5049867440979674283550056811008711021335689938139123848001009973488195934856710011362201742204267137987627824769600

Publicados en http://oeis.org/A115527

Concatenación con diferencias constantes

Casi todos los casos están estudiados. Aquí ya no disponemos del análisis de los factores de 2*10^c+1 o similares. Sólo podemos acudir a la búsqueda, porque al añadir un sumando al número todo el planteamiento anterior falla.

n//n+1

Los primeros ejemplos los buscaremos con hoja de cálculo (no mostraremos el código) y con PARI.



Hemos añadido la raíz cuadrada de la concatenación. Esta sucesión está publicada en
 http://oeis.org/A030465  y llama a los primeros números de Sastry.

El código PARI adecuado es

concatint(a,b)=eval(concat(Str(a),Str(b)))
{for(n=1,10^7,a=concatint(n,n+1);if(issquare(a),print(a)))}

 N+1//n

Los primeros ejemplos son



También publicado en  http://oeis.org/A054214

Adapta tú el código PARI para encontrar más.

n//n+2

El número par 7874 es el más pequeño que cumple que concatenado con el siguiente par 7876 produce un cuadrado: 78747876=8874^2. Este caso ya está publicado en http://oeis.org/A115426.

n+2//n

Es el problema simétrico del anterior y también está estudiado en http://oeis.org/A115431
Aquí paramos, porque otras concatenaciones resultan menos atractivas. No obstante, con lo que ya has leído puedes emprender búsquedas por tu cuenta.



miércoles, 23 de octubre de 2013

Triangulares con piezas concatenadas


Esta entrada participa en la edición 4.1231056 del Carnaval de Matemáticas, cuyo anfitrión es el blog Scientia.

Quien ha entrado en el mundo de la programación elemental sabe qué es la operación de concatenar cadenas (“strings”): situar sus caracteres uno detrás del otro. Si lo representamos por &, equivaldría a que “Pablo “&”Pérez”= “Pablo Pérez”.

En las hojas de cálculo disponemos de la función CONCATENAR, que une varios textos de celdas en uno =CONCATENAR(A12;B22;G1).

Más difícil es concatenar números naturales, de forma que el resultado sea otro verdadero número en el que cada cifra tenga su valor relativo. Una forma se basa en esta función CONCATENAR. Para ello debemos convertir los números en cadenas, con la función TEXTO, después, concatenarlos, y finalmente, usar la función VALOR para devolverles el carácter numérico. Tiene un inconveniente, y es que TEXTO ha de ir acompañado de un formato, y esto lo complica todo. En PARI no existe ese problema, por lo que puedes definir la concatenación entre números mediante

concatint(a,b)=eval(concat(Str(a),Str(b)))

Un método más matemático, y es el que adoptaremos para la hoja de cálculo es el de multiplicar el número de la izquierda por una potencia de 10 adecuada y sumar luego el de la derecha. Así, concatenar 255 con 182 equivaldría al número 255*10^3+182=255182

¿Qué exponente ha de tener esa potencia de 10? El número de cifras del que está a la derecha. Para encontrar ese número podemos usar el logaritmo decimal, de esta forma: =ENTERO(LOG(N;10))+1. Por tanto, una concatenación numérica vendría dada por la fórmula CONCAT(A;B)=A*10^((ENTERO(LOG(B;10))+1))+B

Esta fórmula fallaría para B=0, por lo que habría que retocarla con un condicional, pero no lo haremos. Basta que se sepa que existe esa función numérica, y en la práctica en este blog usaremos una rutina en Basic.

Se producen muchas curiosidades cuando concatenamos números naturales. Veamos algunas. Es evidente que nos movemos en cuestiones curiosas y no teóricas. Comenzamos generando números triangulares y dejaremos para otras entradas otros casos.

Producir triangulares

Intentaremos concatenar un número n consigo mismo o con otros relacionados con él a fin de conseguir un número triangular. Por ejemplo, 426 concatenado consigo mismo produce el triangular 426426. Para entender mejor lo que sigue, recuerda que todo número triangular se puede expresar como N(N+1)/2, es decir, la mitad de un oblongo N(N+1). En este caso, 426426=923*924/2

Estudiamos algunas concatenaciones concretas:

Triangular concatenando n//n

En primer lugar probaremos a concatenar un número consigo mismo para producir un triangular.

Ya están publicados en http://oeis.org/A068899

55, 66, 5050, 5151, 203203, 255255, 426426, 500500, 501501, 581581, 828828, 930930, 39653965, 50005000, 50015001, 61566156, 3347133471, 5000050000, 5000150001, 6983669836, 220028220028, 500000500000, 500001500001…

Si te llaman la atención los ejemplos del tipo 500…500 y 500…1500…1, piensa que no son nada extraordinarios: 500500=1000*1001/2, que es un triangular y 50015001=10001*10002/2 que es otro. Investiga casos similares.

Triangular concatenando 2n//n

De esta forma se generan los siguientes:

21, 105, 2211, 9045, 222111, 306153, 742371, 890445, 1050525, 22221111, 88904445, 107905395, 173808690, 2222211111, 8889044445, 12141260706, 15754278771, 222222111111, 888890444445, 22222221111111, 36734701836735, 65306123265306, 88888904444445, 163718828185941…

¿Es siempre triangular 2222…1111…? Sí, porque sus dobles se descomponen como 4444…2222=6666..6*6666…7, es decir, números oblongos formados por productos de números consecutivos. En lo que sigue acudiremos varias veces al hecho de que el doble de un triangular es un oblongo, k(k+1).
Se puede demostrar que cada vez que se añade la cifra a los factores aparecen 4444..2222. Lo razonamos con 666*667=444222 pero para más cifras se comprende igual: En efecto, si 666*667=444222, al añadir una cifra tenemos:

6666*6667=(6000+666)(6000+667)=36000000+6000*1333+666*667=43998000+444222=44442222.

Observa que si aumentamos las cifras, 1333 se convertiría en 133….33 y el sumando final 43998000 en 4399…8000… con lo que el efecto de reconstruir 44444 y 2222 sería el mismo.

Algo similar ocurre con la subsucesión 9045, 890445, 88904445,…engendrada por los oblongos 134*135, 1334*1335, 13334*13335,…Son casualidades que ocurren al dividir las potencias de 10 en tercios o en sextos.

Si deseas reproducir los resultados puedes usar este código en PARI

concatint(a,b)=eval(concat(Str(a),Str(b)))
istriang(x)=issquare(8*x+1)
{for(n=1,10^5,a=concatint(2*n,n);if(istriang(a),print(a)))}

Hemos publicado esta sucesión en https://oeis.org/A226742

Concatenación inversa n//2n

¿Y si concatenáramos en sentido contrario, primero el número y después su doble? Pues, aunque menos llamativo, también se construyen triangulares. Son estos:

36, 1326, 2346, 3570, 125250, 223446, 12502500, 22234446, 1250025000, 2066441328, 2222344446, 2383847676, 3673573470, 125000250000, 222223444446, 5794481158896, 12500002500000, 12857132571426, 22222234444446, 49293309858660...

Intenta razonar la aparición de estos números, con un método similar al usado en el anterior caso: 36, 2346, 223446, 22234446,… es porque sus dobles se descomponen como 666…68*666…69. Observa también esta otra subsucesión: 125250, 12502500, 12500025000, que provienen de los oblongos 500*501, 5000*5001,…¿Y el resto? Te lo dejamos por si encuentras una pauta.

Código PARI para este caso:

concatint(a,b)=eval(concat(Str(a),Str(b)))
istriang(x)=issquare(8*x+1)
{for(n=1,10^7,a=concatint(n,2*n);if(istriang(a),print(a)))}

Hemos publicado esta sucesión en https://oeis.org/A226772

Concatenación n//n+1

También se producen números triangulares:

45, 78, 4950, 5253, 295296, 369370, 415416, 499500, 502503, 594595, 652653, 760761, 22542255, 49995000, 50025003, 88278828, 1033010331, 1487714878, 4999950000, 5000250003, 490150490151, 499999500000, 500002500003, 509949509950, 33471093347110, 49999995000000, 50000025000003, 69834706983471…

Se destaca el subconjunto 45, 4950, 499500,….y es porque sus dobles son 9999…*10000… y también los 5253, 502503, 50035003,…¿En qué se parecen entre sí?

Puedes reproducirlos con este código PARI

concatint(a,b)=eval(concat(Str(a),Str(b)))
istriang(x)=issquare(8*x+1)
{for(n=1,10^7,a=concatint(n,n+1);if(istriang(a),print(a)))}

Hemos publicado esta sucesión en https://oeis.org/A226788

Con n+1//n resultan verdaderos monstruos

21, 26519722651971, 33388573338856, 69954026995401, 80863378086336,…

A partir de este último no se han podido encontrar más para n<10^10, o resultados menores que 10^20. Quizás con una herramienta o equipo más potentes se pueda encontrar alguno más fuera de esa acotación. Los lectores quedáis invitados a intentarlo. Podéis usar este código PARI

concatint(a,b)=eval(concat(Str(a),Str(b)))
istriang(x)=issquare(8*x+1)
{for(n=1,10^7,a=concatint(n,n+1);if(istriang(a),print(a)))}

Si disponéis de MATHEMATICA también bastará adaptar este otro, añadido por T.D. Noe a A226789:

TriangularQ[n_] := IntegerQ[Sqrt[1 + 8*n]]; t = {}; Do[s = FromDigits[Join[IntegerDigits[n+1], IntegerDigits[n]]]; If[TriangularQ[s], AppendTo[t, s]], {n, 100000}]; t (* T. D. Noe, Jun 18 2013 *)

No vamos seguir las concatenaciones de este tipo. Las dejamos para quien le apetezca encontrar más ejemplos curiosos. Sí podíamos seguir jugando con las cifras, pero con otras estructuras. Seguimos buscando triangulares.

Otras concatenaciones para triangulares

No hemos intentado todavía concatenar un número con su reverso. Por ejemplo, 59 con 95 forman el triangular 5995. Intentamos una búsqueda por ahí. Antes de presentar resultados hay que advertir que los terminados en 0, como 90, producen resultados ambiguos, en este caso 990. Por eso restringiremos la búsqueda a números no múltiplos de 10. En ese caso resultan estas soluciones:

55, 66, 5995, 8778, 617716, 828828, 35133153, 61477416, 1264114621,…, que forman una subsucesión de http://oeis.org/A003098

Un resultado curioso es si concatenamos un número n por la izquierda con 10*n, porque en ese caso resulta un número duplicado con un cero en el centro. Hemos encontrado estos, que resultan muy vistosos:

41041, 66066, 165301653, 56661056661, 3719010371901, 276816602768166, 13776656013776656, 28265441028265441, 41631576041631576, 47337278047337278, 55666611055666611, 82189446082189446, 91836735091836735, 1185252600118525260, 1960592100196059210…

Como es norma de este blog, evitamos seguir insistiendo en el tema. Con estos ejemplos nuestros lectores pueden abordar otras búsquedas.


jueves, 17 de octubre de 2013

Ciclos(3) Números de Stirling de primera especie

Vimos en la entrada anterior que toda permutación sobre el conjunto {1,2,3,…,n} se puede descomponer en k ciclos, y van desde la identidad, que comprende n ciclos, hasta las permutaciones cíclicas, que se reducen a un solo ciclo.

Si fijamos el número k, podremos plantearnos cuántas permutaciones se pueden descomponer exactamente en k ciclos. Por ejemplo, en el conjunto {1,2,3,4,5}, las permutaciones formadas por dos ciclos son (escribimos sólo los conjuntos invariantes en los ciclos):

(1,2,3,4)(5), (1,2,3,5)(4), (1,2,4,5)(3), (1,3,4,5)(2), (2,3,4,5)(1),
(1,2,3)(4,5), (1,2,4)(3,5), (1,3,4)(2,5), (2,3,4)(1,5), (1,2,5)(3,4), (1,3,5)(2,4), (2,3,5)(1,4),
(1,4,5)(2,3), (2,4,5)(1,3), (1,3,5)(1,2)

Resultan en total 15 configuraciones, pero cada conjunto de cuatro elementos equivale a seis ciclos (permutaciones circulares, factorial de n-1=3). Así, (1,2,3,4) contiene en realidad los ciclos (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3)(1,4,3,2) y cada conjunto de tres equivale a dos ciclos (y los de dos, a uno solo), luego tendremos:

S(5,2)=5*6+10*2=50

Al número de permutaciones de n elementos que están formadas por k ciclos le llamaremos número de Stirling de primera especie sin signo, y lo representaremos por S(n,k). Así, el cálculo anterior se puede expresar como S(5,2)=50

Es evidente que S(n,n)=1, pues sólo la identidad contiene n ciclos, y que S(n,1)=(n-1)!, pues representaría a las permutaciones circulares. Además, S(n,0)=0, valor adoptado por definición. Piensa también por qué S(n,n-1)=Cn,2 (número combinatorio).

El resto de números de Stirling se obtiene mediante la fórmula de recurrencia

S(n+1,k)=S(n,k-1)+nS(n,k)

En efecto, si añadimos un elemento nuevo a una configuración en ciclos, puede ocurrir que ese elemento sea un invariante, que forme ciclo consigo mismo. En ese caso puede estar acompañado de S(n,k-1) formas distintas de distribución en ciclos. Por el contrario, si el nuevo lo deseamos integrar en los ciclos ya existentes, lo podemos incluir ocupando n lugares distintos, luego formará nS(n,k) configuraciones diferentes.

Lo entenderás mejor con un ejemplo. Formemos todas las distribuciones de 4 elementos en 3 ciclos:

(1)(2,3)(4), (2)(1,3)(4), (3)(1,2)(4)
(1,4)(2)(3), (1)(2,4)(3), (1)(2)(3,4)

En total resultan 6. En la primera fila hemos añadido el 4 como elemento invariante, añadido a las tres configuraciones de 3 elementos en dos ciclos S(3,2) y en la segunda lo hemos integrado en los ciclos existentes, que sólo tienen una posibilidad, (1)(2)(3) (S(3,1)) y podemos insertarlo en 3 posiciones distintas, luego resultan 3S(3,3). En resumen:

S(4,3)=S(3,2)+3S(3,3)

Esto nos da una posibilidad de calcular estos números. Por convenio se les da valor cero cuando el número de ciclos es cero. En la imagen tienes la tabla conseguida en hoja de cálculo con stirling.xls y stirling.ods (los puedes descargar desde
http://hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#nume)



Comprueba en ella alguna generación por recurrencia. Por ejemplo, 274=50*5+24, 1624=225*6+274

También es elemental la propiedad de que la suma de números de Stirling para un n dado es n!, pues abarcan todas las posibilidades. Comprueba este hecho sumando todos los números de una misma fila en la tabla de la imagen.

Observa que cada fila posee un solo máximo, como ocurre, por ejemplo con los números combinatorios, sólo que aquí no está necesariamente en el punto medio.

Función generatriz

La función generatriz de estos números (con signo), para un n dado es

Fn(x)=x(x-1)(x-2)(x-3)…(x-n+1)=x(n

Con ella resultan los números con signo y prescindiendo de S(n,0). Observa que se trata de una potencia factorial, o factorial de grado n de x. Los números de Stirling con signo obedecen la misma fórmula de recurrencia, pero restando el segundo término. Esto es claro si consideras el desarrollo de

Fn+1(x)=x(x-1)(x-2)(x-3)…(x-n+1)(x-n)= Fn(x)(x-n)

Piensa en un grado cualquiera del desarrollo y lo comprenderás.

Lo podemos comprobar con PARI, por ejemplo en el caso n=6

{print(taylor(x*(x-1)*(x-2)*(x-3)*(x-4)*(x-5),x,7))}

Resultado: -120*x + 274*x^2 - 225*x^3 + 85*x^4 - 15*x^5 + x^6 + O(x^7)

En la imagen puedes estudiar la comprobación con wxMaxima:



Como ves, los ordena en sentido inverso.

Una interpretación sencilla de este desarrollo es el considerar los números de Stirling (salvo el caso de índice cero) como los coeficientes mediante los que una potencia factorial x(n se descompone como combinación lineal de potencias ordinarias xk de x.

jueves, 10 de octubre de 2013

Ciclos (2) – Descomposición en ciclos


Algunas permutaciones dejan invariantes unos elementos, y a otros los van transformando cíclicamente hasta volver al primero. Así, la permutación (1,3,4,2,5,6) deja invariantes 1, 5 y 6, mientras 3 se transforma en 4, este en 2 y el 2 tiene como imagen el 3. A este tipo de permutaciones las llamaremos ciclos. Omitimos definiciones formales, porque aquí nuestro interés es práctico y de aprendizaje de las hojas de cálculo.

Llamaremos ciclo a una permutación que deja invariantes algunos elementos y somete a una rotaciones completas a los restantes. 

Representaremos un ciclo mediante los elementos que se van transformando uno en otro, omitiendo los invariantes. Así, (3,4,2) representaría a la anterior permutación. Podemos someter a los elementos 3,4,2 a una rotación en el orden y representarían el mismo ciclo: (3,4,2) = (4,2,3) = (2,3,4), pero otro tipo de alteración del orden, como (3,2,4) ya representaría un ciclo distinto. Si aplicamos reiteradamente un ciclo, cada elemento irá pasando por todas las posiciones posibles e, inversamente, por una posición dada irán pasando ordenadamente todos los elementos.

Un mismo ciclo se puede representar comenzando con cualquiera de sus elementos si se respeta el orden circular.

Un ciclo de un elemento representa un elemento invariante, y el de dos, una transposición entre dos elementos. Si el ciclo abarca la permutación completa, a esta la llamaremos cíclica.

La propiedad más importante de los ciclos es que toda permutación se puede descomponer en ciclos disjuntos de forma única salvo el orden. Según esto, la del ejemplo podemos representarla como (1,3,4,2,5,6)=(3,4,2)(1)(5)(6). Se suelen ordenar los ciclos por su magnitud, de mayor a menor.

¿Cómo descomponer una permutación en ciclos?

El procedimiento puede ser el siguiente:

Elegimos el elemento 1, y aplicamos la permutación de forma reiterada hasta que la imagen vuelva a ser 1. Como el conjunto es finito, esto se acabará logrando, con lo que ya tendremos el primer ciclo de la descomposición. Buscamos después el siguiente elemento que no pertenezca al ciclo conseguido (si hemos acabado es que la permutación estudiada se reduce a un solo ciclo, es cíclica) y efectuamos la misma operación para obtener el segundo ciclo, y así sucesivamente hasta agotar el conjunto.
Por ejemplo, la permutación (4, 2, 6, 7, 8, 9, 10, 11, 3, 1, 5) nos llevaría al siguiente proceso:
Comenzamos con el 1. Las sucesivas imágenes serían: 1 – 4 – 7 – 10 – 1. Ya tendríamos el primer ciclo (4, 7, 10, 1).

Buscamos el siguiente elemento no estudiado aún: el 2, que se transforma en sí mismo. El siguiente ciclo es, pues, (2)

Siguiente elemento libre: 3, que engendra: 3 – 6 – 9 – 3, formando el ciclo (3, 6, 9)

Por último, con 5 logramos (5, 8, 11)

Hemos terminado: (4, 2, 6, 7, 8, 9, 10, 11, 3, 1, 5) = (4, 7, 10,1) (3, 6, 9) (5, 8, 11) (2)

Como cada ciclo opera sobre elementos disjuntos, esta descomposición es un producto en Sn (ver entrada anterior del blog), en el que los ciclos son permutables y por tanto, no influye el orden.
En este proceso los ciclos que se formen serán disjuntos, pues si dos de ellos tuvieran un elemento común, al aplicar el ciclo sobre él reiteradamente se incluirían todos los elementos, y los ciclos serían en realidad uno solo.

El número de ciclos en que se descompone una permutación varía entre 1, si ella misma es cíclica, hasta n, si se trata de la permutación identidad.

Podemos conseguir que una hoja de cálculo haga lo mismo:


Lo hemos implementado en Excel y Apache OpenOffice (http://hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#ciclos)

Observa que ha creado una fila en la que va tomando nota de los ciclos a los que pertenece cada elemento, y después ha escrito debajo la composición de cada ciclo. Es una tarea un poco larga, por lo que sólo explicaremos los fundamentos, remitiendo después a la hoja ya confeccionada.

Proceso para encontrar los ciclos:

1) Se crean unas memorias que contendrán la información de los ciclos que se van ocupando. Al principio se inician todas a cero.

2) En cada paso del proceso se busca el primer elemento cuyo número de ciclo es 0. Se aumenta en una unidad el número del ciclo, que, por tanto, comenzará en 1. Con un procedimiento similar al usado en la anterior entrada, se aplica reiteradamente la permutación hasta completar el ciclo.

Este paso se da mientras exista un elemento con número de ciclo 0. Para cada elemento, se irá escribiendo en la hoja a qué ciclo pertenece.

3) Localizados los ciclos, se van buscando los elementos de cada uno y se escriben en filas distintas debajo del esquema. Esta parte es más informática que matemática, y la podemos omitir.

Generación aleatoria

Como la hoja de cálculo ofrecida no tiene más objetivo que el de explicar el concepto, se ha añadido la posibilidad de generar aleatoriamente una permutación para comprender mejor la descomposición en ciclos.


Orden de un ciclo

No es difícil entender que el orden de un ciclo es su longitud, ya que los elementos invariantes seguirán siéndolo aunque reiteremos y los cíclicos se irán recorriendo uno por uno y se llegará al primero cuando se recorra toda la longitud:

El orden de un ciclo coincide con su longitud

También es sencillo entender que si una permutación se descompone en ciclos, su orden será el MCM de las longitudes de los mismos.

Así, el orden de (1)(2, 3, 7)(4, 5)(6) será 6, el mcm(1, 3, 2, 1)

En la misma hoja se puede estudiar el orden de los ciclos y el de la permutación total

El orden de los ciclos aparece en la parte izquierda de los mismos










El orden total, MCM de los de los ciclos lo tendrás en la parte derecha

Transposiciones

Llamaremos transposición a un ciclo de orden 2. Todo ciclo, y en consecuencia toda permutación, se puede descomponer en transposiciones. Se comprende sólo con estudiar este desarrollo:

(a, b, c, d, e)=(a, e)(a, d)(a, c)(a, b)

Esta descomposición no es única.

Algunos cálculos

Permutaciones circulares  o cíclicas

Puede ocurrir que una permutación sea en sí misma un ciclo. La llamaremos cíclica o circular. Dentro del grupo simétrico Sn el número de permutaciones cíclicas equivale a (n-1)! Es algo muy conocido y se justifica porque para inventarte una permutación de este tipo en primer lugar has de ordenar todos los elementos, lo que puedes realizar de n! formas diferentes y una vez elegida una, esta representa n circulares idénticas, porque tienes n formas de elegir el primer elemento, luego el número es n!/n=(n-1)!
Permutaciones de n elementos que son ciclos de orden k

Deberemos elegir k elementos para el ciclo y dejar los restantes n-k fijos. El elegirlos nos supone Cn,k formas y dentro de los elegidos, (k-1)! ciclos posibles, luego el número total de ciclos de orden k será



Permutaciones reducidas

Son aquellas que no dejan fijo ningún elemento, las que en la descomposición en ciclos ninguno de ellos tiene orden 1. Son las conocidas como desarreglos (o desbarajustes) Los puedes estudiar en http://hojamat.es/sindecimales/combinatoria/teoria/teorcomb.pdf

En esa dirección hemos explicado su fórmula



jueves, 3 de octubre de 2013

Ciclos (1) Grupo simétrico


Solemos considerar las permutaciones como las distintas ordenaciones de un conjunto. Existe otro punto de vista alternativo, que es muy fructífero, y es considerarlas como  aplicaciones biyectivas del conjunto en sí mismo. Así, la permutación S=(3,2,1,4) se puede considerar derivada de (1,2,3,4) (orden principal) mediante la aplicación S(1)=3, S(2)=2, S(3)=1 y S(4)=4. Así la interpretaremos aquí.

Como la naturaleza de los elementos no influye en la teoría, imaginaremos que se trabaja siempre sobre el conjunto {1,2,3,4,…,n} y que una permutación como S=(5,1,3,2,…) se interpreta: S(1)=5, S(2)=1, S(3)=3, S(4)=2,…La escribimos así, como un conjunto de imágenes, por comodidad de escritura, pero te la puedes imaginar con los orígenes sobre ellas formando una matriz de dos filas, con lo que cae cada imagen debajo del origen

Las permutaciones se pueden componer como todas las aplicaciones, usando una de ellas  y después la otra sobre las imágenes de la primera. No es fácil verlo en este caso, por lo que usaremos un ejemplo:
Sean G=(4,2,5,3,1) y H=(1,4,3,5,2), o escribiendo orígenes:

G:







H:








La composición H*G (escribiendo de derecha a izquierda) se formaría así (hay que estar atentos):

H*G(1)=H(G(1))=H(4)=5   H*G(2)=H(G(2))=H(2)=4   H*G(3)=H(G(3))=H(5)=2
H*G(4)=H(G(4))=H(3)=3   H*G(5)=H(G(5))=H(1)=1, con lo que resultaría
H*G=(5,4,2,3,1)  Como ves, no es nada intuitivo.

Es fácil demostrar que las n! permutaciones forman grupo para esta composición, siendo la identidad E=(1,2,3,4,…, n) y el inverso la permutación que convierte las imágenes en orígenes. A este grupo lo llamaremos Grupo simétrico para {1,2,3,…, n} y lo representaremos como Sn.

¿Te apetecería comprobar composiciones de permutaciones con hoja de cálculo? Te damos unas ideas:

Puedes escribir en filas distintas, una debajo de la otra, las dos permutaciones G y H (en la imagen, filas 12 y 16) y después la composición de ambas (fila 20), que es la única que contendrá fórmulas. El resto de la hoja sólo contiene datos.

Es muy interesante estudiar qué fórmula podemos implementar en la fila 20 de la imagen. Explicaremos la primera celda, B20, y después bastará extenderla al resto de la fila. La fórmula adecuada es:

=ÍNDICE($B16:$J16;1;B12)

La función ÍNDICE elige en una lista el elemento que presenta un número de orden. En este caso la lista es la permutación H. De ahí que hayamos usado el rango $B16:$J16. Después hay que indicar la fila del rango. Como solo hay una fila, hemos escrito un 1. El siguiente parámetro es el número de orden, y aquí va a residir el truco: Hemos de elegir en H el elemento que ocupe el lugar que indica G en la misma columna. Insistimos en que esto, al principio, no es fácil. Hemos escrito en la fórmula “B12”, que es la primera imagen de G, un 6, luego deberemos ir a H y buscar el sexto elemento, un 8, y por eso en la celda B20 aparece ese 8.

Como puede que te siga costando, te ofrecemos esta hoja en la dirección

http://hojamat.es/blog/compopermu.zip

Como el grupo simétrico opera sobre un conjunto finito (cardinal n!), la aplicación reiterada de una sustitución consigo misma (potencia de la permutación) llevará a la repetición de resultados, es decir, a que dos potencias distintas sean equivalentes:

Pm=Pn

Si suponemos, por ejemplo que m<n, entonces esa igualdad, si le aplicamos la permutación inversa para simplicar, se convertiría en

Pn-m=Pk=E (identidad)

Toda permutación, aplicada un número determinado de veces, se convierte en la identidad.

El número mínimo para el que eso ocurre recibe el nombre de orden de la permutación. En los ejemplos de arriba, el orden de G es 4, y el de H es 3. Compruébalo. Esta idea nos servirá en lo que sigue.

Una propuesta: En la imagen se ha compuesto G consigo misma, y el conjunto total parece haberse dividido en tres subconjuntos, cada uno de los cuales parece que va “a su aire”, sin mezclarse con los otros. ¿Cuáles son?


En otra entrada los relacionaremos con los ciclos. Te puedes adelantar en su estudio.