Desarreglos parciales: Otra forma de calcular el valor numérico

En el tema anterior vimos que 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.

En ese tema anterior vimos que el número de desarreglos parciales se calcula con la siguiente fórmula, donde D(n-k, 0) = !(n-k)

Haciendo uso de la recurrencia del Triángulo de Pascal

Sustituyendo en [1]

En [2] vemos que C(n-1, k) / C(n, k) = 1-k/n pues

Volviendo a [3] nos queda

Despejando queda esta otra fórmula recurrente para obtener el número de desarreglos parciales:

Como n≥k, el caso base está en k=0 en cuyo momento n será n-k = n, obteniéndose el valor base D(n-k, 0) = !(n-k) = !n

En el tema anterior obtuvimos los primeros valores para la fórmula [1]

Si aplicamos [4] a la tabla anterior obtenemos los mismos valores para n≥1, k≥1

Desplegando la recurrencia

Desplegamos la recurrencia [4]

Hemos obtenido la solución esperada D(n, k) = C(n, k) !(n-k) tras haber identificado el factorial descendente

Resolviendo la recurrencia con secuencia de primeros casos

Vamos a solucionar la recurrencia

Como vimos en caso base genérico, suponiendo que los valores iniciales son n₀, k₀, esta recurrencia se desplaza también en k con los valores k₀, k₀-1, k₀-2,..., 2, 1, 0 y en n con los valores n₀, n₀-1, n₀-2,..., n₀-(k₀-1), n₀-k₀

Si designamos b=n₀-k₀ vemos que esta diferencia permanece constante pues

Entonces para todo n,k tenemos que b=n-k es constante, pudiéndose modificar la recurrencia con una sola variable, teniendo en cuenta que b=n-k ⇒ k = n-b

que es lo mismo que

De forma compacta

En un tema anterior también vimos como resolver recurrencias con caso base genérico, mostrando que una forma de resolverlo es obteniendo una secuencia de primeros casos base para ver si deducimos un término general:

En lo anterior hemos usado Wolfram Alpha para resolver las recurrencias y obtener el término general y la función generadora, como por ejemplo para el último caso. Por otro lado tomamos los valores del subfactorial !b = 1, 0, 1, 2, 9, 44, ..., valores que se replican en las funciones generadoras, por lo que podemos suponer la general así:

Para suponer el término general observamos primero el factorial descendente que ya vimos en [5] y que suponemos que esta parte se generaliza así

Observamos ahora que la secuencia 1, 0, 1/2, 1/3, 3/9, 11/30, ... es el resultado de diviir la secuencia del subfactorial !b = 1, 0, 1, 2, 9, 44, ... entre la del factorial b! = 1, 1, 2, 6, 24, 120, ... pues

Por lo tanto el término general suponemos que es así:

Entonces

Si deshacemos el cambio b=n-k observamos que C(n, b) = C(n, k)

Obteniendo la solución general esperada

Resolviendo la recurrencia con función generadora

Resolvemos la misma recurrencia aplicando la técnica de la función generadora

De forma compacta

Incrementamos índices

Usaremos esta función generadora

Estas son las condiciones iniciales

Aplicando la función generadora a la recurrencia

Veamos la parte izquierda de [12]

Veamos la parte derecha de [12]

Veamos la serie en [14]

Para seguir resolviendo primero vemos que:

Ahora supongamos lo siguiente:

• a(n) = D(n+b)
• a(n-1) = D(n+b-1)
• ∑_n≥1 (a_n-1 / n) xⁿ = ∑_n≥1 (D(n+b-1)/n) xⁿ que es el sumatorio en [15]
• A(x) = ∑_n≥0 D(n+b) xⁿ = G(x)/x^b tal como vimos antes
• ∫ A(x) dx = ∑_n≥1 (a_n-1 / n) xⁿ por el principio de integrales de una serie que ya hemos visto en un tema anterior

Por lo tanto la serie en [15] queda así:

Actualizando [14] con [15] y [16] y agrupando con [13] en [12] nos queda:

Reagrupando G(x)

Dejando solo la integral en la parte derecha

Derivando en ambos lados

quedando

Tras simplificaciones que puede ver en el desplegable siguiente, queda finalmente la siguiente ecuación diferencial lineal ordinaria con coeficientes variables de primer orden, homogénea en este caso:

Se resuelve integrando en ambos lados:

Resultando:

Tras manipular los logaritmos y la constante, exponenciamos en ambos lados para obtener finalmente la función generadora:

Obteniendo la solución general

Lo que acabamos de obtener en el apartado anterior es como [6] a excepción de la constante c = !b que hemos de validar tras obtener el término general de la función generadora genérica sin la constante:

Cuando tenemos una función generadora y queremos buscar la solución o término general podemos hacer uso del Desarrollo de Taylor. Pero esta función tiene el problema de que hay que valorar en x=0 y ahí la función y sus derivadas iniciales valen cero, pues:

Las primeras derivadas son:

Se observa que para las derivadas G⁰(0) hasta G^b-1(0) resultarán cero y sólo a partir de la derivada G^b(0) = b(b-1)(b-2)···3·2·1 para ver la primera distinta de cero. Por lo tanto no parece fácil usar esta técnica a menos que hagamos lo siguiente:

Y trataremos de obtener el desarrollo de Taylor de f(x), tal como hicimos en un tema anterior cuando tratamos los casos base genéricos:

Parece que no es necesario seguir pues se supone el término general para n≥1

Como pochhammer genera la secuencia para n≥0 siguiente

Entonces podemos generalizar para n≥0

Entonces

Y nuestra función es

Como vimos en pochammer que n^k = k! C(n+k-1, k) entonces el término general queda así:

Se observa que hemos aplicado C(n, n-b) = n!/((n-b)! b!) = C(n, b) con lo que hemos alcanzado lo mismo que obtuvimos en [8] a falta de la constante c que aún hemos de determinar en [17]:

Resolviendo la constante

Para resolver la constante volvemos a recordar la recurrencia:

Y el caso base junto a [11] que se obtenía de la definición de esa recurrencia:

Entonces y, como era de esperar, tras ver que C(b, b) =1 obtenemos c = !b

Con lo que obtenemos la misma solución con la técnica de la función generadora que con las otras dos usando el despliegue o una secuencia de primeros casos base: