Función generadora con exponencial y logaritmo

Figura
Figura. Función generadora con subfactorial y logaritmo

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:

G(x) =-e-x log(x-1)
1-x

De forma indirecta en ese tema anterior nos servimos de OEIS para descubrir que esa función generadora exponencial respondía a la secuencia siguiente:

A(n) = 1, 1, 5, 20, 109, 689, 5053, 42048, ...

Esa secuencia, que se inicia en n≥1, es la misma que obteníamos de forma indirecta en el tema anterior, aunque allí le agregábamos el término A(0) = 0. En OEIS también exponen este término general:

A(n) = ∑k=1..n (-1)n-k C(n, k) k! H(k)

También en el tema anterior vimos otra fórmula equivalente, que fue la que usamos para la solución final de la recurrencia del coste del algoritmo que generaba los desarreglos, conteniendo H(n-j) que es el número armónico:

A(n) = ∑j=0..n-1(-1) j n!H(n-j)
j!

En OEIS usa log(1-x) en lugar de log(x-1), luego volveremos sobre esto, con este desarrollo de Taylor:

-e-xlog(1-x)=1 x1+1 x2+5 x3+20 x4+109 x5+689 x6+5053 x7+...
1-x1!2!3!4!5!6!7!

Se observa que los numeradores son los mismos que los de la secuencia dada. Sin embargo si tratamos de obtener esto en Wolfram Alpha no lo vamos a encontrar. Cuando hacemos equivaler una función con una serie se suele condicionar a algo como |x|<1, de tal forma que x es un número real. Pero en la función tenemos log(x-1) con lo que para |x|<1 tendremos números negativos, para los que el logaritmo no está definido entre los reales, aunque si en los complejos. Podemos hacer esto:

2 log(x-1) = log(x-1) + log(x-1) = log((x-1)2) ⇒
log(x-1) = 1/2 log((x-1)2)

Así (x-1)2 siempre tomará valores positivos para |x|<1. Y además (x-1)2 = (1-x)2. Entonces nuestra función queda así, cuyo desarrollo de Taylor podemos ver en WolframAlpha que ahora si produce la secuencia dada:

-e-xlog(x-1)= -e-xlog((1-x)2)=1 x1+1 x2+5 x3+20 x4+109 x5+ O(x6)
1-x2 (1-x)12624120

En cualquier caso podemos obtener el desarrollo de Taylor de -e-x log(x-1) / (1-x) directamente, como se muestra en el siguiente desplegable.

Así que teniendo el término general y el desarrollo de Taylor podemos expresarlo como una función generadora exponencial usando cualquiera de los dos términos generales de A(n) que vimos en [1] o [2]:

-e-xlog(x-1)= ∑n≥0 (k=1..n (-1)n-k C(n, k) k! H(k) )xn=
1-xn!
= ∑n≥0 (j=0..n-1(-1) j n!H(n-j) )xn
j!n!

Verificando la corrección de los términos generales

El asunto ahora es verificar matemáticamente que eso es cierto, pues de serlo estamos seguros que podemos usar A(n) en nuestra solución de la recurrencia del tema anterior. En primer lugar veamos que relación hay entre log(x-1) y log(1-x), pues como vimos más arriba, OEIS usaba esta segunda forma.

log(x-1) = log((-1)×(1-x)) = log(1-x) + log(-1) + = log(1-x) + i π

En el desplegable anterior vimos porque log(-1) = i π. Y además que podíamos despreciar la parte compleja pues lo que estamos buscando son las partes reales. Así que a nuestros efectos es equivalente usar log(1-x) en nuestra función puesto que ignoraremos la parte compleja:

G(x) = -e-xlog(x-1)= -e-x(log(1-x) + i π)= -e-x log(1-x)- iπ e-x
1-x1-x1-x1-x

Observe que la parte imaginaria tiene la función e-x / (1-x) que es la función generadora del subfactorial, cuya secuencia es !n = 1, 0, 1, 2, 9, 44, 265, 1854, ... como vimos en el desplegable anterior. Vamos a buscar la serie con su término general de la parte real:

G(x) =e-x× (- log(1-x))
1-x

Intencionadamente hemos separado esto en dos partes, por un lado la primera que es el subfactorial que vimos en el tema de los desarreglos:

G1(x) =e-x= ∑n≥0 !nxn
1-xn!

Y la segunda que contiene el logaritmo:

G2(x) = - log(1-x)

Intentemos encontrar la serie asociada a este logaritmo usando Taylor:

f(x) = ∑n≥0f n(0)xn
n!

Empecemos

f 0(x) = -log(1-x) f 0(0) = -log(1) = 0
f 1(x) =d(- log(1-x))=1 f 0(0) = 1
dx1-x
f 2(x) =1 f 1(0) = 1
(1-x)2
f 3(x) =2 f 2(0) = 2
(1-x)3
f 4(x) =6 f 3(0) = 6
(1-x)4
f 5(x) =24 f 4(0) = 24
(1-x)5
f 6(x) =120 f 4(0) = 120
(1-x)6

Entonces

f(x) = ∑n≥0f n(0)xn=0x0 +1x1 +1x2 +2x3 +6x4 +24x5 + ... =
n!0!1!2!3!4!5!
=0!x1 +1!x2 +2!x3 +3!x4 +4!x5 + ... =
1!2!3!4!5!
=x+x2+x3+x4+x5=
12345
=∑n≥11xn= ∑n≥1n!xn= ∑n≥1 (n-1)!xn
nnn!n!

El número armónico

Entonces la segunda función con el logaritmo da lugar a una serie armónica:

G2(x) = -log(1-x) = ∑n≥1 (n-1)!xn= ∑n≥11xn
n!n

Como para n=0 lo anterior no estaría definido, vamos a reformularlo pues necesitamos el producto de dos series que se inician en cero (ver en WolframAlpha):

G2(x) = -log(1-x) =
= ∑n≥0 (1/nn≥1xn )
0n=0

El n-ésimo número armónico se define como la suma de los recíprocos de los primeros n números naturales, con esta serie para n≥1:

H(n) = ∑j=1..n 1/j

Genera la secuencia con términos fraccionarios siguiente:

H(n) = 1/1, 3/2, 11/6, 25/12, 137/60, ...

Si ajustamos la fracción para que se corresponda con un denominador con n! tendremos la secuencia

H(n) = 1/1!, 3/2!, 11/3!, 50/4! 274/5!, ...

También puede obtenerse de forma recurrente:

n<1 ⇒ H(n) = 0,
n=0 ⇒ H(n) = 1,
H(n) = H(n-1) +1
n

Otra alternativa es usando los números de Stirling de primera clase, que exponemos en el siguiente apartado:

H(n) =S(n+1, 2)
n!

Los valores sin signo para n≥1 son los siguientes:

S(n+1, 2) = 1, 3, 11, 50, 274, 1764, 13068, 109584, ...

Por lo tanto los primeros valores de los números armónicos son los que resultan dividiendo Stirling por subfactorial, partiendo de n≥1:

H(n) =S(n+1, 2)= 1/1!, 3/2!, 11/3!, 50/4!, 274/5!, 1764/6!, ...
n!

Números de Stirling de primera clase

S(n, k) o bien [nk] son los números de Stirling de primera clase sin signo pueden definirse como el número permutaciones de n elementos en k ciclos disjuntos, contando las permutaciones cíclicas que veremos en un tema posterior. Obedecen a la siguiente recurrencia:

n=k ⇒ S(n, k) = 1,
n=0 ∨ k=0 ∨ n<k ⇒ S(n, k) = 0,
S(n, k) = (n-1) S(n-1, k) + S(n-1, k-1)

Los primeros valores pueden obtenerse en la aplicación Combine Tools, en la pestaña "Numéricos":

n↓k→01234567
010000000
101000000
201100000
302310000
4061161000
5024503510100
60120274225851510
7072017641624735175211

No debemos confundirlos con los que tienen signo que obedece a la recurrencia

n=k ⇒ s(n, k) = 1,
n=0 ∨ k=0 ∨ n<k ⇒ s(n, k) = 0,
s(n, k) = - (n-1) s(n-1, k) + s(n-1, k-1)

con estos valores numéricos

n↓k→01234567
010000000
101000000
20-1100000
302-310000
40-611-61000
5024-5035-10100
60-120274-22585-1510
70720-17641624-735175-211

Ambas se equiparan así:

s(n, k) = (-1)n-k S(n, k)
S(n, k) = | s(n, k) |

Los números de Stirling de primera clase son los coeficientes s(n, k) (con signo) del factorial descendente (o falling factorial):

(x)n = xn = x(x-1)(x-2)···(x-n+1) = ∑k=0..n s(n, k) xk

Por ejemplo:

x3 = x(x-1)(x-2) = x3-3x2+2x

siendo los coeficientes s(3, 3) = 1, s(3, 2) = -3, s(3, 1) = 2 tal como se observa en la tabla de valores anterior.

Por otro lado, los números de Stirling sin signo S(n, k) se corresponden con los coeficientes del factorial ascendente (o símbolo de Pochhammer):

x(n) = xn = x(x+1)(x+2)···(x+n-1) = ∑k=0..n S(n, k) xk

El producto de Cauchy o convolución de exponenciales y logaritmos

Antes en [3] habíamos presentado este producto de funciones exponencial y logarítmica:

G(x) =e-x× (- log(1-x))
1-x

Como ya conocemos las series asociadas a ambas funciones, vamos a realizar ese producto o convolución de funciones, pero antes recordamos el producto de Cauchy:

P(x) Q(x) = (n≥0 pn xn ) × (n≥0 qn xn ) = ∑n≥0 (k=0..n pk qn-k ) xn =
= ∑n≥0 ( p0 qn + ∑k=1..n pk qn-k ) xn =
= ∑n≥0 p0 qn xn + ∑n≥0 (k=1..n pk qn-k ) xn =
= ∑n≥0 p0 qn xn + ∑n=0..0 (k=1..n pk qn-k ) xn + ∑n≥1 (k=1..n pk qn-k ) xn =
= ∑n≥0 p0 qn xn + ∑k=1..0 pk q0-k x0 + ∑n≥1 (k=1..n pk qn-k ) xn =
= 0 + 0 + ∑n≥1 (k=1..n pk qn-k ) xn

Lo anterior es cierto si p0 = 0, pues vamos a tomar pn como el término de la serie armónica [7] que proviene del logaritmo. Y además la suma k=1..0 es cero al tener un rango invertido.

Así que tomando pn como el término de la serie [7] y qn como el término de la serie [4], entonces el producto [3] queda así:

G(x) = G1(x) × G2(x) = (n≥0!nxn) × (n≥01xn) =
n!n
= ∑n≥1(k=1..n!(n-k)×1) xn
(n-k)!k

Veamos el término de la serie, al que denominaremos B(n), usando la definición del subfactorial que era !n = ∑j=0..n (-1) j n! / j!

B(n) = ∑k=1..n!(n-k)×1=
(n-k)!k
= ∑k=1..n (j=0..n-k(-1) j (n-k)!) ×1=
j! (n-k)!k
= ∑k=1..n (j=0..n-k(-1) j) ×1
j!k

Al incluir este término en la función generadora [8] nos quedará:

G(x) = ∑n≥1 B(n) xn= ∑n≥1 B(n) n!xn= ∑n≥0 A(n)xn
n!n!

Hemos definido A(n) = B(n) n! Observe que podemos reajustar el rango a n≥0 pues hemos redefinido el caso n=0 en [7] donde forzamos p0 = 0 al desarrollar el producto de Cauchy. Se observa que podemos modificar el rango del sumatorio exterior, pues llegamos a un sumatorio con rango invertido cuya suma es cero:

n≥0 (k=1..n ak ) xn = ∑n=0..0 (k=1..n ak ) xn + ∑n≥1 (k=1..n ak ) xn =
= ∑k=1..0 ak x0 + ∑n≥1 (k=1..n ak ) xn = 0 + ∑n≥1 (k=1..n ak ) xn

Entonces A(n) pueden ser las dos ya vistas en [1] y [2] (cuya equivalencia ya demostramos en un apartado del tema anterior) a su vez supuestamente equivalentes también con esta última que acabamos de obtener:

A(n) = ∑k=1..n (-1)n-k C(n, k) k! H(k) =
= ∑j=0..n-1(-1) j n!H(n-j) =
j!
= ∑k=1..n (j=0..n-k n!(-1) j) ×1
j!k

Para asegurarnos de que la tercera es equivalente a las otras dos, calcularemos los primeros valores, desde n = 1 hasta n = 8

A(1) = ∑k=1..1j=0..1-k 1! (-1) j/j! 1/k = 1
A(2) = ∑k=1..2j=0..2-k 2! (-1) j/j! 1/k = 1
A(3) = ∑k=1..3j=0..3-k 3! (-1) j/j! 1/k = 5
A(4) = ∑k=1..4j=0..4-k 4! (-1) j/j! 1/k = 20
A(5) = ∑k=1..5j=0..5-k 5! (-1) j/j! 1/k = 109
A(6) = ∑k=1..6j=0..6-k 6! (-1) j/j! 1/k = 689
A(7) = ∑k=1..7j=0..7-k 7! (-1) j/j! 1/k = 5053
A(8) = ∑k=1..8j=0..8-k 8! (-1) j/j! 1/k = 42048

Hemos resuelto lo anterior con ayuda, como por ejemplo para el último caso, en WolframAlpha. Vemos que esta secuencia A(n) = 1, 1, 5, 20, 109, 689, 5053, 42048, ... es precisamente la que obteníamos con las dos primera fórmulas equivalentes. Veamos si podemos demostrar que esto es cierto. Para ello tomemos esta expresión genérica:

k=1..n (j=0..n-k aj ) bk =
= ∑k=1..n ( a0 + a1 + ... + an-k ) bk =
= ( a0 + a1 + ... + an-1 ) b1 + ... + ( a0 + a1 ) bn-1 + ( a0 ) bn =
= a0 ( b1 + ... + bn ) + ... + an-2 ( b1 + b2 ) + an-1 ( b1 ) =
= ∑j=0..n-1 aj (k=1..n-j bk )

Si aj = (-1) j n! / j! y, por otro lado, bk = 1/k entonces si:

k=1..n (j=0..n-k aj ) bk =
= ∑k=1..n (j=0..n-k n!(-1) j) ×1
j!k

sucederá que es equivalente a esta

j=0..n-1 aj (k=1..n-j bk ) =
= ∑j=0..n-1(-1) j n!(k=1..n-j1) =
j!k
= ∑j=0..n-1(-1) j n!H(n-j)
j!

Hemos identificado H(n-j) como vemos en WolframAlpha, como el (n-j)-ésimo número armónico, pues el n-ésimo número armónico es H(n) = ∑k=1..n 1/k, con lo que demostramos la equivalencia de la tercera con la segunda fórmula en [10] y, a su vez, con la primera pues ya se demostró la equivalencia de las dos primeras.