Chemins de Manhattan sur une grille

INDEX Dénombrement Graphe Jeux et énigmes Logique Logique Topologie	Types de Nombres – GRILLES
	Suites pour dénombrer	Nombres de Catalan	Chemin sur réseau
	Nombres Manhattan	Nombres de Narayana	Chemin auto-évitant
	Taxi dans Manhattan	Nombres de Delannoy	Chemin le plus court
	Périple du cavalier	Nombres octaédriques	Diagramme de Voronoï
	Périple de la tour	Nombres de Motzkin	Nombres de Dyck

Faites un double-clic pour un retour en haut de page

CHEMINS de MANHATTAN

Chemin dessiné sur une grille (anglais: lattice path).

Déplacement vers la droite ou vers le haut seulement. Par nature, ces chemins sont naturellement auto-évitants.
Comme un taxi circulant dans les rues de New York.

C'est aussi la manière dont se déplace la tour aux échecs.

En interdisant les déplacements au dessus de la diagonale montante, on définit les nombres de Dyck.

Sommaire de cette page

>>> Approche: déplacement de la tour

>>> Déplacement de la tour – Dénombrement

Débutants

Dénombrement

Glossaire

Combinatoire

Manhattan

À New York, dans le quartier de Manhattan, les rues se croisent à angle droit. Le plan date de 1811, créant une matrice de rues presque parfaite.

Approche: déplacement de la tour		haut
Mouvement de la tour aux échecs Dans ce cas, la tour part du coin bas-gauche et doit rejoindre le coin haut-droit en se déplaçant vers la droite ou vers le haut. Quelle est la quantité de chemins possibles sur l'échiquier 8 × 8 ? Ce type de chemin est aussi qualifié de parcours du taxi dans les rues à angle de droit de Manhattan (New York). C'est aussi les façons de monter les marches d'un escalier en admettant des marches de toute taille (staircase walk).	Voir Échecs
Sur une seule case (2 × 2 points) Rejoindre le coin supérieur peut s'effectuer de deux manières. T(1) = 2
Sur une grille 3 × 3 points Rejoindre le coin supérieur peut s'effectuer de deux manières. T(2) = 6 On compte (figure du bas) Chaque point représente le centre d'une case de l'échiquier. Notez que: le côté mesure deux unités, mais il y a trois points sur un côté. Pour aller du départ (D) à l'arrivée (A), il y a 6 chemins possibles: 1 chemin pour aller en B ou en C ou en E ou en H; 2 chemins pour aller en F: 1 en passant par B et 1 en passant par E. 3 chemins pour aller en G: 1 en passant par C et 2 en passant par F. Idem pour I. 6 chemins pour aller en A: 3 en passant par G et 3 en passant par I.

Déplacement de la tour – Dénombrement		haut
Échiquier complet 8 × 8 Chaque point est repéré par la quantité de chemins possibles pour l'atteindre. C'est la somme des deux quantités en bas et sur la gauche. Oui ! C'est bien le triangle de Pascal selon la diagonale descendante (Voir en bas à gauche): 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 …
Formule Quantité de chemin depuis l'origine pour rejoindre le point de coordonnées (a, b): expression en coefficient binomial. Notez que le point origine à pour coordonnées (0, 0) et le point en haut à droite (7, 7).	Exemple pour le point A (7,7)

Formule

Ces nombres sont les nombres de Catalan; calculé à partir du nombre central sur chaque ligne du triangle de Pascal

Exemple n = 3

Nombres de Catalan

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004, … OEIS A000108

Applications

Exemples

Richard Stanley en avait identifié 214.

Expressions contenant n paires de parenthèses qui sont correctement assorties;

Différentes manières de découper un polygone convexe à n + 2 côtés en triangles en reliant les sommets par des lignes droites.

Arbres binaires à n nœuds internes (n + 1 feuilles).

Permutations de l'ensemble {1, 2, …, n} qui évitent le motif 321. Une permutation P évite le motif 321 si on ne trouve pas une sous-suite xyz de P telle que x > y > z.

Haut de page (ou double-clic)

Suite	*Voir* haut de page Chemins de Dyck Mots de Dyck Chemin auto-évitant Chemin eulérien Chemin de la fourmi sur pavé, cylindre … Graphe – Index
Voir	Diagramme de Venn Dominos et graphe Échiquier et graphe Énigmes et paradoxes Intelligence artificielle	Jeux – Index Logique formelle Projet Manhattan (bombe atomique) Raisonnement Topologie – Glossaire
Sites	Self-avoiding Walks – OEIS – Une revue des différents types Chemin auto-évitant – Wikipédia Self-avoiding walk – Wolfram MathWorld Chemins auto-évitants : autour de la constante de connectivité – Cécile Gachet Dyck path enumeration – Emeric Deutsch – 1997 Combinatorics of r-Dyck paths, r-parking functions, and the r-Tamari lattices – F. Bergeron – 2012 – pdf 36 pages
Cette page	http://diconombre.fr/LogForm/Manhatt.htm