Catalan-Zahlen[MATHE]

    • schoe01
      schoe01
      Bronze
      Dabei seit: 21.09.2009 Beiträge: 741
      Hi Leute,

      der Matheclown hat mal wieder vorbeigeguckt und hat mir folgende Aufgabe hinterlassen :

      Cn bezeichne die n-te Catalan-Zahl. Zeigen Sie: Es gibt genau Cn−2 Möglichkeiten, ein konvexes n-Eck durch Diagonalen in lauter Dreiecke zu zerlegen, wenn keine zwei Diagonalen einander überschneiden dürfen.

      HILFE .... Keinen Plan von gar nix ... :( wär super, wenn jemand von euch einen Lösungsvorschlag bzw einen Lösungsweg hat ...
  • 1 Antwort
    • Blinzler
      Blinzler
      Bronze
      Dabei seit: 04.03.2005 Beiträge: 7.456
      grad schon bisserl spät und von daher kein bock mehr, das auszuprobieren.
      aber mein ansatz wäre folgender.

      wir schauen uns so ein (n+1)-eck an.
      jetzt wählen wir uns eine ecke davon aus. die müssen wir ja irgendwie mit ner anderen ecke verbinden. da bleiben uns dann noch (n+1)-3 ecken übrig (die ecke selber und die 2 benachbarten gehen ja nicht, da dadurch keine dreiecke enstehen würden). damit bilden sich 2 neue vielecke mit weniger als (n+1) ecken und für die können wir nach induktion die anzahl dreiecke bestimmen, nämlich gerade die catalan zahlen.
      was man dann eigentlich nur noch machen müsste, wäre es eben, sich die summe aufzuschreiben und dann eben zu addieren. da sollte dann das richtige rauskommen.