Le nombre d'arbres binaires qui peuvent être créés avec les clés N est donnée par la Nième catalan nombre. Pourquoi?

Cela a été me tracasse depuis un moment. Je sais que, étant donné les clés N à organiser sous la forme d'un arbre de recherche binaire, le nombre possible d'arbres qui peuvent être créés correspondent à la n-ième nombre de la Catalan séquence.

J'ai été d'essayer de déterminer pourquoi il en est; impossible de trouver quelque chose qui pourrait même tenter de l'expliquer intuitivement, je recours à la convention collective de la connaissance de soi. J'ai trouvé d'autres façons de calculer le nombre d'arbres possibles, mais ils semblaient moins intuitif et aucune explication n'a été offert au-delà de la façon de l'utiliser. En Plus de la page wiki (lien ci-dessus) montre même une image de l'arborescence possible des formations avec 3 clés, ce qui m'a conduit à penser qu'il ya un beau et soigné explication à être entendu (ce qui est, cela va sans dire, ne figurant pas dans l'article).

Merci d'avance!

  • Question très intéressante, même si je ne suis pas sûr que c'est vraiment relatives à la programmation :-/ Semble que plus d'un résumé de mathématiques (topologie) chose.
  • Euh, cela n'a rien à voir avec la topologie de!
  • Quelle est votre question? Vous vous demandez pourquoi le nombre d'arbres binaires à N clés est le même que celui de la quantité indiquée sur la page du nombres de Catalan, ou vous vous demandez à propos de l'expression pour les nombres de Catalan eux-mêmes (ce qui est prouvé sur la page de quatre façons)?
  • Je me demandais comment faire pour déterminer le nombre de techniciennes se chargent qui peut être créé étant donné un nombre N de nœuds. J'ai découvert que la réponse à cette question est la même comme demandant "Quel est le n-ième nombre de catalan séquence?", mais même si la formule est facilement disponible sur cet article de wiki, j'aimerais une explication de pourquoi cela fonctionne. Je n'aime pas à accepter les méthodes sans quelques explications de leur logique interne ou certaines de base, intuitive description autre qu'une formule.
  • Cela s'applique à des arbres binaires, en général, il n'a rien à voir avec les spécificités de l'arbre de recherche.
  • vous êtes tout à fait tort
  • Juste pour info - lien: codingworkout.blogspot.com/2014/08/...

InformationsquelleAutor Sergio Morales | 2009-08-30
  1. 14

    Puisqu'il y a quatre épreuves dans l'article de wikipedia que vous l'avez mentionné, il semble que vous n'êtes pas à la recherche d'une explication mathématique pour la correspondance entre les nombres de Catalan et les permutations d'un arbre binaire.

    Donc, au lieu de cela, voici deux façons d'essayer et de façon intuitive de visualiser la façon dont le Catalan séquence (1, 2, 5, 14, 42, ...) se pose, dans la combinatoire des systèmes.

    Découper les polygones en triangles

    Pour un polygone à côtés N, de combien de façons peut-on en tirer des coupures entre les sommets que chop le polygone entièrement en triangles?

    • Triangle (N=3): 1 (C'est déjà un triangle)
    • Carré (N=4): 2 (Peut découper à la diagonale)
    • Pentagone (N=5): 5 (Deux découpage lignes émanant d'un sommet. Cinq sommets au choix)
    • Hexagone (N=6): 14 (Essayez le dessin)
    • ...et ainsi de suite.

    Dessin d'un chemin à travers une grille sans traverser la diagonale

    Dans ce cas, le nombre de chemins d'accès unique est le Catalan nombre.

    Grille 2x2 => 2 chemins

      _|       |
_|       __|

    Grille 3x3 => 5 chemins

        _|       |       _|         |         |
  _|      _ _|      |          _|         |
_|      _|       _ _|      _ _|      _ _ _|

    Grille 4x4 => 14 chemins

    Grille de 5x5 => 42 chemins

    et ainsi de suite.

    Si vous essayez de tracer les possibles des arbres binaires, pour un certain N, vous verrez que le chemin de l'arbre permute est la même.

    Votre désir de ne pas accepter aveuglément la correspondance entre l'arbre et la séquence est admirable. Malheureusement, il est difficile d'aller beaucoup plus loin dans cette discussion (et expliquer pourquoi le Catalan formule "arrive à" la façon dont il est), sans faire appel à du binôme de mathématiques. Le Wikipedia de discussion de coefficients binomiaux est un bon point de départ si vous voulez comprendre la combinatoire (qui comprend permutation de comptage) lui-même en plus de profondeur.

    InformationsquelleAutor ire_and_curses
  2. 7

    catalan http://www.nohre.se/publicImages/catalan.png

    Binaires un arbre de recherche peut être codé par la visite de tous les nœuds de pré-commande et de coder un 1 pour chaque parent et un 0 pour chaque feuille. Si l'arbre a n parents il aura n+1 feuilles et, par conséquent, le code binaire aura n 1:s et (n+1) 0:s. En outre, et tout préfixe du code devront avoir au moins autant d'1:s comme il a 0:s. Par conséquent, le nombre d'arbres possibles est égal au nombre de chemins en dessous de la diagonale.

    • Si vous n'avez pas prouver qu'il y a une correspondance entre les arbres et leur codage binaire à votre argument est inutile.
    • Euh, vous êtes à l'aide de précommande dans votre exemple!
    • Désolé, je ment de pré-commande (corrigé)
    InformationsquelleAutor ragnarius
  3. 2

    Et bien voici la solution récursive de compter les arbres...

    int countTrees(int numkeys){

if(numkeys > 1){
    int i =1;
    int sum=0;

    for(i = 1; i <= numkeys; i++){

        int lcount = countTrees(i-1);
        int rcount = countTrees(numkeys-i);
        sum += lcount*rcount;
    }
    return(sum);
}else
    return(1);
}
    InformationsquelleAutor Sid