jueves, 6 de julio de 2017

Números piramidales (5) Hexágonos


Quienes sigáis esta serie sobre números piramidales adivinaréis que los de tipo hexagonal son suma de los primeros números poligonales hexagonales, 1, 6, 15, 28, 45, 66, 91, 120, 153, 190, 231, 276, 325,… Ve acumulando sumas y obtendrás los piramidales hexagonales (PHEX):

1, 7, 22, 50, 95, 161, 252, 372, 525, 715, 946, 1222, 1547, 1925, 2360, 2856, 3417, 4047, 4750, 5530, 6391, 7337, 8372,… http://oeis.org/A002412

Con nuestra calculadora Calcupol puedes también recorrerlos. Descárgala desde

http://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#figurados

Fija el tipo en Piramidal de orden 6, escribe un 1 en pantalla y pulsa reiteradamente la tecla PROX. Así los obtendrás uno a uno. En la imagen hemos llegado hasta el 525.



Como todos los números piramidales, estos poseen una expresión polinómica que los genera. En este caso es

PHEX(n) = n(n + 1)(4n - 1)/6

Esta fórmula se obtiene particularizando para 6 la general de los piramidales:


Lo podemos comprobar, por ejemplo, para n=6, y nos queda:
PHEX(6)=6*7*23/6=161, como era de esperar.

Recurrencias

Estos números presentan varias formas de generación por recurrencia. La más práctica es la siguiente:

a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) + 4.

Podemos organizarlo según esta tabla, que iniciamos con 1, 7, 22. En cada fila añadimos un elemento nuevo calculado mediante la recurrencia:



Como suma

De diferencias de cuadrados

La definición de los números figurados mediante acumulación de otros más simples hace que sean frecuentes las generaciones mediante sumas de elementos. En el caso de los piramidales hexagonales basta acumular diferencias de cuadrados entre un número natural N y todos los menores que él. Lo puedes ver en esta tabla:


Por ejemplo, 50 es igual a 4^2-0^2+4^2-1^2+4^2-2^2+4^2-3^2

Se puede desarrollar algebraicamente, si recuerdas la fórmula para la suma de los primeros cuadrados:

S = n2-02+n2-12+n2-22+n2-32+…n2-(n-1)2 = n3-n(n-1)(2n-1)/6 = n(n+1)(4n-1)/6

Hemos desembocado en la fórmula de los piramidales hexagonales, lo que demuestra la propiedad.

De números naturales impares

Todos los números piramidales hexagonales son suma de triangulares impares. Así, el tercero a(3) = t(1)+t(3)+t(5) = 1+6+15 = 22

Algebraicamente:

1*2/2+3*4/2+5*6/2+…(2n-1)n, expresada como sumatorio queda:


Si desarrollas llegarás a la fórmula del piramidal hexagonal: PHEX(n)=n(n+1)(4n-1)/6

Relación con números combinatorios

El denominador 6 de la fórmula de los piramidales hexagonales sugiere su relación con números combinatorios de índice inferior igual a 3, y, en efecto, existen esas relaciones:


Lo desarrollamos:

C(n+2,3)+3C(n+1,3)=(n+2)(n+1)n/6+3(n+1)n(n-1)/6=n(n+1)/6*(n+2+3n-3)=n(n+1)(4n-1)/6

Es un simple identidad algebraica.

Otra relación:



Es también una identidad algebraica sencilla.

Fin de la serie

No podemos extender en demasía la exposición de números piramidales. Terminamos con una breve referencia a los octogonales.

Como todos los anteriores, los piramidales octogonales resultan de la suma de los poligonales del mismo número de lados. Por ejemplo, la pirámide octogonal de índice 5 resultará de la suma: 1+8+21+40+65=135

Los primeros octogonales son:

1, 9, 30, 70, 135, 231, 364, 540, 765, 1045, 1386, 1794, 2275, 2835, 3480, 4216, 5049, 5985, 7030, 8190, 9471, 10879,… http://oeis.org/A002414

Su fórmula: a(n)=n(n+1)(2n-1)/2

Por ejemplo, a(7)=7*8*13/2=28*13=364

En una próxima entrada justificaremos este tipo de fórmulas mediante interpolación polinómica sobre el conjunto {1, 2, 3, 4,…, n}

Fin de temporada

Con esta entrada damos fin a la temporada 2016-17 de este blog. Como todos los años, aprovecharemos el verano para resumir y ordenar materiales, así como actualizar otros pertenecientes a hojamat.es. Nos volveremos a encontrar en septiembre. Feliz verano.


lunes, 26 de junio de 2017

Cartesius (5) - Particiones (1)


El tema de las particiones ya ha sido tratado en este blog desde el punto de vista de las funciones generatrices, y también con la ayuda de nuestra herramienta “Cartesius”. Como esta ha sido mejorada sustancialmente, volveremos a tratar el tema incluyendo nuevas prestaciones.

Si deseas contar con las funciones generatrices recorre las entradas de este blog relativas al tema, a las que puedes acceder mediante la etiqueta “Funciones generatrices” en el panel derecho de este blog

No trataremos ese tema en esta nueva serie.

También puedes repasar el tema de particiones con la etiqueta correspondiente:


En esta serie repasaremos conceptos y se añadirán condicionamientos interesantes.

Particiones de un número

Se llaman particiones de un número natural N a las distintas formas de descomponerlo en sumandos enteros positivos sin tener en cuenta el orden y admitiendo repetición de sumandos.  Para no tener en cuenta el orden se puede exigir que los sumandos sean decrecientes en sentido amplio (o crecientes).  Así es más fácil representarlos.

Por ejemplo, el 9 se puede descomponer en estas sumas:

9,   8+1,  7+2,   7+1+1,   6+3,   6+2+1,   6+1+1+1,   5+4,   5+3+1, 5+2+2  5+2+1+1,   5+1+1+1+1,   4+4+1,  4+3+2,  4+3+1+1,   4+2+2+1,   4+2+1+1+1  4+1+1+1+1+1,   3+3+3,  3+3+2+1,   3+3+1+1+1, 3+2+2+2,   3+2+2+1+1,   3+2+1+1+1+1 3+1+1+1+1+1+1, 2+2+2+2+1, 2+2+2+1+1+1, 2+2+1+1+1+1+1, 2+1+1+1+1+1+1+1  1+1+1+1+1+1+1+1+1

Son 30 en total

Al número total de particiones de N lo representaremos por la función P(N). Por tanto la afirmación anterior se puede representar como P(9)=30. En muchos lenguajes de programación se representa como partitions(n), y si solo se desea contar las particiones, como #partitions(n).

Particiones con Cartesius

La nueva versión de nuestra herramienta la puedes descargar desde

http://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius

Con ella es más sencillo el desarrollo de particiones, gracias a la condición XRANGO, que recorre todos los números de sumandos de la partición. Hay que advertir que los desarrollos pueden resultar lentos, y casi imposibles para números grandes (Cartesius solo usa hasta 12 elementos), especialmente en LibreOffice Calc. Si se tiene a la vista el desarrollo se puede observar que la lentitud aparece en el tramo final, cuando casi todos los sumandos tienen el valor 1. En ese momento se puede adivinar el resultado aunque no haya terminado. Cada equipo y versión de hoja de cálculo tiene una forma de interrumpir la ejecución de una macro, pero a veces no es fácil encontrar ese dato. En el equipo del autor y con Excel 2010 funciona la combinación de pulsar la tecla de Windows y ESC.

Repasa en las entradas anteriores sobre Cartesius su funcionamiento básico, Debes abrir la hoja Planteamiento, borrar las condiciones si las hay y escribir las nuevas. Con el botón Iniciar obtienes las particiones. El planteamiento mínimo para una partición, como para el caso 7, es:


Si la usas, no tengas prisa, que tarda. Resultan 15 particiones:

Puedes comprobarlo en la página de WolframAlpha, que además te ofrece los diagramas de Ferrer



El lenguaje PARI también te puede servir para comprobar:

O bien consigues el desarrollo


O bien el número. Estudia el planteamiento de la primera línea:



Llegados a este punto, la pregunta es obvia, y es que para qué usar Cartesius si disponemos de estas herramientas. La respuesta está en los condicionamientos.

Particiones sobre números de un tipo determinado

Imagina que deseamos saber cuántas formas existen de expresar el número 12 como suma de primos. En este caso deberemos exigir que todos los sumandos en Cartesius sean de ese tipo. Sabemos que los primos inferiores a 12 son: 2, 3, 5, 7 y 11. Cinco en total. Aprovechamos que en Cartesius los sumandos se pueden definir mediante conjuntos (valores separados por comas, sin espacios), lo que facilita las cosas:



Declaramos un rango de sumas del 1 al 5, explicitamos cuáles son los sumandos y exigimos que la suma sea igual a 12. Resultan 6 posibilidades:



En este caso conocemos los sumandos, pero en otros no merece la pena buscarlos. Por ejemplo, deseamos conocer las particiones del número 1001 en suma de primos comprendidos entre 300 y 350. No esperamos más ni menos de tres sumandos, luego el planteamiento adecuado sería:



Esto es ya algo más complicado: XTOTAL=3 obliga a que sean tres sumandos, XT=300..350 establece el rango de los sumandos, y XT=FILTRO(PRIMO) indica que se seleccionan los sumandos primos, que en este caso son los de la imagen:



Obtendríamos dos sumas posibles:



Este ejemplo justifica el uso de Cartesius. Disponemos de los filtros PRIMO, PAR, IMPAR, CUADRADO, FIBONACCI y TRIANGULAR. En próximas versiones se podrían añadir más. Consulta las Instrucciones de Cartesius para más detalles. Puedes obtenerla en

http://www.hojamat.es/sindecimales/combinatoria/herramientas/cartesius.pdf

Otro ejemplo

Sabemos que todo número entero se descompone en suma de a lo sumo tres números triangulares, pero ¿de cuántas formas? Por ejemplo, el número 30. Planteamos:


Y se obtiene


Existe otro teorema similar que afirma que todo número se puede descomponer en a lo sumo cuatro cuadrados. Bastaría para comprobarlo cambiar XRANGO a 4 y efectuar un filtro de cuadrados. Lo probamos con el número 100:



Resultan cinco posibilidades (salvo el orden):



Es curioso que todos tienen sumandos repetidos.

Por hoy hemos desarrollado bastante. En la siguiente entrada expresaremos números en función de listas o de otros tipos, como factoriales, números de Fibonacci, impares y demás. Comprobaremos con estos últimos un teorema importante que ya tratamos en este blog.

jueves, 15 de junio de 2017

Descomposiciones múltiples del tipo x^2+ky^2

Últimamente nos han surgido cuestiones sobre descomposiciones en suma de cuadrados. Recordamos dos:

http://hojaynumeros.blogspot.com.es/2016/09/expresion-cuadratica-x2ky2-n.html
http://hojaynumeros.blogspot.com.es/2017/01/numero-de-descomposiciones-en.html

Siguiendo esta línea, hoy recorreremos aquellos números que se pueden descomponer en una suma del tipo x^2+ky^2, con k>1, x>0, y>0 de varias formas distintas. Expresado así, es un problema bastante general, que se presta a muchos casos y subcasos, por lo que sólo se desarrollarán algunos, con el fin de aprender a tratarlos y sacar alguna posible propiedad.

Hay un hecho que vale para todos ellos, y es que si N admite una descomposición de un tipo dado x^2+ky^2, con k>1, si lo multiplicamos por un cuadrado admitirá el mismo número de descomposiciones al menos, luego muchas soluciones que encontremos engendrarán otras al multiplicarlas por un cuadrado.

Caso k=2

Si deseamos encontrar todas las expresiones de un número de la forma x^2+2y^2, nuestra mejor herramienta es la que hemos presentado hace pocas semanas bajo el nombre de Cartesius, hoja de cálculo especializada en productos cartesianos condicionados. Puedes descargarla en versión para Excel y LibreOffice Calc, así como las instrucciones en la dirección

http://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius

En este caso bastará concretar: 2 sumandos, uno de ellos un cuadrado, el otro doble de un cuadrado, y que la suma de ambos sea igual al número propuesto. Por ejemplo, para saber  cuántas descomposiciones de este tipo permite el número 969, daríamos a Cartesius estas instrucciones:

xtotal=2
xt=1..33
x1=suc(n^2)
x2=suc(2*n^2)
suma=969

La primera exige que sean dos sumandos. La segunda fija un rango de búsqueda de 1 al 33, para que no se nos escape ningún cuadrado inferior a 969, y las siguientes determinan un sumando n^2 y otro 2*n^2. Así se recorrerán todas las posibilidades, que resultan ser cuatro. Si copias esas instrucciones en Cartesius (zona de condiciones) y pulsas el botón Iniciar obtendrás estos cuatro sumandos:



Traducidos a nuestra cuestión, equivalen a las igualdades

969=1^2+2*22^2=13^2+2*20^2=29^2+2*8^2=31^2+2*2^2

No seguiremos por ahí. Nos interesa buscar números con este tipo de propiedad, y podemos dejar Cartesius solo para comprobar. Nos pasamos al VisualBasic de las hojas de cálculo.

Es fácil diseñar una función que recorra todas las posibilidades de suma del tipo x^2+ky^2 para un número dado. El que tenga forma de función nos permite construir tablas para distintos valores, cosa imposible con Cartesius. Proponemos esta:

Public Function numsumacuad(n, k)  ‘Tiene dos parámetros, el número n y k
Dim x, p

p = 0 ‘Iniciamos el contador a cero
For x = 1 To Sqr(n - k) ‘Al estar x elevada al cuadrado, será inferior a una raíz cuadrada
If escuad((n - x ^ 2) / k) Then p = p + 1 ‘Si la diferencia dividida entre k es cuadrado, vale
Next x
numsumacuad = p ‘Contamos las veces
End Function

Esta función no se puede aplicar a 1, pero ya sabemos que no es suma de cuadrados no nulos.

Así podemos formar tablas como esta:


Vemos que entre 20 y 30 solo tienen solución 22, 24 y 27, y esta, doble. Todos los números que admiten al menos una de estas descomposiciones, se podrán representar como suma de tres cuadrados simétricos. Es sólo una curiosidad, pero atractiva. Así, 24=2^2+4^2+2^2

Este número de soluciones, asignando un 0 al 1, está publicada en http://oeis.org/A216278

Destacamos en negrita el intervalo entre 20 y 30.
0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 2, 0, 0, 0, 0, 0, 2, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 2…

Con la función numsumacuad podemos seleccionar aquellos números que admiten dos representaciones (al menos) distintas del tipo x^2+2y^2. Los primeros son estos:

27, 33, 51, 54, 57, 66, 81, 99, 102, 108, 114, 123, 129, 132, 153, 162, 171, 177, 187, 198, 201, 204, 209, 216, 219, 228, 243, 246, 249, 258, 264, 267, 291, 297, 306, 321, 323, 324, 339, 342, 354, 363, 369, 374, 387, 393, 396, 402, 408, 411, 417, 418, 432, 438, 451, 456, 459, 473, 486, 489, 492, 498,…

Todos los números de la sucesión son compuestos, pues Fermat, Euler y Gauss demostraron que los números primos sólo podían descomponerse como x^2+2y^2 de forma única, y no todos, porque deberían ser congruentes con 1 o 3 respecto al módulo 8.



En esta tabla figuran los primeros números primos que se pueden descomponer de la forma dada, y vemos que sus restos son 1 o 3 módulo 8. Un buen ejercicio es adivinar la descomposición en cuadrados mentalmente: 73=1^2+2*6^2, 89=9^2+2*2^2,…

En este tipo de búsquedas siempre recomendamos el lenguaje PARI como complemento o ampliación. En esta cuestión el código adecuado sería, por ejemplo:

for(n=3,500,p=0;for(x=1,sqrtint(n-2),if(issquare((n - x ^ 2) / 2),p+=1));if(p>1,print1(n,", ")))

Si cambiamos la condición p>1 por p==2 obtendremos los números que admiten exactamente dos descomposiciones del tipo que estamos estudiando:

27, 33, 51, 54, 57, 66, 81, 102, 108, 114, 123, 129, 132, 162, 177, 187, 201, 204, 209, 216, 219, 228, 246, 249, 258, 264, 267, 291, 321, 323, 324, 339, 354, 374, 393, 402, 408, 411, 417, 418, 432, 438, 451, 456, 473, 489, 492, 498,…

Vemos que faltan algunos, como el 99, que admiten más de una descomposición.
En todos estos números se dará la siguiente igualdad

N= a2+2b2=c2+2d2  que equivale a (a+c)(a-c)=2(d+b)(d-b)

De esa identidad se deduce que a y c han de tener la misma paridad, para que coincida con el múltiplo de 2 del segundo miembro, pero entonces (a+c)(a-c) será múltiplo de 4, lo que obliga a que también d y b tengan la misma paridad.

Lo puedes comprobar con los ejemplos.

Algunos de estos elementos son cuadrados

81, 324, 729, 1089, 1296, 2025, 2601, 2916, 3249, 3969, 4356, 5184, 6561, 8100, 9801,…

En ellos se cumple que n2=x2+2y2, o bien (n2-x2)/2=y2, es decir, que (n+x)(n-x)/2=y^2. Podemos interpretar que estos números generan triángulos de catetos enteros cuya área coincide con la de un cuadrado. Por ejemplo, tomamos 1089=33^2. Según nuestra hoja Cartesius admite cuatro descomposiciones del tipo deseado:



Si tomo la segunda, tendré: n=33, x=17, y=20, y se cumple 332=172+2*202, y aplicando los cálculos anteriores, se puede formar el triángulo de lados (33+17, 33-17), es decir 50 y 16, con área 50*16/2=400=202, que efectivamente, es un cuadrado.

Con el primero: (33+11,33-11) se convierte en los lados 44 y 22 de área 44*22/2=484=22^2.

Tipo x^2+3y^2

Este caso ofrece menor interés. Estos son los primeros números que admiten más de una descomposición de ese tipo:

Con más de un caso de sumas de cuadrados

28, 52, 76, 84, 91, 112, 124, 133, 148, 156, 172, 196, 208, 217, 228, 244, 247, 252, 259, 268, 273, 292, 301, 304, 316, 336, 343, 364, 372, 388, 399, 403, 412, 427, 436, 444, 448, 468, 469, …

Los puedes generar con este código PARI o con Cartesius o nuestra función en Visual Basic para Excel.

for(n=4,1000,p=0;for(x=1,sqrtint(n-3),if(issquare((n - x ^ 2) / 3),p+=1));if(p>1,write1("final.txt",n,", ")))

Por ejemplo, 469 se descompone como

469=13^2+3*10^2=19^2+3*6^2

Podemos seguir con otros números de casos. Por ejemplo, con tres o más descomposiciones están:

28, 52, 76, 84, 112, 124, 148, 156, 172, 196, 208, 228, 244, 252, 268, 292, 304, 316, 336, 364, 372, 388, 412, 436, 444, 448, 468, 496,…

Vemos que falta el 469, pero no el 468, que admite tres descomposiciones:
468=62+3*122=152+3*92=212+3*32

Puedes intentar descubrir casos llamativos. Un ejemplo: 2548 es el primero con nueve descomposiciones distintas. Insertamos el desarrollo con Cartesius. Las columnas X4 y X5 son los valores de x e y respectivamente:




Tipo x^2+4y^2

Su interés radica en que produce sumas simétricas de cinco cuadrados. No lo estudiaremos. Tan sólo un ejemplo:

464=10^2+10^2+8^2+10^2+10^2


Tipo 2x^2+3^y2

También este caso presenta el interés de obtener una suma de cinco cuadrados que sea simétrica y con bases alternantes. También damos un ejemplo:

365 =3^2+13^2+3^2+13^2+3^2

La reiteración mata el interés. Es mejor parar aquí y dejar abiertos otros caminos de investigación.

martes, 6 de junio de 2017

Números piramidales (4) Pentágonos


Esta es la cuarta entrada que dedicamos a los números piramidales. Puedes consultar las anteriores mediante la etiqueta "Números figurados".

Hoy desarrollaremos los piramidales pentagonales, que se forman añadiendo a la unidad (el vértice de la pirámide) distintos números pentagonales como si fueran cortes poligonales de la pirámide. Para nosotros es preferible ver los piramidales como suma de pentagonales sucesivos. Así, si estos forman la sucesión 1, 5, 12, 22, 35, 51, 70, 92, 117, 145,… http://oeis.org/A000326, los piramidales correspondientes coincidirán con sus sumas parciales: 1, 6, 18, 40, 75, 126, 196,…
Los primeros piramidales pentagonales son:

1, 6, 18, 40, 75, 126, 196, 288, 405, 550, 726, 936, 1183, 1470, 1800, 2176, 2601, 3078, 3610, 4200, 4851, 5566, 6348, 7200, 8125, 9126, 10206, 11368, 12615, 13950, 15376, 16896, 18513, 20230, 22050, 23976, 26011, 28158, 30420, 32800, 35301, 37926, 40678,…
http://oeis.org/A002411

Al igual que en entradas anteriores sobre el mismo tema, puedes usar nuestra calculadora calcupol para recorrerlos. Descárgala, si lo deseas, desde

http://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#figurados

Para recorrer la sucesión basta fijar el tipo en Piramidal y el orden en 5. Después se escribe un 1 en pantalla y cada pulsación de la tecla PROX nos devolverá un térmiuno nuevo de la sucesión.

En la imagen hemos llegado a 405:



Con la tecla ANT puedes retroceder, y entre ambas recorrer el rango de términos que desees.

Fórmula

Los números piramidales pentagonales (PPENT) siguen una expresión polinómica muy sencilla:



Esta fórmula se obtiene particularizando para 5 la general de los piramidales:



Por tanto, podemos afirmar que los piramidales pentagonales son los promedios entre el cuadrado y el cubo de un número. Por ejemplo:

405 es el piramidal pentagonal número 9, y se cumple que 405=(81+729)/2=810/2=405

Esto nos permite crear una tabla a partir de la sucesión de números naturales:



También la fórmula obtenida descubre que una pirámide pentagonal de lado k equivale a k veces el triangular del mismo lado. Por ejemplo, la pirámide de lado 6, 126, es seis veces mayor que 21, que es el triangular número 6.

Otra interpretación

El número piramidal pentagonal PPENT(n) equivale a la suma de los n+1 múltiplos menores de n. En efecto, esos múltiplos serán n*0, n*1, n*2,…n*n, y formarán progresión aritmética de diferencia n, luego su suma será (n*0+n*n)*(n+1)/2 = (n^3+n^2)/2, que es la expresión descubierta más arriba. Aquí tienes el esquema para PPENT(7)=196

Si extraemos factor común el 7, nos queda la suma 0+1+2+3+…que es un número triangular, tal como vimos unos párrafos más arriba. Esto nos descubre otra interpretación, y es que un número piramidal pentagonal equivale a un “prisma” triangular de la misma altura.

Expresado como sumatorio:



Recurrencia

Estos números presentan tantas formas de generación que el procedimiento recurrente no es muy necesario. No obstante, existen varias fórmulas de recurrencia. La más simple es

ppent(n) = 3*ppent(n-1) - 3*ppent(n-2) + ppent(n-3) + 3.

Es una recurrencia de tercer orden no homogénea. Se puede demostrar con un simple desarrollo algebraico, si recordamos que ppent(n)=(n^3+n^2)/2.

Desarrollamos:

Ppent(n)=3((n-1)^3+(n-1)^2)/2-3((n-2)^3+(n-2)^2)/2+((n-3)^3+(n-3)^2)/2+3

Si nos da pereza simplificar, podemos acudir a Wiris, wxMaxima u otro similar. Usamos el segundo y obtenemos:


Como el resultado es (n^3+n^2)/2, hemos demostrado la recurrencia. No es muy útil.

Cuestiones combinatorias

Es muy ilustrativo el estudio de algunas relaciones entre temas propios de números enteros con otros combinatorios. Muchas sucesiones poseen sentidos bastante simples si las estudiamos desde ese punto de vista. Los piramidales pentagonales también las admiten.

Bolas y cajas

Imagina que disponemos de n bolas que deseamos guardar en n cajas, pero con la caprichosa condición de que solo usaremos 2 de ellas, dejando vacías las demás. En ese caso, el número de formas de guardar esas bolas es PPENT(n-1)
Así que decidimos usar solamente dos cajas. En la imagen nos hemos decidido por la 3 y la 6:


Nos comprometemos a guardar las n bolas en esas dos cajas. Es evidente que tenemos n-1 posibilidades, si no deseamos que una quede vacía: 1+(n-1), 2+(n-2), 3+(n-3), …(n-1)+1

Por otra parte, la elección de las cajas, que en nuestro ejemplo eran la 3 y la 6, se puede efectuar de C(n,2) formas, combinaciones de n cajas tomadas de 2 en 2, es decir n(n-1)/2

Multiplicamos las formas de elegir dos cajas por las de rellenarlas, y tenemos:
P= n(n-1)/2*(n-1)=(n^3-2n^2+n)/2

Esta expresión coincide con PPENT(n-1)=((n-1)^3+(n-1)^2)/2=(n^3-2n^2+n)/2

Cadenas de caracteres

En esta cuestión imaginamos que formamos todas las palabras posibles de tres caracteres en un alfabeto de n caracteres, y consideramos iguales entre sí aquellas palabras que contienen los mismos caracteres, pero invertidos.

Por ejemplo, supongamos las cinco letras A, B, C, D, E agrupadas en palabras de tres AAA, ABC, CBD,… y consideramos idénticas las inversas entre sí, como CBD, que la considaremos equivalente a DBC.

Con estas condiciones, el número de palabras con un alfabeto de n caracteres será PPENT(n).

Tampoco es difícil de razonar: El número total de palabras será n*n*n, pero estas se dividen en dos grupos:


  •  Simétricas (capicúas o palindrómicas) que se contarán una vez. Su número es n*n=n^2 (el tercer elemento está obligado)
  •  No simétricas, cuyo número se ha dividir entre 2 para eliminar las palabras simétricas entre sí. Como su número es (n*n*n-n*n), al dividir entre 2 quedará (n*n*n-n*n)/2=n^2(n-1)/2

Sumamos ambos casos:

P=n^2+n^2(n-1)/2 = n^2(2+n-1)/2 = n^2(n+1)/2 = (n^3+n^2)/2=PPENT(n)

Así hemos demostrado la equivalencia. Lo vemos con el caso n=5:

Con un alfabeto de 5 caracteres se forman 5*5*5=125 palabras, de las que 5*5=25 son capicúas, y 125-25=100, no capicúas. Estas segundas hay que contarlas una vez, luego dividimos entre 2, quedando 50. Sumamos ambos casos y obtenemos 50+25=75, que es el quinto número piramidal pentagonal.

lunes, 29 de mayo de 2017

Cartesius(4) Combinaciones


Llegamos a la cuarta entrada de esta serie sobre la herramienta Cartesius. Las anteriores las puedes leer previamente si eliges la etiqueta Cartesius en el lateral de este blog:


Recordamos también la dirección de descarga:

http://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius

Combinaciones

Cartesius maneja de igual forma variaciones que combinaciones. La única diferencia es que en estas hay que añadir CRECIENTE, para que el orden no intervenga y cada arreglo sea en realidad un conjunto. Si además se desea que no existan repeticiones, se añade NO REPITE.

Combinaciones ORDINARIAS

Ya lo hemos explicado: basta añadir CRECIENTE y NO REPITE  a las condiciones. Por ejemplo, así construiríamos las combinaciones de 7 elementos tomados de 5 en 5:


XTOTAL=5 indica que las combinaciones constarán de cinco elementos cada una, XT=1..7 define los elementos del conjunto base, Y CRECIENTE y NO REPITE ya están explicados.

Te resultarán 21, según la clásica fórmula

que en este caso da C7,5=7!/(5!2!)=21. Son estas:



Es un tema sencillo, que podemos usar para comprobar desarrollos construidos manualmente.

Combinaciones con repetición

Es evidente que si suprimimos la condición NO REPITE resultarán combinaciones con repetición.

Si combinamos 6 elementos tomados de 3 en 3, de forma creciente y pudiendo repetir elementos, nos resultarán combinaciones con repetición. Usamos estas condiciones:



Resultan 56 combinaciones. Aquí vemos las primeras:



Este resultado está de acuerdo con la fórmula general:


En efecto, CR6,3 = 8!/(3!5!) = 8*7*6/6 = 56

Se comprende que esta hoja es muy útil para comprobar cálculos efectuados con otras herramientas. Pero también permite investigar condiciones nuevas. ¿Qué hubiera ocurrido si añadimos la palabra REPITE? Una primera idea es que no se alteraría nada, que resultarían combinaciones con repetición, pero no es exactamente así. Si desarrollamos con esa nueva condición el resultado no es ya 56, sino 36. Como habrás comprendido, ahora sólo se generan arreglos que tengan repetición con toda seguridad, mientras que antes entraban todos, los que contenían repeticiones y los que no. La fórmula en este caso sería la diferencia entre el número de combinaciones con repetición y las que no la admiten:



En este ejemplo los cálculos serían Crep6,3=8!/(3!5!) - 6!/(3!3!)=56-20=36
Como en los ejemplos anteriores, se pueden añadir otros condicionamientos. Podemos fijar una cuenta de elementos, pero sólo en el caso de combinaciones con repetición. Imaginemos que en el ejemplo anterior deseamos que se permitan repeticiones y que el elemento 4 se repita dos veces. Quedarían las condiciones así:



El resultado sería



Es fácil de entender que sólo resulten cinco: el par 4 4 acompañado de 1, 2, 3, 5 o 6.

Sumas

Un tipo especial de combinaciones, al que quizás volvamos más adelante son los desarrollos de un número en sumas según una lista

 (ver http://hojaynumeros.blogspot.com.es/2010/02/frobenius-y-los-mcnuggets.html)

Se trata de partir de una lista concreta de números, por ejemplo los primeros cinco primos, y encontrar la forma de descomponer otro número como suma de ellos. En Cartesius puedes efectuarlo con todos o con parte de ellos. Por ejemplo, ¿se puede descomponer el número 28 en suma de los siete primeros primos 2, 3, 5, 7, 11?

Para ello usaremos una condición nueva, ETIQ, que sustituye los números que se van a combinar por otros predefinidos en la hoja Almacén de datos. En otro momento lo explicaremos con más detalle. En este caso bastaría escribir XT=ETIQ(PRIMO) para que los elementos a combinar pasaran de 1, 2, 3, 4 y 5 a los primos 2, 3, 5, 7 y 11.



Las condiciones completas serían:


Ya podrás interpretarlas, al menos parcialmente. Nos obligan a: combinar cinco números tomados de 5 en 5, que han de ser primos y sumar 28. Lo desarrollaremos de forma creciente para evitar soluciones idénticas pero con distinto orden.

El resultado es


Vemos que existen cuatro formas de engendrar el 28 con números primos (con repetición). Si añadiéramos la condición NO REPITE, sólo obtendríamos la segunda: 2+3+5+7+11. ¿Y con menos sumandos? Sustituimos XTOTAL=5 por XRANGO=5, a ver qué ocurre.

Lo programamos y descubrimos cuatro soluciones más, porque XRANGO recorre las posibilidades de suma desde 1 sumando hasta 5:


Por terminar esta presentación rápida, comprobamos que Cartesius no sólo puede calcular la suma, sino, en casos preparados, descubrir su naturaleza. Si en lugar de SUMA=28 hubiéramos escrito SUMA:PRIMO, se desarrollarían todas las sumas entre 2, 3, 5, 7 y 11 cuyo resultado es primo. Obtenemos 76 posibilidades, que van desde las más simples, como 2+3 o 2+5 hasta la de mayor suma, 7+7+11+11+11 =47.

Si impedimos que se repitan sólo obtendríamos 12, contando las sumas unitarias:


Este tema de descomposiciones en sumas da para otras entradas. En concreto, dedicaremos una a particiones de un número y otra a sumas especiales.