Arbres binomiaux et récurrences
Répondre à la discussion
Affichage des résultats 1 à 2 sur 2

Arbres binomiaux et récurrences



  1. #1
    sperca

    Arbres binomiaux et récurrences


    ------

    Bonjour à tous,

    J'essaye actuellement de résoudre un problème proposé par les auteurs du livre "Introduction à l'algorithmie" (le Cormen pour ceux qui connaissent). Ce problème concerne les arbres binomiaux et la numérotation de leur noeud dans l'ordre postfixe.

    Il faut montrer qu'à la profondeur i, une étiquette (numéro du noeud en base 2) possède (k - i) '1'. J'ai différentes idées mais aucune ne semblent pouvoir me faire avancer...

    J'expose rapidement mes idées.

    Un arbre binomial Bk contient 2^k noeuds donc à l'aide d'un parcours postfixe, la racine de ce sous arbre est numérotée 2^k - 1 (On numérote à partir de 0). Donc à partir de là j'ai essayé de trouver une règle de numérotation pour les noeuds situés à une même profondeur en utilisant la définition sur la construction d'un Bk à partir de ses k - 1 fils... Mais je ne sais pas trop comment conclure...

    Ensuite j'ai tenté de trouver une relation entre un noeud et son frère. Toujours dans l'espoir de montrer que le nombre de 1 ne varie pas (à l'aide d'opération de décalage liées aux puissances de 2 etc).

    J'ai également essayé avec le nombre de noeuds présents à une certaine profondeur (combinaison de i parmi k à la profondeur i d'un Bk)...

    Bref, j'ai testé pas mal de chose (peut-être un peu trop...) et je commence à me demander si je ne loupe pas quelque chose de "simple".

    Si vous pouviez m'aiguiller dans une direction ou dans une autre, merci à vous

    --
    sperca

    -----

  2. #2
    sperca

    Re : Arbres binomiaux et récurrences

    Salut,

    Mon énoncé n'est pas assez clair ? Ou les problèmes algorithmiques ne sont pas traités dans cette section ?

    Merci à vous.

    Sperca

Discussions similaires

  1. Relation : Coefficients binomiaux
    Par invitefe34e79f dans le forum Mathématiques du collège et du lycée
    Réponses: 5
    Dernier message: 06/08/2010, 01h56
  2. Relation entre coeff. binomiaux
    Par mx6 dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 08/12/2009, 19h57
  3. Nombres premiers et coefficients binomiaux
    Par Gpadide dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 02/03/2007, 18h55
  4. Recurrences...
    Par invite3ac51b88 dans le forum Mathématiques du collège et du lycée
    Réponses: 18
    Dernier message: 20/09/2006, 22h27
  5. demonstration avec coef binomiaux
    Par .:Spip:. dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 18/04/2005, 15h48