G221. Photos de famille Imprimer
G2. Combinatoire - Dénombrements
calculator_edit.png  

Diophante aime prendre en photo ses 7 petits-enfants qui sont tous de taille différente. Il les aligne de telle façon que chacun est plus grand que tous ceux placés avant lui ou plus petit que tous ceux placés après lui. Combien peut-il faire de photos avec des dispositions différentes ?



Pour les plus courageux, donner une généralisation avec n petits-enfants tous de taille différente (n 3).


Pour les plus curieux, quelle est la parenté de ce problème avec le problème G17 "Référendum" ?


Source : Pierre Henri Palmade



 Solution


Pierre Henri Palmade,Jean Moreau de Saint Martin et Daniel Collignon ont résolu le problème avec ses deux interprétations possibles.
Commentaires

Comme l'ont montré les trois réponses ci-dessus, le résultat demandé est le nombre de Catalan quelle soit l'interprétation retenue. Ce même nombre a été calculé dans le problème G217 Référendum. Il intervient dans d'autres problèmes de combinatoire qui sont analysés dans le document Catalan Numbers de Tom Davis et sur le site http://fr.wikipedia.org/wiki/Nombre_de_Catalan