lunes, 18 de septiembre de 2017

Cartesius(6) – Particiones (2)

Condicionamientos sobre las particiones de un conjunto

En la entrada anterior de esta serie (http://hojaynumeros.blogspot.com.es/2017/06/cartesius-5-particiones-1.html) procedimos a crear particiones en un número, y en algunas condicionamos los sumandos, para que fueran primos, triangulares o cuadrados.  Ahora condicionaremos los resultados, y más adelante repasaremos los condicionamientos clásicos.

Condicionamientos sobre resultados

Las particiones de un número las hemos definido a partir de todas las sumas posibles, pero estas podrían ser condicionadas, en el sentido de suprimir algunas de ellas. Lo vemos con un ejemplo:

¿De cuántas formas podemos descomponer el número 7 en particiones con los dos sumandos menores iguales? 

Si no condicionamos los sumandos, existen, según vimos, 15 particiones. Al obligar a que los dos menores sean iguales, restringiremos ese número. Podemos plantearlo así:

XRANGO=7
XT=1..7
CRECIENTE
ES X1=X2
SUMA=7

Es el mismo planteamiento de la entrada anterior sobre el tema de particiones, con el añadido ES X1=X2, que obliga a que los dos primeros sumandos sean iguales. Como hemos decidido que los arreglos sean crecientes, estos dos primeros serán también los menores. El resultado es:



Resultan ocho particiones en lugar de 15.

Podemos introducir muchos más condicionamientos: fijar la suma parcial de los tres menores o exigir que el tercer sumando sea mayor que el segundo, y otros parecidos.

Particiones condicionadas

Todos estos condicionamientos se suelen expresar como función así:
P(N/condicionamiento)
De esta forma, el anterior ejemplo se escribiría como P(7/x1=x2)

Otro ejemplo

Imaginemos que deseamos que el tercer sumando sea a su vez suma de los dos anteriores. Procederíamos así:

XRANGO=7
XT=1..7
CRECIENTE
ES X3=X1+X2
SUMA=7

Al desarrollar veríamos que es un ejemplo sin interés, porque sólo existe una suma así (siendo sumandos crecientes)



En efecto, si los valores iniciales son 1, 1, 2, ya no admiten para suma 7 nada más que un 3.

Condicionamientos clásicos

Ya vimos en entradas anteriores sobre particiones que históricamente se han planteado algunos condicionamientos especiales a las particiones. Los recorremos de nuevo:

Función de partición Pk(N) 

Es la misma función P(N) condicionada a que sólo intervenga un número K de sumandos:

Pk(N)= P(N / k sumandos): Particiones con un número k de sumandos fijado.
Con la hoja Cartesius es fácil programar esta función, ya que basta con definir XTOTAL=K, dejando el resto de condiciones igual.
Por ejemplo, evaluamos las particiones del número 12 en 4 sumandos, es decir p4(12):

xtotal=4 
xt=1..12 
creciente 
suma=12


Resultan 15 particiones.

Función de partición Q(N)

Como la anterior, cuenta el número de particiones, pero en este caso se exige que los sumandos sean todos distintos. Por ejemplo, el entero 7 admite las siguientes particiones como números distintos: 7 = 6+1 = 5+2 = 4+3 = 4+2+1, luego Q(7)=5

Euler demostró que esta función coincide con el número de particiones de n en partes impares. Lo veremos más adelante.

La programación de esta función se consigue añadiendo la condición NO REPITE, para que todos los sumandos sean iguales. En el caso del 7 podríamos escribir:

xrango=7
xt=1..7
suma=7
creciente
no repite

Tendríamos el resultado siguiente:



Sólo son posibles las cinco particiones.

Particiones en partes impares P(N/Impar)

Introducimos este condicionamiento porque da lugar a un resultado obtenido por Euler:

El número de particiones de un número en sumandos distintos coincide con el de particiones en sumandos impares

Con Cartesius el planteo se limita a exigir que los sumandos sean impares. Basta condicionar los sumandos como una sucesión del tipo 2*n-1:



Obtenemos cinco particiones, el mismo número que nos dio el de sumandos distintos.



Podíamos haber usado un filtro, para que los sumandos sean impares:



Resultaría más rápido que el planteamiento anterior. Por último, otra posibilidad es definir los sumandos como un conjunto:


También es más rápido.

En otra futura entrada seguiremos condicionando las particiones de un número.

miércoles, 6 de septiembre de 2017

Números figurados e interpolación polinómica



Las entradas sobre números piramidales publicadas en este blog contenían siempre una fórmula polinómica para expresar cada término de la sucesión. Por ello parece conveniente presentar un método general para la obtención de esas fórmulas. Disponemos para ello de la teoría de la interpolación polinómica, en la que elegiremos el método de Newton, y una hoja de cálculo que nos facilitará las cosas.

Teoría

Los conceptos y métodos de la interpolación polinómica los puedes encontrar en cualquier texto del primer ciclo de estudios universitarios. Todos se basan en el cálculo con diferencias sucesivas. En nuestro caso nos limitaremos a la suma de funciones enteras definidas sobre los primeros números naturales, lo que simplifica mucho los cálculos.

Por ejemplo, imaginemos que deseamos sumar los primeros números oblongos: 1*2, 2*3, 3*4, 4*5, 5*6,…o bien, 2, 6, 12, 20, 30,…Queremos obtener una expresión para 2+6+12+20+30+…

En las técnicas de interpolación que usaremos, la primera operación es la obtención de las diferencias sucesivas, es decir, diferencias entre los elementos, diferencias entre las diferencias, y así sucesivamente hasta (en el caso polinómico) que sean todas iguales. Lo intentamos con el ejemplo. En primer lugar encontramos las sumas parciales de oblongos: 2, 2+6=8, 2+6+12=20,…que serían 2, 8, 20, 40, 70, 112, 168, 240,…

Lo puedes organizar con una hoja de cálculo:



La siguiente imagen, tomada de nuestra hoja newton.xls, puedes entender muy bien el concepto de diferencias sucesivas. En primer lugar hemos escrito nuestra sucesión: 2, 8, 20, 40, 70, 112, 168,…Después hemos ido restando cada elemento con el siguiente: 6, 12, 20, 30, 42, 56,…(resultan ser los oblongos). A continuación hemos restado esas diferencias: 6, 8, 10, 12, 14,…entre sí, y al final en otra resta, hemos llegado a 2, 2, 2,…Esa es la señal de que esos números siguen una expresión polinómica, el que las diferencias se hagan iguales y las siguientes nulas.



Como aquí las diferencias constantes se alcanzan en tres pasos, la fórmula que buscamos será un polinomio de tercer grado. Lo repasamos en teoría:

Fórmula de interpolación de Newton

Cuando en un proceso se llega a diferencias constantes, sabemos que es posible expresar la sucesión dada mediante un polinomio dependiente del número de orden. La fórmula hallada por Newton es algo compleja en el caso general, en el que hay que usar diferencias divididas, pero se simplifica bastante en el caso de un polinomio aplicado al conjunto 1, 2, 3, 4,…Sería esta:


En ella a0 es el primer término, d1 la primera diferencia, d2 la primera de las segundas diferencias, y así sucesivamente. En nuestro caso sería:

P(x)=2+6(x-1)+6(x-1)(x-2)/2!+2(x-1)(x-2)(x-3)/3!

Reduciendo a común denominador y simplificando:


Lo hemos comprobado con la hoja de cálculo. Observa la coincidencia de los valores en rojo:


Como ves, lo que es más complicado es la simplificación, pero el método es simple: encontrar diferencias sucesivas hasta que se estabilicen, y aplicar la fórmula de interpolación simplificada para los puntos de apoyo 1, 2, 3, 4,…
Todo esto puedes reproducirlo con nuestra hoja de cálculo newton, que puedes descargar desde

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

Recuerda que sólo te vale para sumas definidas sobre los primeros naturales.

Basta escribir los valores de la sucesión en la segunda fila


y leer los coeficientes (en forma de fracción) más abajo:



Es fácil de interpretar (de derecha a izquierda): 2/1 es el coeficiente de 1, 6/1 el de (x-1), 6/2 para (x-1)(x-2) y, finalmente, 2/6 para (x-1)(x-2)(x-3). Después vendría la simplificación, pero si quieres ahorrártela, la hoja dispone del cálculo para un valor concreto. Por ejemplo, ¿cuánto suman los diez primeros oblongos?

Para ello dispones de las celdas adecuadas



La respuesta es 440. Hay que advertir que puede producir pequeños errores para índices grandes, por lo que se aconseja comprobar.

Si deseas evitarte la simplificación puedes acudir a un CAS. Nosotros hemos usado wxMaxima para obtener el resultado previsto:

Otro paso sería el intentar, si es posible, buscar una interpretación al resultado obtenido. En nuestro caso es fácil ver que, para x mayor o igual a 3, se reduce a


Este proceso se puede repetir para números poligonales, piramidales o poligonales centrados (y otros similares que nos inventemos), porque todos se basan en sus definiciones en la acumulación de sumas, lo que garantiza que la fórmula buscada es de tipo poligonal.

Otro ejemplo

Sabemos que los números piramidales triangulares se construyen sumando los triangulares, y estos, a su vez, acumulando los naturales. Con un sencillo esquema los identificamos:


Luego los primeros piramidales son 1, 4, 10, 20,….Los volcamos en la hoja newton para descubrir sus diferencias y los coeficientes de interpolación:



Las diferencias son 1, 3, 3 y 1, y con ellas se construyen los coeficientes 1/1, 3/1, 3/2 y 1/6. Rellenamos la fórmula de interpolación y queda:

P(x)=1+3(x-1)+3/2(x-1)(x-2)+1/6(x-1)(x-2)(x-3)

Simplificamos con wxMaxima:


Coincide con la que se obtuvo en la entrada correspondiente a los números tetragonales (o piramidales triangulares)

http://hojaynumeros.blogspot.com.es/2017/04/numeros-piramidales-2-tetraedros.html


Con lo aprendido hoy estamos preparados para saltar a la cuarta o quinta dimensión, y sumar números piramidales consecutivos. Lo dejamos para otra entrada.