Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Nombre de Catalan
Résumé
En mathématiques, et plus particulièrement en combinatoire, les nombres de Catalan forment une suite d'entiers naturels utilisée dans divers problèmes de dénombrement, impliquant souvent des objets définis de façon récursive. Ils sont nommés ainsi en l'honneur du mathématicien belge Eugène Charles Catalan (1814-1894) qui les a étudiés en 1838, mais étaient déjà connus d'Euler.
Le nombre de Catalan d'indice n est défini par :
Pour , on peut écrire :
(voir Coefficient binomial central).
Les dix premiers nombres de Catalan (pour n de 0 à 9) sont :
(pour les premiers, voir les liens de la ).
La suite de Catalan est décrite pour la première fois en 1751 par le Suisse Leonhard Euler : dans une lettre à Goldbach, il pose le problème du dénombrement des triangulations d'un polygone, trouve les 8 premiers nombres, suggère une formule de produit explicite et trouve une forme explicite pour la fonction génératrice . Ce problème de triangulation est d'ailleurs aussi à l'origine indirecte du sudoku américano-japonais.
En 1758, Johann Andreas Segner reprend le problème des triangulations (faisant explicitement référence à Euler), prouve une relation de récurrence quadratique et utilise la formule pour calculer les 18 premiers nombres, les 6 derniers de manière incorrecte . Les futurs nombres de Catalan prennent alors le nom de nombres de Segner.
Ce n'est qu'en 1838 qu'Eugène Charles Catalan pose et résout le problème du "nombre de manières d'effectuer le produit de n facteurs différents" .
En 1839 Catalan fait le lien avec le nombre de triangulations, et publie un article complet sur le sujet en 1887. Depuis, le nom de Catalan remplace celui de Segner.
L'astuce de comptage des mots de Dyck est trouvée par Désiré André en 1887.
En 1988, dans la revue chinoise Neimenggu Daxue Xuebao, a été publié le fait que la suite des nombres de Catalan avait été utilisée en Chine par le mathématicien Ming Antu (ou Minggatu) dès 1730, lors de l'écriture de son livre , achevé par son élève Chen Jixin en 1774 et publié 60 ans plus tard.
P. J.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.