Números de Catalan

n	$C_{n}$
0	1
1	1
2	2
3	5
4	14
5	42
6	132
7	429
8	1.430
9	4.862
10	16.796
11	58.786
12	208.012
13	742.900
14	2.674.440
15	9.694.845
16	35.357.670
17	129.644.790
18	477.638.700
19	1.767.263.190
20	6.564.120.420
21	24.466.267.020
22	91.482.563.640
23	343.059.613.650
24	1.289.904.147.324
25	4.861.946.401.452

En combinatòria, els números de Catalan formen una seqüència de número natural que apareix en varis problemes de conteo que habitualment són recursivos. El seu nom fa referència al matemàtic belga Eugène Charles Catalan (1814-1894).

El n-ésimo número de Catalan s'obté, aplicant coeficients binomiales, a partir de la següent fòrmula:

C_{n} = \frac{1}{n + 1} (\binom{2 n}{n}) = \frac{(2 n)!}{(n + 1)! n!} con n \geq 0.

Història

La seqüència de números de Catalan va ser descrita en el XVIII per Leonhard Euler. La seqüència du el nom d'Eugène Charles Catalan, qui va descobrir la conexió en les expressions entre paréntesis durant la seua exploració del rompecabezas de les torres de Hanói.

En 1988, va eixir a la llum que la seqüència numèrica de Catalan havia segut utilisada en China pel matemàtic mongol Minggatu cap a 1730.^[1]^[2] Va ser quan va començar a escriure el seu llibre Ge Yuan El meu Lu Jie Fa [El método ràpit per a obtindre la relació precisa de divisió d'un círcul], que va ser completat pel seu alumne Chen Jixin en 1774, pero publicat xixanta anys despuix.

Propietats

Una expressió alternativa per a C_n és

C_{n} = (\binom{2 n}{n}) - (\binom{2 n}{n - 1}) con n \geq 1.

Esta atra expressió mostra que C_n és un número natural, la qual cosa no resulta obvi a priori observant la primera fòrmula donada.

Una forma curiosa de generar C_n, derivada de les fòrmules anteriors, és a partir del factorial de qualsevol número entero parell $(2 n)!$ . Es dividixen tots els térmens situats a l'esquerra del factor $n + 1$ , entre tots els térmens situats a la seua dreta i el resultat serà el n-ésimo número de Catalan.

Els números de Catalan satisfan la següent relació de recurrencia:

C_{0} = 1 y C_{n + 1} = \sum_{i = 0}^{n} C_{i} C_{n - i} con n \geq 0.

I també satisfan:

C_{0} = 1 y C_{n + 1} = \frac{2 (2 n + 1)}{n + 2} C_{n},

que pot ser una forma més eficient de calcular-los.

L'expressió en forma de recursión seria:

C_{n} = {\begin{matrix} si n = 0 & \Rightarrow 1 \\ si n > 0 & \Rightarrow \frac{2 (2 n - 1)}{n + 1} C_{n - 1} \end{matrix}

Asintóticament, els números de Catalan creixen com:

C_{n} \sim \frac{4^{n}}{n^{3 / 2} \sqrt{π}}

considerant que el cocient entre el n-ésimo número de Catalan i l'expressió de la dreta tendix cap a 1 quan n → ∞ (açò pot provar-se usant la fòrmula de Stirling).

Referències

↑ Larcombe, Peter J.. «The 18th century Chinese discovery of the Catalan numbers».
↑ «Ming Antu, the First Inventor of Catalan Numbers in the World». Archivat des d'el original, el 31 de giner de 2020. Consultat el 18 de maig de 2021.

Referències

Este artícul conté una traducció derivada de «Números de Catalan» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Larcombe, Peter J.. «The 18th century Chinese discovery of the Catalan numbers».

[2] «Ming Antu, the First Inventor of Catalan Numbers in the World». Archivat des d'el original, el 31 de giner de 2020. Consultat el 18 de maig de 2021.

[1]

[2]