Catalan Zahl < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 16:04 Mi 28.05.2008 | | Autor: | polo |
| Aufgabe | Bei einer Wahl stehen die zwei Kandidaten A und B zur Auswahl ; insgesamt
werden 2n Stimmen abgegeben und jeder der beiden Kandidaten erhält genau n Stimmen ( n [mm] \in \IN [/mm] ) . Bei jedem Zwischenstand der Abzählung hat A jedoch
mehr Stimmen als B . Zeige :
Die Anzahl der möglichen Varianten der Stimmabzählung ist gegeben durch die
Catalan-Zahl C(n) . |
Hallo,
ich wäre sehr dankbar ,wenn jemand mir zu dieser Aufgabe einen Tipp geben könnte.
Grüße,
Polo
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Grüße!
Das hängt alles ein wenig von eurer Definition der Catalanzahl ab. Ich habe um mein Gedächtnis aufzufrischen bei Wikipedia nachgesehen:
![[]](/images/popup.gif) Wikipedia-Artikel Catalan Zahl
Und da fanden sich auch einige recht anschauliche Beweise für das Problem... mach Dir zunächst klar, dass die dort beschriebenen Dyck-Worte bzw. monotonen Pfade im $n [mm] \times [/mm] n$ Gitter, die unterhalb der Diagonalen verlaufen exakt den gesuchten Stimmverteilungen entsprechen.
Gruß,
Lars
|
|
|
|
