On nous donne des "N" paires de parenthèses, c'est-à-dire "N" parenthèse ouvrante "(" et "N" parenthèse fermante ")". Nous sommes invités à trouver le nombre de façons de faire la séquence de 2N parenthèses qui sont BON, , c'est-à-dire que nous ne fermons pas avant l'ouverture.Recherche d'une définition de problème combinatoire
J'ai besoin de trouver une définition pour GOOD séquences que je peux utiliser pour la suite du problème.
Numéros catalans!
Vous pourriez avoir ajouté un lien pour les paresseux. ;-) – Chris
La meilleure présentation des nombres catalans que je connaisse est celle de * Le livre des nombres * de Conway et Guy. Aux pages 101-104, ils expliquent le lien entre les motifs de frise, les dissections de polygones, les arbres binaires, les exponentiations, les buissons enracinés et les expressions entre parenthèses. –
http://en.wikipedia.org/wiki/Catalan_number semble être une référence en ligne appropriée. Certainement intéressant pour moi et mentionne explicitement le problème ci-dessus. – Chris
Techniquement, c'est la même question que le nombre d'arbres de recherche binaires distincts contenant n nœuds. – st0le