9.2: Números catalanes

Este es un ejemplo que muestra aún más claramente la potencia del método de función generadora.

Los números catalanes son una secuencia que se puede definir de diversas maneras, porque surgen en una serie de circunstancias diferentes. Usaremos la siguiente definición.

Definición: Número Catalán

El número\(n^{\text{th}}\) catalán,\(C_n\), es el número de diferentes formas en las que se pueden poner paréntesis alrededor de\(n\) términos, para indicar diferentes órdenes de combinación de los términos.

Así, por ejemplo,\(C_3 = 2\), ya que tres términos se pueden combinar como

[(_·_) ·_], o [_·_ (_·_)].

Estos números tienen algo en común con el Ejemplo 6.3.2, en el que Shawna estaba construyendo torres a partir de lego. Si hubiéramos preguntado en cuántos órdenes diferentes podría combinar los bloques para construir su torre, suponiendo que el pedido final de los bloques se decidiera de antemano, habríamos estado pidiendo el número catalán. Entonces podemos usar una lógica similar a la lógica que usamos en ese ejemplo: para crear una expresión con n términos, nuestro paso final debe implicar combinar un conjunto de\(k\) términos (para los cuales ya se ha determinado el orden de combinarlos) y un conjunto de\(n − k\) términos (para los cuales el orden de combinar ellos ya se han determinado). Aquí,\(k\) puede tomar cualquier valor de\(1\) a\(n − 1\)). Esto da como resultado la relación recursiva:

\(C_n = \sum_{k=1}^{n-1} C_kC_{n−k}\)

Esto puede ser más fácil de ver con un ejemplo. Hemos trabajado\(C_3\) arriba; para poder trabajar\(C_4\) usando esta relación recursiva, también necesitamos saber\(C_1\) y\(C_2\). Sólo hay una manera de combinar un solo término (no necesitamos corchetes en absoluto), entonces\(C_1 = 1\). También tenemos\(C_2 = 1\), ya que sólo hay una manera de poner corchetes alrededor de un par de términos: (_·_).

Ahora bien, para usar corchetes para ordenar las operaciones en una expresión de cuatro términos, nuestra operación final debe combinar un grupo de tres términos con un solo término; un grupo de dos términos con otro grupo de dos términos; o un solo término con un grupo de tres términos (esta vez, el término único está a la izquierda). Las dos primeras expresiones siguientes provienen de combinar un grupo de tres términos con un solo término; la tercera viene de combinar un grupo de dos términos con otro grupo de dos términos; y los dos últimos provienen de combinar un solo término con un grupo de tres términos.

([(_·_) ·_] ·_), ([_· (_·_)] ·_), [(_·_) · (_·_)] (_· [(_·_) ·_]) (_· [_· (_·_)]).

Por lo tanto,

\(C_4 = C_3C_1 + C_2C_2 + C_1C_3 = 2 + 1 + 2 = 5\).

Ahora queremos usar funciones generadoras para averiguar qué podemos sobre los números catalanes. Desafortunadamente, hay una dificultad. Cada vez que queremos usar funciones generadoras para resolver una secuencia definida recursiblemente, la secuencia debe comenzar con un\(0^{\text{th}}\) término, para ser el coeficiente de\(x^0\). Con algunas secuencias definidas recursiblemente, podemos simplemente usar la relación recursiva “hacia atrás” para resolver términos anteriores, bajando a\(n = 0\), incluso si nuestras condiciones iniciales comenzaron con términos mucho más altos. Por ejemplo, si una secuencia definida recursiblemente viene dada por\(h_2 = 1\),\(h_3 = 5\) y\(h_n = 8h_{n−2} − h_{n−1}\) para cada\(n ≥ 4\), podemos usar\(n = 3\) en esto para obtener

\(h_3 = 5 = 8h_1 − h_2 = 8h_1 − 1\).

Resolviendo para\(h_1\) da\(h_1 = \dfrac{3}{4}\). Luego usando la relación recursiva con\(n = 2\) da

\(h_2 = 1 = 8h_0 − h_1 = 8h_0 − \dfrac{3}{4}\).

Resolviendo para\(h_0\) da\(h_0 = \dfrac{7}{32}\). Esto nos permite utilizar funciones generadoras en la secuencia.

La relación recursiva para los números catalanes no tiene una forma que nos permita resolver\(C_0\) por conocer otros términos de la secuencia, así hacemos lo que tenemos que hacer, para que las cosas funcionen. En lugar de trabajar con la función generadora para los propios números catalanes (ya que no podemos), trabajamos con la función generadora para la secuencia\(c_0, c_1, c_2, . . .\), donde\(c_i = C_{i+1}\) para cada\(i ≥ 0\). Es decir, el\(n^{\text{th}}\) término de nuestra nueva secuencia será el número\(n + 1^{\text{st}}\) catalán.

Ajustando la relación recursiva que hemos determinado para los números catalanes a esta nueva secuencia, da

\(c_0 = 1\), y\(c_n = \sum_{k=0}^{n-1} c_kc_{n−k−1}\) para cada\(n ≥ 1\).

Observe que

\( \begin{equation} \begin{split} c(x)c(x)&= (c_0 + c_1x + c_2x^2 + c_3x^3 + . . .)(c_0 + c_1x + c_2x^2 + c_3x^3 + . . .) \\ &= c_0c_0 + (c_1c_0 + c_0c_1)x + (c_2c_0 + c_1c_1 + c_0c_2)x^2 + (c_0c_3 + c_1c_2 + c_2c_1 + c_3c_0)x^3 + . . ., \end{split} \end{equation} \)

y en general, el coeficiente de\(x^m\) in\((c(x))^2\), es

\(\sum_{k=0}^{m}c_kc_{m−k}\).

¡Esto debería parecer familiar! De hecho, se puede ver que el coeficiente de\(x^m\) in\((c(x))^2\), es el mismo que el coeficiente de\(x^{m+1}\) in\(c(x)\), ya que este último es

\(\sum_{k=0}^{m}c_kc_{m−k}\)

también.

Así, tenemos una expresión para\(c(x)\) en términos de\((c(x))^2\), ya que multiplicar\((c(x))^2\) por x da todos los términos de\(c(x)\) excepto\(c_0: c(x) = x(c(x))^2 + c_0\). Podemos reorganizar esta ecuación, para ver que

\(x[c(x)]^2 − c(x) + 1 = 0\).

Estamos a punto de hacerle algo a esta función generadora que puede parecer un poco como magia negra: usaremos la fórmula cuadrática para facturar esta ecuación cuadrática en\(c(x)\), tratando\(x\) como el coeficiente de\((c(x))^2\). Así, en la fórmula cuadrática\(a = x\), tomamos\(b = −1\), y\(c = 1\), y obtenemos

\(c(x) = \dfrac{1 ± \sqrt{1 − 4x}}{2x}\)

Por supuesto, hay dos raíces en esto, y solo una de ellas dará la función generadora correcta; necesitamos averiguar cuál (ya sea tomar el más o el menos).

Usando el Teorema Binomial Generalizado, vemos que

\((1 − 4x)^{\dfrac{1}{2}} = \binom{\dfrac{1}{2}}{0} + \binom{\dfrac{1}{2}}{1}(-4x) + \binom{\dfrac{1}{2}}{2}(-4x)^2 + ... + \binom{\dfrac{1}{2}}{k}(-4x)^k + ... \)

y

\(\binom{\dfrac{1}{2}}{k} = \dfrac{(\dfrac{1}{2})(−\dfrac{1}{2})(−\dfrac{3}{2}). . .(\dfrac{1}{2} − k + 1)}{k!} = \dfrac{(−1)^{k−1} 1 · 3 · 5 · (2k − 3)}{2^kk!} \)

por lo que el coeficiente de\(x^k\) in\((1 − 4x)^{\dfrac{1}{2}}\) es

\(\dfrac{(−1)^{k−1} 1 · 3 · 5 · (2k − 3)}{2^kk!} (-4)^k)= \dfrac{(−1) 1 · 3 · 5 · (2k − 3)2^k}{k!}\)

Cualquiera que sea la raíz que usemos requerirá esta expresión, así que vamos a trabajar con ella un poco más para ponerlo en una forma más agradable.

\(2^k k! = 2^k (1 · 2 · 3 · . . . · k) = 2 · 4 · 6 · . . . · 2^k,\)

así que si multiplicamos el numerador y denominador de la fracción por\(k!\) (que no cambia el resultado), vemos que tenemos

\(\dfrac{(−1)1 · 3 · 5 · (2k − 3)2 · 4 · 6 . . . · 2k}{k!k!} = \dfrac{(−1)(2k − 2)!2k}{k!k!} = \dfrac{(−1)(2k)!}{(2k − 1)k!k!} = \dfrac{-1}{2k − 1} \binom{2k}{k}, \)

por lo

\((1 − 4x)^{\dfrac{1}{2}} = −\sum_{k=0}^{\infty} \dfrac{1}{2k-1} \binom{2k}{k}x^k\)

Los coeficientes mostrados en el lado derecho de esta ecuación se vuelven rápidamente grandes y negativos.

Si

\(c(x) = \dfrac{1 + \sqrt{1-4x}}{2x} \)

entonces para\(n > 0\) el coeficiente de\(x^n\) in\(c(x)\) será la mitad del coeficiente de\(x^{n+1}\) in\((1 − 4x)^{\dfrac{1}{2}}\), que (cuando\(n\) es grande) será grande y negativo. Pero es fácil ver por la relación de recurrencia que todos los números catalanes son positivos. Para obtener coeficientes positivos, debemos usar

\(c(x) = \dfrac{1 - \sqrt{1-4x}}{2x} \)

Ya que en esta expresión tomamos el negativo de los grandes coeficientes negativos, el resultado serán grandes coeficientes positivos (incluso cuando dividimos por\(2\), y buscamos el coeficiente de\(x^{n+1}\)).

Por lo tanto,

\(c(x) = \dfrac{1 - (1 − 4x)^{\dfrac{1}{2}}}{2x} = \dfrac{1 + \sum_{k=0}^{\infty} \dfrac{1}{2k-1} \binom{2k}{k}x^k}{2x} \)

De esto, vemos que para\(n > 0\), el coeficiente de\(x^n\) in\(c(x)\) es la mitad del coeficiente de\(x^{n+1}\) in\((1 − 4x)^{\dfrac{1}{2}}\), que es

\( \begin{equation} \begin{split} \dfrac{1}{2} \binom{2(n+1)}{n+1} \dfrac{1}{2n+1}&= \dfrac{(2n+2)!}{2(n + 1)!(n + 1)!(2n + 1)} \\ &= \dfrac{1}{2} \cdot \dfrac{2n + 2}{n+1} \cdot \dfrac{(2n)!}{(n + 1)!n!} \cdot \dfrac{2n+1}{2n+1} \\ &= \dfrac{1}{n+1}\binom{2n}{n}. \end{split} \end{equation} \)

Entonces

\(c_n = \dfrac{1}{2n+1} \binom{2n}{n}\).

A pesar de que derivamos esta expresión por\(n > 0\) sólo, podemos verificar que\(c_0 = 1 = \dfrac{1}{0+1} \binom{0}{0}\) ya que\(0! = 1\), así esta expresión es cierta para cada uno\(n ≥ 0\).

Ejercicio\(\PageIndex{1}\)

1. Utilizar la inducción y la relación recursiva para los números catalanes (como ajustado para los valores de\(\{c_i\}\), dónde\(c_i = C_{i+1}\)) para demostrar que\(c_n > 0\) para cada\(n ≥ 0\).
2. Calcular\(c_4\) usando la fórmula explícita que calculamos en esta sección.
3. Calcular\(c_4\) usando la relación recursiva