Nombre de Schröder

En mathématiques, et notamment en combinatoire, un nombre de Schröder compte un certain type de chemins. Ce sont les chemins dans une grille de taille n × n reliant le point de coordonnées (0, 0) au point de coordonnées (n, n) en utilisant seulement des pas unités de direction nord, nord-est ou est, et qui ne dépassent pas la diagonale sud-ouest - nord-est. Un tel chemin est appelé un chemin de Schröder. Les premiers nombres de Schröder sont : 1, 2, 6, 22, 90, 394, 1806, 8558, .... (C'est la ). Ils sont nommés ainsi d'après le mathématicien allemand Ernst Schröder. Ils sont proches des nombres de Catalan, des nombres de Motzkin, des nombres de Schröder-Hipparque. Comme eux, ils possèdent de nombreuses interprétations combinatoires. thumb|upright=2|Les six chemins de Schröder d'une grille 2 × 2. thumb|upright=2|Les 6 chemins de Schröder de longueur 4 vus horizontalement : les pas horizontaux viennent par deux. Les nombres de Schröder comptent le nombre de chemins de (0, 0) à (2n, 0), formés depas unitaires nord-est et sud-est (pas (1, 1) ou (1, –1)) ou de pas horizontaux doubles (pas (2, 0)), et qui de plus sont toujours au-dessus de l'axe des x. Ils ressemblent en cela aux chemins de Motzkin, sauf qu'ici, les pas horizontaux viennent par deux. upright=2|thumb|Les 6 divisions en 3 rectangles par 2 coupures. thumb|upright=2|Les 22 rectangulations en 4 rectangles par 3 coupures. thumb|upright=2|Les 6 chemins de Motzkin colorés de longueur 2. Le n-ème nombre de Schröder compte aussi le nombre de subdivisions d'un rectangle en n + 1 rectangles plus petits obtenu par n droites horizontales ou verticales, avec la restriction qu'il y a n points à l'intérieur du rectangle qui ne sont alignés ni horizontalement ni verticalement, et que toute droite coupante passe par un des points et ne divise qu'un seul rectangle en deux. Sur la figure ci-dessous figurent les 6 subdivisions rectangulaires (rectangulations) en 3 rectangles avec 2 droites coupantes.

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

Publications associées (1)

Concepts associés (2)

Computation of Al-Salam Carlitz and Askey-Wilson moments using Motzkin paths

Gaspard Ohlmann

In this paper we study the moments of polynomials from the Askey scheme, and we focus on Askey-Wilson polynomials. More precisely, we give a combinatorial proof for the case where d = 0. Their values have already been computed by Kim and Stanton in 2015, h ...

ELECTRONIC JOURNAL OF COMBINATORICS2021

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 .

Nombre de Catalan

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