Números de Catalan (A000108) e triángulo de Narayana (A001263)

 por Andrés Ventas

$ \newcommand{\tei}[1]{\lceil #1 \rceil} \newcommand{\teib}[1]{\Big\lceil #1 \Big\rceil} \newcommand{\teig}[1]{\Bigg\lceil #1 \Bigg\rceil} \newcommand{\fa}[2]{\rlap{#1}\rule[9pt]{#2}{0.8pt}} \newcommand{\fd}[2]{\rlap{#1}\rule[-3pt]{#2}{0.8pt}} $ Esta entrada é un entretenemento numérico que xorde de botar unha ollada ás secuencias da OEIS A000108 Catalan numbers e OEIS A001263 Triangle of Narayana numbers.

Imos ver como se obteñen a partir dunha serie hiperxeométrica e unha fracción continua teito.

Recollendo o que se comenta na wikipedia (Catalan number) temos que se calculan como $C_{n}=\dfrac{1}{n+1}\displaystyle\binom{2n}{n}= \dfrac{(2n)!}{(n+1)!n!}$ dando lugar á secuencia:

$1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, \ldots$

Teñen varias interpretacións combinatorias como por exemplo ser o número de particións non cruzadas dun conxunto de $n$ elementos.

Aquí partición non cruzada defínese como:

Sexa $n$ un número natural e $P = \{B_1,\dots,B_k\}$ unha partición do conxunto $\{1,\dots,n\}$. Dise que esta partición é non cruzada se para todo $i \neq j$, os bloques $B_i$ e $B_j$ non se cruzan, é dicir, para todo $a,b \in B_i; \ c,d \in B_j,$ non é certo que $a \lt c \lt b \lt d$.

Por exemplo, $\{ \{1,2\}, \{3,4\} \}$ é unha partición sen cruzamento para $n=4$ pero $\{\{1,3\}, \{2,4\}\}$ non o é.

Números de Catalan xerados mediante unha función hiperxeométrica

Na páxina Wolfran Mathworld Catalan Number aparece que os números ce Catalan pódense obter mediante a función hiperxeométrica $_2F_1(1-n, -n; 2; 1)$, imos botar contiñas:

$ \begin{align} C_n={}_2F_1(1-n, -n; 2; 1) &= \sum_{k=0}^{\infty}\dfrac{(1-n)^{\fa{k}{7pt}}(-n)^{\fa{k}{7pt}}}{2^{\fa{k}{7pt}}k!}z^k; \\ &= 1 + \dfrac{(1-n)(-n)}{2}+ \dfrac{(1-n)(2-n)(-n)(1-n)}{2\cdot 3 \cdot 2!} + \\ & \quad\quad + \dfrac{(1-n)(2-n)(3-n)(-n)(1-n)(2-n)}{2\cdot 3 \cdot 4 \cdot 3!} + \\ & \quad\quad + \dfrac{(1-n)(2-n)(3-n)(4-n)(-n)(1-n)(2-n)(3-n)}{5! \cdot 4!} + \cdots \\ \end{align} $

E coidado aquí co símbolo de Pochhammer porque existe un lío de nomenclatura precisamente pola mor das series hiperxeométricas. Os parámetros das series hiperxeométricas son factoriais ascendentes pero escríbense tradicionalmente co índice abaixo: $(a)_n$ sería $ a(a+1)(a+2) \cdots (a+n-1)$ e cando necesitas usar na mesma fórmula factoriais ascendentes con descendentes non fica claro como representar os descendentes. Así que aquí vou usar o subliñado e sobreliñado de Donald Knuth $x^{\fd{k}{7pt}}=x(x-1)(x-2)\cdots (x-(k-1))$ para o factorial descendente e $x^{\fa{k}{7pt}}=x(x+1)(x+2)\cdots (x+k-1)$ para o factorial ascendente.

O último parámetro é $z=1$. Tendo en conta que as series hiperxeométricas rematan cando $a$ ou $b$ son números enteiros non positivos, e por tanto aquí remataría cando un termo $a - n$ faise cero, temos para cada $n$:

$ \begin{align} n=0; C_0 &= 1 + \dfrac{1\cdot 0}{2}= 1;\\ n=1; C_1 &= 1 + \dfrac{0\cdot -1}{2}= 1;\\ n=2; C_2 &= 1 + \dfrac{-1\cdot -2}{2} + \dfrac{0\cdot -1}{6\cdot 2}= 1 + 1 = 2;\\ n=3; C_3 &= 1 + \dfrac{-2\cdot -3}{2} + \dfrac{(-2)(-1)(-3)(-2)}{6\cdot 2}= 1 + 3 + 1 = 5;\\ n=4; C_4 &= 1 + \dfrac{-3\cdot -4}{2} + \dfrac{(-3)(-2)(-4)(-3)}{6\cdot 2} \\ & \quad\quad + \dfrac{(-3)(-2)(-1)(-4)(-3)(-2)}{24\cdot 6}= 1 + 6 + 6 + 1 = 14;\\ n=5; C_5 &= 1 + \dfrac{-4\cdot -5}{2} + \dfrac{(-4)(-3)(-5)(-4)}{6\cdot 2} + \dfrac{(-4)(-3)(-2)(-5)(-4)(-3)}{24\cdot 6} \\ & \quad\quad + \dfrac{(-4)(-3)(-2)(-1)(-5)(-4)(-3)(-2)}{120\cdot 24} = 1 + 10 + 20 + 10 + 1 = 42;\\ &\cdots \end{align} $

E vemos que os sumandos van formando os valores do triángulo de Narayana.

Como o triángulo de Narayana comeza con $k=1$ e aquí os sumandos comezan en $k=0$ e a maiores $(1-n){^\fa{k-1}{15pt}} (-n)^{\fa{k-1}{15pt}} = (n-1)^{\fd{k-1}{15pt}} \ n^{\fd{k-1}{15pt}},$ daquela temos que os coeficientes do triángulo de Narayana poden definirse como $N(n,k) = \dfrac{(n-1)^{\fd{k-1}{15pt}} \ n^{\fd{k-1}{15pt}}}{k!(k-1)!}$ e isto coincide coa fórmula usual dos coeficientes do triángulo de Narayana:

$ \begin{align} C_n &= \dfrac{1}{n}\displaystyle\binom{n}{k} \displaystyle\binom{n}{k-1} \\ &= \dfrac{1}{n} \cdot \dfrac{n^{\fd{k}{7pt}}}{k!} \cdot \dfrac{n^{\fd{k-1}{15pt}}}{(k-1)!} \\ &= \dfrac{(n-1)^{\fd{k-1}{15pt}} \ n^{\fd{k-1}{15pt}}}{k!(k-1)!}. \end{align} $

Números de Catalan xerados mediante unha fracción continua

Imos ampliar ampliar a fórmula da entrada de retallos Relación entre series infinitas, fraccións continuas teito e constantes. Series hiperxeométricas. Final. para recoller tamén a fórmula dos converxentes:

Para a suma $S=\frac{1}{u_0}+\frac{1}{u_0 u_1}+\frac{1}{u_0 u_1 u_2}+\cdots $

Se pasamos a unha $fctx$ temos: $ S^{-1}= \teig{ \begin{matrix} - & u_0 & u_1 & u_2 & u_3 &\ldots\\ u_0 & u_1 + 1 & u_2 + 1 & u_3 + 1 & u_4 + 1 & \ldots \end{matrix} }$

Os converxentes da inversa da fracción continua serían $B_i/A_i$. $ S^{-1}= \teig{ \begin{matrix} A_i & 1 & u_0 & u_0 (u_1+1) - u_0 =u_0u_1 & u_2 u_1 u_0 + u_1 u_o - u_1 u_0 = u_2 u_1 u_0 &\ldots \\ B_i & 0 & 1 & u_1 + 1 & (u_1 + 1)(u_2+1) - u_1 = u_2(u_1 + 1) +1 & u_3 (u_2(u_1 + 1)+1) + 1 & \ldots \end{matrix} }$

Observamos outra forma de expresar os $B_i$, por exemplo $u_3 (u_2(u_1 + 1)+1) + 1=u_3 u_2u_1 + u_3u_2 + u_3 +1$.

Por tanto $A_i= \prod_{j=0}^{i}u_j; \quad B_i = \big(\sum_{k=1}^{i} \prod_{j=k}^{i}u_j \big) + 1.$

E aquí perden a súa maxia as fraccións continuas teito xeneralizadas pois se realizamos esta suma do xeito tradicional e sen simplificar temos un resultado cuspidiño:

$S=\frac{1}{u_0}+\frac{1}{u_0 u_1}+\frac{1}{u_0 u_1 u_2}+\cdots = \frac{u_1 + 1}{u_0 u_1} + \frac{1}{u_0 u_1 u_2}+\cdots = \frac{u_2(u_1 + 1)+1}{u_0 u_1 u_2} +\cdots$

No noso caso partindo da función hiperxeométrica

$ \begin{align} C_n={}_2F_1(1-n, -n; 2; 1) &= 1 + \dfrac{(1-n)(-n)}{2}+ \dfrac{(1-n)(2-n)(-n)(1-n)}{2\cdot 3 \cdot 2!} + \\ & \quad\quad + \dfrac{(1-n)(2-n)(3-n)(-n)(1-n)(2-n)}{2\cdot 3 \cdot 4 \cdot 3!} + \\ & \quad\quad + \dfrac{(1-n)(2-n)(3-n)(4-n)(-n)(1-n)(2-n)(3-n)}{5! \cdot 4!} + \cdots \\ \end{align} $

Temos $u_0=1, u_1=\dfrac{2}{(1-n)(-n)}, u_2=\dfrac{3 \cdot 2}{(2-n)(1-n)}, u_3=\dfrac{4 \cdot 3}{(3-n)(2-n)}, u_4=\dfrac{5 \cdot 4}{(4-n)(3-n)},\cdots;$

Imos botar contas para $n=4$ e $n=5$:

Para $n=4$

$ \begin{align} & u_0=1; u_1=\dfrac{1}{6}; u_2=1; u_3= 6. \\ A_3 &= 1\cdot \dfrac{1}{6} \cdot 1 \cdot 6 = 1. \\ B_3 &= \dfrac{1}{6} \cdot 1 \cdot 6 + \cdot 1 \cdot 6 + 6 + 1= 1 + 6 + 6 + 1 = 14. \\ \end{align} $

Para $n=5$

$ \begin{align} & u_0=1; u_1=\dfrac{1}{10}; u_2=\dfrac{1}{2}; u_3=2; u_4= 10. \\ A_4 &= 1\cdot \dfrac{1}{10} \cdot \dfrac{1}{2} \cdot 2 \cdot 10 = 1. \\ B_4 &= \dfrac{1}{10} \cdot \dfrac{1}{2} \cdot 2 \cdot 10 + \dfrac{1}{2} \cdot 2 \cdot 10 + \cdot 2 \cdot 10 + 10 +1 = 1 + 10 + 20 + 10 + 1 = 42. \\ \end{align} $

E pouco máis que agregar, todo cadra despois de botar contas de diversos xeitos.