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) = n^k. En este tema veremos un algoritmo para obtener las permutaciones con repetición.

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 despligue 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.

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.

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.

Las permutaciones con repetición, también denominado multinomial, de un conjunto de una lista A = { a₁, ..., a_n } donde pueden producirse repeticiones y al quitar los elementos repetidos obtenemos otra lista { b₁, ..., b_m } con m≤n elementos distintos, donde cada elemento b_i puede estar repetido r_i veces, con 0 ≤ r_i ≤ n, de tal forma que r₁+...+r_m = n, son todas las posibles ordenaciones de la lista A. Se denota como PR(r₁, ..., r_m). 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)ⁿ a más variables, como por ejemplo (x+y+z)ⁿ con 3 variables.

Exportar un trozo de HTML a una imagen se basa en la facultad de albergar un SVG (Scalable Vector Graphics) en un elemento imagen (IMG). Se usa la API Image(), que es un constructor del elemento imagen, conjuntamente con un Canvas para convertir el SVG en un formato de imagen, como PNG, JPG y otros. Un SVG no es otra cosa que un XML. Y yo empecé a estudiar HTML aprendido primero XHTML que debe ser escrito como XML. Es necesario respetar las reglas XHTML en el trozo de HTML que queremos convertir en imagen, pero no es nada complicado. La imagen adjunta es un archivo PNG que se extrae de un trozo de HTML, como veremos en un ejemplo interactivo en ese tama.

En este tema intentaré explicar cómo se hace, pues de paso recordaremos cosas que se relacionan como SVG, XML, XHTML, HTML-5, Base64, Canvas e Image. Y otras cosas relacionadas con la serialización de bytes, manejando Base64 con el uso de los métodos encodeURIComponent(), btoa() y atob(). O bien con TextEncoder y TextDecoder, donde se usa el array tipado (Typed Array) Uint8Array, que junto a Blob y objetos URL veremos también para la descarga de archivos, algo que explicaremos en el último apartado.

En este tema veremos las clases del módulo Math que nos permiten escribir HTML y CSS suficiente para presentar visualmente una fórmula matemática. Y, adicionalmente, poder extraerla como una expresión en lenguaje natural válida para usarla en aplicaciones como Wolfram Alpha.

En la imagen puede ver como presentamos la raíz cuadrada usando el símbolo UNICODE "√". El estilo en forma de clases con un guion bajo inicial y dos letras aplicarán lo necesario para incluir la línea superior que abarca la raíz, algo que el simple caracter "√" no incluye. En lenguaje natural la extraemos como sqrt(n), expresión que podemos usar en Wolfram Alpha y otras aplicaciones. Empecemos por listar las clases disponibles con la versión actual.

Desde hace tiempo he necesitado presentar fórmulas matemáticas en estas páginas web. Aunque existe la extensión MathML, de la que luego hablaremos, HTML ofrece pocas cosas para hacerlo directamente. He venido usando algunos recursos como los elementos SUB y SUP. Por ejemplo x²+1, con el código <var>x<sup>2</sup>+1</var>. El elemento VAR tiene fuente Georgia y estilo itálica para intentar lograr una apariencia de fórmula matemática. Sin embargo, escribir fracciones, raíces o cosas más complejas con solo estos recursos y con una presentación aceptable no es fácil.

Ahora, con la serie de temas que exponen la Combinatoria con recursivos, he implementado los módulos JavaScript Math y CopyMath. En la imagen puede ver una fórmula matemática escrita en HTML directamente en esta página, con estilo CSS. Antes de entrar a explicar estos módulos veamos que otros recursos existen y sus ventajas o inconvenientes.

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]}.

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.

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.

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) + n² con a(0)=0. Expone entre otras la solución a(n) = ∑_j=0..n (n! j²) / 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.

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.

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.

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.

Las combinaciones con repetición de una lista con n elementos distintos son todas las sublistas con k elementos no necesariamente distintos que se pueden extraer sin importar el orden. Se denotan como CR(n, k) y también como CR_n,k.

Hay varias identidades relacionadas con los coeficientes binomiales. Una de ellas es la que vemos en la imagen, obtenida a partir de la denominada identidad Hockey-stick. Se observa que es una expresión recurrente que podría servirnos para buscar una versión mejorada del problema de obtener los subconjuntos combinaciones sin repetición de un conjunto que vimos en el tema anterior.

Usaremos la técnica de la función generadora para obtener el coste del algoritmo. Finalizaremos comparando la mejora obtenida con respecto al algoritmo del tema anterior.

El número de combinaciones sin repetición de n elementos distintos en subconjuntos de k elementos son las posibles muestras de k elementos distintos y sin orden que pueden extrarser de los n elementos. En estas páginas las denotaremos como C(n, k).

La primera aproximación para implementar un algoritmo es usar la conocida fórmula matemática con la recurrencia C(n, k) = C(n-1, k-1) + C(n-1, k) que sirve para construir el Triángulo de Pascal. La fila n son los coeficientes binomiales del polinomio (1+x)ⁿ. Analizaremos el coste usando la técnica de la función generadora.