| G2976. Par monts et par vaux et par trois |
|
| G2. Combinatoire - Dénombrements |
|
Problème proposé par Pierre Leteurtre
Un chemin de Dyck à p monts et de longueur 2n est défini par une suite de segments U (pour Up) et de segments D (pour Down), organisés en une alternance de p segments UUU… et de p segments DDD….de telle sorte que le nombre de lettres D rencontrées depuis le début ne dépasse jamais le nombre de lettres U. Le passage d'un segment U à un segment D est un "mont", l'inverse est un val" (on dit aussi un sommet et un creux). Voici par exemple un chemin de Dyck symétrique à 4 monts et de longueur 2n = 18.  Prouver qu'il existe une bijection entre l'ensemble D4 des chemins de Dyck symétriques de longueur 2n à 4 monts et l'ensemble M4 des entiers multiples de 3 dont l'écriture en base 2 à n chiffres requiert exactement 4 chiffres 1. Solution |
