Collares bicolores – Conteo total

Seguimos con el tema de collares, pero sólo aquellos que están sometidos a giros planos, sin tener en cuenta simetrías. Hemos indicado que este otro caso, algo más complejo, lo dejamos como complemento.

Descubrimos en la entrada anterior que para n=7 existían 20 collares distintos, e igualmente se podría haber razonado que para n=6, caso que hemos estudiado exhaustivamente, serían 14.

Si consultas http://oeis.org/A000031 verás que los resultados son

N	0	1	2	3	4	5	6	7	8	9	10	11
C	1	2	3	4	6	8	14	20	36	60	108	188

Existe una fórmula, que puedes consultar en http://mathworld.wolfram.com/Necklace.html
para calcular esos números sin acudir a un análisis individual de cada collar. Es esta, adaptada al caso de 2 colores:

La variable d recorre todos los divisores de n desde 1 hasta n, y  φ(d)  es la función indicador de Euler que indica el total de números menores que d y primos con él incluido el 1.

Apliquemos la fórmula al caso 6:

Divisores: 1,2,3,6
Indicadores: φ(1)=1, φ(2)=1, φ(3)=2, φ(6)=2
Total: C=(1*26+1*23+2*22+2*21)/6=(64+8+8+4)/6=84/6=14, como ya sabíamos.

En el caso de 7:

Divisores:1,7
Indicadores: φ(1)=1, φ(7)=6
Total: C=(1*27+6*21)/7 = (128+12)/7 = 140/7 = 20, que también coincide.

Y aquí acabamos. El resto es cosa tuya. Puedes llegar por este camino hasta el Teorema de Enumeración de Polya.

Collares bicolores – Conteo de collares

Los conceptos de órbita (collares en nuestro caso) y de estabilizador están relacionados por un cálculo. Si representamos como |C| al cardinal de un conjunto C, tendremos que

Si G actúa sobre un conjunto C, para cada elemento x de C se cumple que |Orb(x)|=|G|/|est(x) |

Es decir, el cardinal de la órbita de x equivale al cociente del cardinal del grupo que actúa sobre él y el de su estabilizador. 

Así, en el ejemplo de la imagen, el grupo de giros tiene cardinal 6 y en párrafos anteriores vimos que su estabilizador tiene 3, luego su órbita contendrá 6/3=2 elementos, el de la imagen y su simétrico intercambiando negras y blancas.

En los collares con n primo no existen subgrupos propios, luego todos los collares tendrán n elementos equivalentes. Estudia los collares de siete elementos y lo comprobarás.
 
Hay una forma de contar todos los collares mediante órbitas y estabilizadores. Se trata del lema o teorema de Burnside:

Sea G un grupo que actúa sobre un conjunto C, y llamemos r(g) al número de elementos de C que quedan invariantes respecto a g (x=g(x)). En ese caso el número de órbitas en C viene dado por 

Puedes consultar la demostración en textos adecuados.

Lo aplicamos al caso de collares de 6 cuentas, 3 negras y 3 blancas. Contamos los puntos fijos de cada giro:

e: Todos los elementos son fijos, contamos 20 elementos
g₁, g₃, g₅: No tienen elementos fijos
g₂, g₄: Cada uno presenta 2 elementos fijos. Contamos 4

Aplicamos el teorema de Burnside: O=(20+0+4)/6 = 4 órbitas, tal como sabíamos desde el principio. Encontramos cuatro collares distintos.

En el caso que propusimos de 2 cuentas negras y 4 blancas tendríamos:

Número total de elementos: 6!/(2!.4!)= 15 permutaciones
e: Todos los elementos son fijos, contamos 15 elementos
g₁, g₂, g₃, g₅: No tienen elementos fijos
g₃: Presenta 3 elementos fijos.

Luego O=(15+0+3)/6 = 3 órbitas, que se corresponden con los propuestos en nuestra primera entrada.

Puedes estudiar el caso sencillo de collares de 4 cuentas. Desarrolla por separado los casos de 3 de un color y 1 del otro o el de 2 colores de cada clase. Te deben resultar un collar del primer tipo y dos del segundo. Dibújalos si quieres.

En el caso de 7, al ser primo, no hay puntos fijos y el cálculo se reduce a dividir entre 7 el número de permutaciones. Por ejemplo, si C_7,4 =C_7,3 = 35, el número de collares será igual a 35/7 = 5. En el caso de 5 y 2 serían 3=21/7

Ahí los tienes todos

Son 10 en total, y si le añadimos los que resultan de intercambiar negras y blancas, se convierten en 20. Este resultado y otros similares los puedes encontrar en http://oeis.org/A000031

Collares bicolores – Órbitas y estabilizadores

Llamemos C al conjunto de permutaciones de n cuentas, r de ellas de color negro y s de color blanco, con r+s=n. En total existirán C_n,r = C_n,s elementos. Con las condiciones que se impusieron en la anterior entrada en la definición de un collar se advierte que vamos a someter a ese conjunto C a una serie de giros, y que consideraremos pertenecientes a un mismo collar a las permutaciones que se pueden convertir una en la otra mediante un giro.

Concretamos:

Llamemos g₁ al giro que traslada cada cuenta al lugar de su siguiente en el sentido de las agujas del reloj. En términos de permutaciones equivaldría a mover cada elemento un lugar y al último convertirlo en primero. Así, en la permutación XOXXO el efecto de g₁ sería OXXOX. Se puede formalizar más, pero así se entiende bien. Esta definición es independiente del número de cuentas.

Igualmente, llamaremos g₂ a la composición de g₁ consigo mismo, es decir g₂(x)= (g₁.g₁)(x)=g₁(g₁(x)). En la práctica equivaldría a un giro doble. De igual forma podemos definir el giro triple g₃(x)= (g₁.g₂)(x)=g₁(g₂(x)) y así sucesivamente hasta llegar a g_n que equivaldría a la transformación identidad e.

Hemos definido en realidad un grupo G (puedes demostrarlo), el de los giros en C, subgrupo del de sustituciones de C. Formalizamos la idea:

Diremos que un grupo G actúa sobre un conjunto C cuando para cada elemento g de G se define una operación externa g(x)=y, donde x e y son elementos del conjunto C, tal que cumpla e(x)=x y además (g.f)(x)=g(f(x)), ambas para todo x de C. En nuestro caso de giros sobre permutaciones se cumplen ambas, luego diremos que G actúa sobre C. La imagen intuitiva es que se hacen girar los collares de todas las formas posibles.

Dos conceptos importantes se desprenden de esa definición

Órbita

Llamaremos órbita o trayectoria de un elemento x del conjunto C sobre el que actúa G, al conjunto orb(x) formado por todas las imágenes posibles de x mediante los elementos de G. En la imagen tienes un ejemplo de órbita según los giros en un conjunto de seis cuentas.

 Las órbitas no son subgrupos, sino subconjuntos de C. Si vuelves a leer desde el principio, entenderás que la definición de “collar” coincide con la de “órbita”

Los collares que hemos definido coinciden con las órbitas de las permutaciones si sobre ellas actúan los giros.

Hay otra definición de collar en la que entran las simetrías, pero lo dejamos por si deseas ampliar el tema.

Estabilizador

Para una permutación cualquiera x, llamaremos estabilizador de x est(x) al subgrupo de giros que la dejan invariante, es decir, todos los g tales que g(x)=x.

Es fácil demostrar que est(x) constituye un subgrupo.

Así, el estabilizador de la permutación de la imagen está formado por el subgrupo {e, g₂, g₄}. Si no ves simetrías aparentes en una permutación, es fácil que su estabilizador sea {e}, sólo la identidad.

Repasa algunos ejemplos y verás que es fácil encontrar su estabilizador.

¿Por qué hablamos de estabilizadores? Porque nos sirven para contar órbitas o, lo que es lo mismo, collares.

Lo dejamos para otro día. Si quieres avanzar en el tema, busca por ahí el lema de Burnside.

Collares bicolores - Introducción

Supongamos que en un hilo cerrado ensartamos n cuentas para formar un collar, r de ellas de color negro y s de color blanco, con r+s=n. Lo dejamos sobre una mesa y permitimos todos los giros posibles, lo que evidentemente deja invariante la estructura de las posiciones mutuas de las blancas y las negras. Por razones de simplicidad (aunque de hecho se hace y está estudiado) prohibiremos cualquier movimiento del collar fuera de la mesa (en el espacio tridimensional)

¿Cómo se estudiarían matemáticamente estas estructuras en forma de collar?

La primera idea es la de que se trata de permutaciones circulares, pero el problema es algo más complicado. Lo abordamos.

Consideremos todas las permutaciones posibles de r negras y s blancas. Sabemos que su número es  C_n,r=  C_n,s = n!/(r!.s!)  Así, si usamos 3 negras y 3 blancas obtendríamos C_6,3= 6!/(3!*3!)= 20 permutaciones. Si representamos las blancas con una O y las negras con X, resultarían las siguientes (se puede ignorar por ahora la última columna):

O	O	O	X	X	X		C1
O	O	X	O	X	X		C2
O	O	X	X	O	X		C3
O	O	X	X	X	O		C1
O	X	O	O	X	X		C3
O	X	O	X	O	X		C4
O	X	O	X	X	O		C2
O	X	X	O	O	X		C2
O	X	X	O	X	O		C3
O	X	X	X	O	O		C1
X	O	O	O	X	X		C1
X	O	O	X	O	X		C2
X	O	O	X	X	O		C3
X	O	X	O	O	X		C3
X	O	X	O	X	O		C4
X	O	X	X	O	O		C2
X	X	O	O	O	X		C1
X	X	O	O	X	O		C2
X	X	O	X	O	O		C3
X	X	X	O	O	O		C1

Intenta imaginar cada permutación como circular y agrupa aquellas que representen el mismo collar cuando se les deja girar libremente. Puedes imaginarlas situadas sobre la esfera de un reloj con la primera cuenta en “las doce” y avanzando en el sentido de las agujas. Así lo haremos a partir de ahora.

Es un ejercicio muy bueno para dominar el tema. En la última columna de la tabla se han destacado con los símbolos C1, C2,… los distintos collares que se pueden considerar.

Han resultado tres tipos de collares C1, C2 y C3 representados cada uno por 6 permutaciones y luego otro tipo, el C4, representado por dos. Los dibujamos:

Si analizas un poco este conjunto adivinarás por qué el cuarto tipo contiene sólo 2 permutaciones y los otros 6. Por ahora lo dejamos aquí y en la siguiente entrada lo interpretaremos en términos de órbitas en un conjunto sobre el que actúa un grupo.

Mientras tanto, intenta estudiar el mismo tipo de collar pero con sólo dos cuentas negras y cuatro blancas.

¿Cuántas permutaciones forman cada uno de los tres tipos de collar? ¿Por qué sólo existen tres tipos?

Parientes de Ruth y Aaron

 (Con esta entrada participamos en la edición 2.2 del Carnaval de Matemáticas que tendrá lugar del 14 al 25 de Marzo en Gaussianos)


Hace unas semanas, el blog NumberADay presentaba los números 714 y 715 como integrantes de un par del tipo Ruth-Aaron, porque ambos son consecutivos y comparten el mismo valor en su logaritmo entero. Estudiamos esta función hace meses en una entrada de nuestro blog. En ella explicábamos que el logaritmo entero de un número se define mediante la suma de todos sus divisores primos contando su multiplicidad. Se representa como sopfr(n). Pues bien, sopfr(714)=2+3+7+17=29 y sopfr(715)=5+11+13=29

Puedes buscar en la Red este concepto, y consultar en http://oeis.org/A039752 la lista de los primeros números que forman pares de Ruth-Aaron.

Podíamos buscar otros números con una propiedad similar y ver si ya están estudiados. Puedes usar la implementación de la función sopfr(n) que ya hemos publicado.

La primera idea sería buscar números que se diferenciaran en 2 unidades y compartieran la misma suma de factores primos. Existen, y los primeros son estos (escribimos el más pequeño del par): 10, 16, 30, 154, 250, 1428, 1896, 2660, 3040, 3724, 4982,…Todos parecen ser pares. ¿Podrías encontrar el siguiente?¿Habría alguno que fuera impar? Desconozco la respuesta a la segunda pregunta.

También existen pares diferenciados en 3, como 847 y 850, ambos con suma 29, como en el primer ejemplo. Y con otras diferencias, como 931 y 935, de diferencia 4, por lo que no parece tener interés seguir investigando por ahí.

Podíamos buscar diferencias más sofisticadas (productos no, ¿por qué?). Una idea sería sumar al más pequeño su propio logaritmo entero. Pues bien, eso ya está estudiado. Por ejemplo, la suma de los divisores primos de 60 (2,2,3,5) es 12. Si sumamos 12 a 60 nos resulta 72, y sus divisores 2+2+2+3+3 también suman 12. Puedes estudiar estos números en http://oeis.org/A050780

También podíamos ensayar el sumarle el número de divisores primos (con multiplicidad), es decir, su redondez  o "multiprimalidad" (función bigomega). Por ejemplo, 45 tiene redondez 3, porque sus divisores primos son tres: 5, 3 y 3, con suma 11. Añadimos esa redondez a 45 y nos resulta 48, cuyos factores primos son 2, 2, 2, 2, 3, cuya suma también es 11.

Aquí tienes los primeros (también sólo escribimos el más pequeño del par): 5, 10, 45, 60, 128, 231, 308, 470, 847…¿Sabrías encontrar el siguiente? Deberás usar tus propios métodos, porque no hemos visto publicados estos números.

Su propiedad se puede expresar así:

(n + bigomega(n) = m) y (sopfr(m) = sopfr(n))

Si llamamos función omega(n) al número de factores primos de n sin contar multiplicidades, ¿qué números cumplirían esta condición?

 (n + omega(n) = m) y (sopfr(m) = sopfr(n))

¿Se te ocurren propuestas parecidas? ¿Habrá más parientes de Ruth y Aaron?

Primos y potencias de 2

Parece que le hemos tomado cariño a estos dos entes. Después de varias entradas algo extenuantes, aquí tienes una demostración que no es muy complicada:

Para todo número primo p a partir del 5, la expresión 2^p-2 es divisible entre p

(a) Es una consecuencia inmediata de un famoso teorema ¿cuál? Te damos un par de minutos para acordarte.

(b) Lo que no es tan inmediato es que también lo es entre 6p (de ahí lo de comenzar en 5). Tienes una pista en las entradas anteriores de este blog.

(c) Y menos inmediato: Siendo p primo, 2^p-2 se puede representar como la suma de p-1 múltiplos de p iguales dos a dos.

(d) Y menos todavía: Si esos múltiplos los divides entre p obtienes el número de collares posibles formados con p cuentas, algunas de ellas negras y otras blancas. Pero esto es mejor dejarlo para otra ocasión. Prometemos su estudio.

La familia de las sigmas (2)

La imagen de la anterior entrada está construida con los cuadrados de todos los divisores del número 20. Es lo que llamaremos función sigma_2 del número 20, mientras que reservamos la palabra sigma a secas (o sigma_1) a la suma de todos los divisores.

Todo esto es una parte de la definición general:

Es decir, que sigma_k es la suma de las potencias k-ésimas de todos los divisores de N. En la imagen propuesta N=20. La altura de la imagen es 42, suma de todos los divisores de 20, y los cuadrados forman el número 546, que equivale a sigma_2(20)

En la teoría elemental de la Divisibilidad estudiamos una fórmula práctica para el cálculo de sigma_1:

donde p_i son los factores primos de N.

Y es fácil demostrar con el mismo proceso que la fórmula para sigma_k es

Si deseas usar una hoja de cálculo, las funciones sigma se programan con unas pocas líneas:

public function sigma(n,k)
dim i,s

s=0
for i=1 to n
if n/i=n\i then s=s+i^k
next i
sigma=s
End function

¿Qué números tienen la propiedad de que la pila de cuadrados de sus divisores se puede convertir en un rectángulo?

Por una parte basta observar la figura para comprender la siguiente desigualdad:

Luego el rectángulo ha de tener una base menor que N.

Si programamos el cociente entre sigma_2 y sigma_1, nos encontraremos algunos números en los que el cociente es un número entero menor que N y esos serán los que presenten la propiedad pedida:

N	Sigma_1	Sigma_2	Cociente
1	1	1	1
2	3	5	1,67
3	4	10	2,5
4	7	21	3
5	6	26	4,33
6	12	50	4,17
7	8	50	6,25
8	15	85	5,67
9	13	91	7
10	18	130	7,22
11	12	122	10,17
12	28	210	7,5
13	14	170	12,14
14	24	250	10,42
15	24	260	10,83
16	31	341	11
17	18	290	16,11
18	39	455	11,67
19	20	362	18,1
20	42	546	13
21	32	500	15,63
22	36	610	16,94
23	24	530	22,08
24	60	850	14,17
25	31	651	21
26	42	850	20,24

En la tabla hemos destacado los números con cociente entero: 1, 4, 9, 16, 20, 25…

La lista se completa así:

1, 4, 9, 16, 20, 25, 36, 49, 50, 64, 81, 100, 117, 121, 144, 169, 180, 196, 200, 225, 242, 256, 289, 324, 325, 361, 400…

En ella están los cuadrados perfectos. Puedes intentar demostrar que en todo cuadrado perfecto el cociente M es entero.


Basta reducirlo a cocientes y productos de diferencias de potencias pares que son siempre divisibles, y se desemboca en un cociente de sumas de potencias impares que también presenta divisibilidad. No indicamos más.

Los restantes elementos de la lista son números que no están libres de cuadrados, pero no están todos, porque por ejemplo 63=3²*7 y no está.

No he encontrado en la lista ningún número libre de cuadrados, pero no sé encontrar la causa. Si alguien lo sabe, le agradeceríamos que nos informe.