Temas sobre desarrollo web y programación informática

Recurrencia Desarreglos Parciales

En este tema implementaremos un algoritmo para generar los desarreglos parciales usando la recurrencia D(n, k) = ∑j=k..n D(n-1, j-1) que calcula su valor numérico, tal como vimos en el tema anterior.

Similitud entre recurrencias de combinaciones y desarreglos parciales

En temas anteriores hemos visto que el valor numérico de los desarreglos parciales se puede calcular con D(n, k) = C(n, k) × D(n-k) y también con D(n, k) = n/k D(n-1, k-1). En este tema buscaremos una tercera forma con similitud con la que ya habíamos visto para las combinaciones C(n, k) = ∑j=k..n C(j-1, k-1), como se observa en la imagen, aplicando D(n, k) = ∑j=k..n D(n-1, j-1)

Recurrencia Desarreglos Parciales

En el tema anterior vimos que la recurrencia D(n, k) = n/k D(n-1, k-1), como se observa en la imagen, también nos sirve para calcular el valor numérico de los desarreglos parciales. En este tema implementaremos un segundo algoritmo para generar los desarreglos parciales basándonos en esa recurrencia.

Función generadora de D(n, k) = n/k D(n-1, k-1) con b=n-k

En el tema anterior vimos que el número de desarreglos parciales se calcula con la fórmula D(n, k) = C(n, k) × D(n-k, 0) donde D(n-k, 0) = !(n-k). En este tema vamos a deducir la fórmula recurrente D(n, k) = n/k D(n-1, k-1) para calcular también el valor numérico de los desarreglos parciales, pudiendo expresarse también con la función generadora G(x) = !b xb / (1-x)b+1.

Función generadora de los desarreglos parciales D(n, k)

Los desarreglos parciales de una lista con n elementos distintos son todas las sublistas ordenadas con n elementos distintos que se pueden generar de tal forma que solo k elementos aparecen en su posición original. También se pueden definir como las permutaciones de n elementos con k puntos fijos. Las denotamos como D(n, k), correspondiendo con k=0 a los desarreglos sin puntos fijos que vimos en un tema anterior.

También se les denomina Rencontres numbers traducido como Problema de encuentros (o reencuentros). La función generadora de esta familia de funciones combinatorias es G(x, k) = e-x xk / (k! (1-x)). En este tema implementaremos un primer algoritmo para generar los desarreglos parciales.

Desarreglos recursivo (Recursive derangements)

En un apartado del tema anterior que trataba sobre el coste de un algoritmo recursivo para generar desarreglos, habíamos llegado a una función sobre la que omitíamos obtener el término general en ese momento, pues contenía un logaritmo.

Era el producto de e-x/(1-x) que genera los subfactoriales y del logaritmo log(x-1), función que hasta ahora no habíamos tratado de obtener su serie asociada y término general. En este tema analizaremos esto.

Desarreglos recursivo (Recursive derangements)

En este tema vamos a implementar un segundo algoritmo para generar los desarreglos de una lista con n elementos. Se basa en la primera recurrencia D(n) = (n-1) ( D(n-1) + D(n-2) ) que expusimos en un tema anterior.

Desarreglos

Desarreglos (Derangements)

Los desarreglos (derangement) de una lista con n elementos distintos son todas las sublistas ordenadas con n elementos distintos que se pueden generar de tal forma que ninguno aparece en su posición original. Se denota como D(n). Y también como !n, el subfactorial de n.

Una permutación de n elementos tiene uno o más elementos que son puntos fijos si esos elementos se mantienen en su posición original. Desde esta definición un desarreglo es una permutación que no tiene ningún punto fijo.

Variaciones con repetición

Las variaciones con repetición de una lista con n elementos distintos son todas las sublistas ordenadas con k elementos no necesariamente distintos que se pueden extraer. Su valor es VR(n, k) = nk. En este tema veremos un algoritmo para obtener las permutaciones con repetición.

Caso base genérico

El caso base de una recurrencia condiciona la búsqueda de su solución. Lo más fácil es que sea un caso base particularizado en n=0 o algún valor superior de n. En el primer ejemplo de recurrencias que vimos en esta serie de temas, la del coste del algoritmo que calculaba el factorial cuya recurrencia era T(0) = 1, T(n) = T(n-1) + 1, tenía el caso base en n=0. En este tema veremos algunos ejemplos con un caso base genérico n=b+1, con lo que tendríamos una recurrencia como T(b+1) = 1, T(n) = T(n-1) + 1. Y veremos otra con T(b+1) = 0, T(n) = T(n-1) + n - b - 1. Aunque b es constante con respecto al desarrollo de la recurrencia, la solución del término general será T(n, b) dependiente también de b.

Resolver recurrencias con caso base genérico puede ser fácil usando la técnica del despliegue de la recurrencia. Pero puede complicarse usando la técnica de la función generadora, como sucedió en el tema anterior. Para ello veremos técnicas de actuación sobre el primer caso base y la de secuencia de primeros casos base que pueden ayudar a resolverlas de otra forma. En el tema anterior aplicamos esa última para resolver la recurrencia de las variaciones. En este tema usaremos esas utilidades para resolver partes del desarrollo de esa recurrencia con función generadora.

Variaciones

Variaciones

Las variaciones sin repetición de una lista con n elementos distintos son todas las sublistas ordenadas con k elementos distintos que se pueden extraer. Se denota como V(n, k). En este tema veremos varios algoritmos para generar las variaciones.

Al final del tema recopilamos la relación que hay entre las variaciones con los temas anteriores para generar permutaciones, K-tuplas y convolución exponencial de factoriales y potencias.

Permutaciones con repetición

El algoritmo de Heap es un algoritmo de intercambio que supone la forma más eficiente de construir las permutaciones sin repetición. Ese mismo algoritmo lo usamos en el tema anterior para construir las permutaciones con repetición o multinomiales. Pero el coste parece excesivo. Por ejemplo, para el conjunto de partida A = { a, a, a, a, a, a, a } con 7 letras "a" repetidas, el coste es de 57638 iteraciones. Son muchas iteraciones en tanto que las permutaciones con repetición de A es una, el propio A. En este tema buscamos una forma de reducir este coste.

Permutaciones con repetición o multinomial

Las permutaciones con repetición, también denominado multinomial, de un conjunto de una lista A = { a1, ..., an } donde pueden producirse repeticiones y al quitar los elementos repetidos obtenemos otra lista { b1, ..., bm } con m≤n elementos distintos, donde cada elemento bi puede estar repetido ri veces, con 0 ≤ ri ≤ n, de tal forma que r1+...+rm = n, son todas las posibles ordenaciones de la lista A. Se denota como PR(r1, ..., rm). En este tema veremos varios algoritmos para generar permutaciones con repetición, uno de ellos usando el algoritmo de Heap que ya vimos en el tema de las permutaciones.

Finalizaremos el tema hablando de los coeficientes multinomiales y la pirámide de Pascal, concepto que amplía el de coeficientes binomiales con dos variables (x+y)n a más variables, como por ejemplo (x+y+z)n con 3 variables.

Algoritmo de Heap para permutar 3 elementos

El algoritmo de Heap genera las permutaciones de forma más eficiente que el que hemos usado en el tema anterior. Se basa en generar cada permutación desde una previa intercambiando una pareja de elementos cada vez. En la Imagen puede ver como se van intercambiando posiciones desde la lista inicial [0, 1, 2] generando las permutaciones {[0, 1, 2], [1, 0, 2], [2, 0, 1], [0, 2, 1], [1, 2, 0], [2, 1, 0]}.

Permutaciones

Permutaciones con 3 elementos

Las permutaciones de una lista con n elementos distintos son todas las sublistas ordenadas con n elementos distintos que se pueden generar. Se denota generamente como P(n). Su valor es P(n) = n! Como se observa en la Imagen, para tres elementos obtenemos P(3) = 3! = 6.

Buscar dos puntos con menor distancia

El caso base de una recurrencia es aquel que nos permite resolverla, finalizando el proceso recursivo y devolviendo la solución. Cuando el caso base es un índice mayor de cero decimos que está desplazado. Y esto afecta a la forma en que aplicamos la técnica de la función generadora o generatriz. Resolveremos un ejemplo que trata de buscar los dos puntos que se encuentran a menor distancia entre un conjunto de puntos.

Convolución exponencial de factoriales y potencias

En la página OEIS podemos ver la secuencia 1, 6, 27, 124, 645, ... que denomina Convolución exponencial de factoriales y cuadrados (Exponential convolution of factorials and squares). Es el resultado de la recurrencia a(n) = n a(n-1) + n2 con a(0)=0. Expone entre otras la solución a(n) = ∑j=0..n (n! j2) / j! que es como la que aparece en la Imagen para k=2. Podemos encontrar OEIS con factoriales y cubos, que también se ajusta a la general con k=3. En este tema analizamos esta recurrencia y su relación con las K-Tuplas que vimos en el tema anterior.

Función Gamma y su recíproca

Adicionalmente en este tema veremos la Función Gamma pues está relacionada con las series que resuelven las recurrencias. He podido también representar esa función como se observa en la Imagen, generada en mi aplicación Gráficas matemáticas. Usa la definición en formato de texto plot-gamma.txt, para lo cual debe copiar ese texto y pegarlo en la pestaña I/O para importarlo en ese graficador de funciones matemáticas si quisiera observar su generación. En rojo se dibuja la función Gamma Γ(x) y en azul la función recíproca 1/Γ(x), que, como se observa, cruza por cero y los enteros negativos.

K-Tuplas

K-Tuplas

Definimos las K-Tuplas de un conjunto A con n elementos distintos a todas las sublistas ordenadas que podemos generar con las permutaciones aplicadas sobre todos los subconjuntos de orden k hasta n que se obtienen desde el conjunto A.

K-Tuplas

Una recurrencia con coeficientes variables es como K(n) = n K(n-1) + 1. No puede usarse el modelo de ecuación de recurrencia de coeficientes constantes y es necesario utilizar la técnica de la función generadora o generatriz exponencial. Se analiza esa recurrencia de ejemplo usando varias técnicas y estudiando nuevos conceptos como el producto de series, la relación con las combinaciones y las series binomiales, la función gamma incompleta, el factorial ascendente (símbolo de Pochhammer) y descendente, la función hipergeométrica generalizada y la función hipergeométrica confluente de segunda clase.