Nombre de Motzkin

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.

À 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.

Concepts associés (2)

Nombre de Narayana

En combinatoire, les nombres de Narayana , pour et forment un tableau triangulaire d'entiers naturels, appelé triangle de Narayana ou triangle de Catalan. Ces nombres interviennent dans divers problèmes de dénombrements. Ils portent le nom de Tadepalli Venkata Narayana (1930-1987), mathématicien canadien. Les nombres de Narayana s'expriment en fonction des coefficients binomiaux par la relation : On trouve aussi la définition équivalente : Les premiers nombres du triangle de Narayana sont les suivants : Ils forment la .

Coefficient binomial

En mathématiques, les coefficients binomiaux, ou coefficients du binôme, définis pour tout entier naturel n et tout entier naturel k inférieur ou égal à n, donnent le nombre de parties à k éléments d'un ensemble à n éléments. On les note - qui se lit « k parmi n » - ou , la lettre C étant l'initiale du mot « combinaison » Les coefficients binomiaux s'expriment à l'aide de la fonction factorielle : Ils interviennent dans de nombreux domaines des mathématiques : développement du binôme en algèbre, dénombrements, développement en série, lois de probabilités, etc.