Ê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 Motzkin
Résumé
vignette|Les façons de choisir des cordes, pour 4 points.
vignette|Les arbres unaires-binaires, pour 4 arcs. Les arbres sont en bijection avec les cercles.
vignette|Les chemins de Motzkin, pour 4 pas. Les chemins sont en bijection avec les arbres.
En mathématiques, et plus particulièrement en combinatoire, les nombres de Motzkin forment une suite d'entiers naturels utilisée dans divers problèmes de dénombrement. Ils sont nommés ainsi d'après le mathématicien Théodore Motzkin (1908-1970). Les nombres de Motzkin ont de nombreuses applications en géométrie, combinatoire et théorie des nombres.
Le nombre de Motzkin d'indice est le nombre de façons de choisir des cordes ne se coupant pas, parmi les cordes reliant points disposés sur un cercle. Les nombres de Motzkin satisfont la relation de récurrence suivante :
Les nombres de Motzkin correspondent à la et les premiers de ces nombres sont:
{| class="wikitable"
|+ Nombres de Motzkin
|-----
|
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
| 9
| 10
| 11
|-
|
| 1
| 1
| 2
| 4
| 9
| 21
| 51
| 127
| 323
| 835
| 2188
| 5798
|}
Commençons par démontrer la relation de récurrence énoncée dans l'introduction. Parmi n+1 points disposés sur un cercle, choisissons-en un, soit P. Le nombre de façons de choisir des cordes ne se coupant pas et joignant des points choisis parmi les n+1 points en question et tous distincts de P est égal à . D'autre part, si pour j dans {1, 2, ..., n}, désigne le j-ième point après P dans un sens fixé de parcours du cercle, le nombre de façons de choisir des cordes possédant les propriétés voulues et telles qu'une de ces cordes soit la corde est le nombre de façons de choisir d'une part un ensemble de cordes convenable relativement aux points et d'autre part un ensemble de cordes convenable relativement aux points . Ces deux choix sont indépendants l'un de l'autre, le nombre de façons de faire le premier est le nombre de façons de faire le second est , donc le nombre de façons de faire les deux choix est , d'où
Jointe à cette relation détermine les nombres de Motzkin.
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.