Catalan et permutations finies
dans Arithmétique
bonjour,
je m'intéresse quelque peu aux nombres de Catalan.
Entre autres, est-il possible de montrer (par dénombrement)
que le nombre de permutations a telles que non ( i<j<k => a(i)<a(j)<a(k) )
est un nombre de Catalan.
Cela n'a pas l'air trivial par récurrence semble-t-il.
Cordialement
Alain
je m'intéresse quelque peu aux nombres de Catalan.
Entre autres, est-il possible de montrer (par dénombrement)
que le nombre de permutations a telles que non ( i<j<k => a(i)<a(j)<a(k) )
est un nombre de Catalan.
Cela n'a pas l'air trivial par récurrence semble-t-il.
Cordialement
Alain
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Alain
, par exemples avec 3 wagons, les suites ()()(), (())(), etc, une parenthese
ouvrante correspond à un mouvement de wagon vers la voie parallelle, une fermante à la remise au garage du dernier mis sur cette voie.
Cela fonctionne tant qu'il n'existe pas i<j<k tel que ai < aj < ak.
Donc le probleme est bien isomorphe à celle des permutations et on tombe donc sur les nombres de catalan.
exemple: on ne peut ranger les entiers dans l'ordre 4321 que si les permutations obtenues en appliquant des mouvements du type précédent
donne la configuration de départ , et cela concerne aussi uniquement les
permutations telles que: non ( i<j<k => ai < aj < ak) de façon à pouvoir pratiquer des mouvements. Soit C4 = 14 permutations sur les 24 possibles.
Pas besoins de récurrence, en fait. Pas du tout même.
Cordialement
Alain