Nombres de Catalan: diferència entre les revisions

Aquesta altra expressió mostra que '' C '' _{'' n ''} és un [[nombre natural]], la qual cosa no resulta obviòbvia '' a priori '' mirant la primera fórmula donada.

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

considerant que el quocient entre ell' '' n ''-ésimoèsim nombre de Català i l'expressió de la dreta [[límit matemàtic|tendeix cap]] 1 quan '' n '' → ∞ (això es pot provar usantfent ús de la [[fórmula de d'Stirling]]).

Hi ha múltiples problemes de [[combinatòria]] on la solució la donen els nombres de Catalan. El llibre '' Enumerative Combinatorics: Volume 2 '' ded'en '' Richard P. Stanley '' conté un conjunt d'exercicis que descriuen 66 interpretacions diferents dels nombres de Catalan. Aquí es mostren alguns exemples, amb il·lustracions per al cas '' C '' ₃ = 5.

* Reinterpretar el símbol X com un [[parèntesi]] obert i la I com un parèntesi tancat, '' C '' _{'' n ''} compte el nombre d'expressions que contenen '' n '' parells de parèntesis correctament col ·locats:

* '' C '' _{'' n ''} és el nombre de formes diferents d'agrupar '' n ''+1 factors mitjançant parèntesis (o el nombre de formes de d'[[propietat associativa|associar]] '' n '' aplicacions d'un [[operador binari]]). Per '' n '' = 3 per exemple, tenim les següents cinc formes diferents d'agrupar els quatre factors:

* Les aplicacions successives d'un operador binari es poden representar amb un [[arbre binari]]. En aquest cas, '' C '' _{'' n ''} és el nombre de [[Arbre (estructura de dades)|arbres]] binaris ded' '' n ''+1 fulles, en els quals cada node té zero o dos fills:

* '' C '' _{'' n ''} és el nombre de ''' camins monòtons ''' que es poden traçar a través de les línies d'una malla de '' n '' × '' n '' cel quadrades, de manera que mai es cruïllacreuï la diagonal. Un camí monòton és aquell que comença a la cantonada inferior esquerra i acaba ena la part superior dreta, i consisteix únicament en trams que apunten cap amunt o cap a la dreta. El recompte d'aquests camins és equivalent a comptar paraules de Dyck: X significa "moure's a la dreta" i Y significa "moure's cap amunt". Els següents diagrames mostren el cas '' n '' = 3:

* '' C '' _{'' n ''} és el nombre de formes diferents de tallar un [[polígon]] convex ded' '' n ''+2 costats a [[triangle]]s connectant vèrtexs amb [[recta|línies rectes]] sense que cap es talli. La següent figura il·lustra el cas dels polígons de 5 costats, quan '' n '' = 3: