kombinatorisches Zählen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Wieviele monotone Wege gibt es in einem Gitter mit Kantenlängen 7 × 5 zwischen den diagonal gegenüberliegenden Eckpunkten A und Z? Monoton bedeutet, dass der Weg von A nach Z von jedem besuchten Gitterpunkt aus nur nach rechts oder oben verlaufen darf, nicht nach links oder unten. |
Ich habe diese Frage in keinem anderen Forum gestellt.
Hallo liebes Forum,
leider habe ich bei dieser Aufgabe keine Ahnung, wie ich das machen könnte. Wenn man sich so ein Gitter betrachtet, dann gibt es doch extrem viele Wege, die genommen werden können. Aber wieviele genau und wie kann man das schnell und präzise herausfinden ohne jeden einzelnen zu betrachten und zu zählen?
Liebe Grüße
Milchschelle =)
|
|
| |
|
Hi
> Wieviele monotone Wege gibt es in einem Gitter mit
> Kantenlängen 7 × 5 zwischen den diagonal
> gegenüberliegenden Eckpunkten A und Z? Monoton bedeutet,
> dass der Weg von A nach Z von jedem besuchten Gitterpunkt
> aus nur nach rechts oder oben verlaufen darf, nicht nach
> links oder unten.
> Ich habe diese Frage in keinem anderen Forum gestellt.
>
> Hallo liebes Forum,
>
> leider habe ich bei dieser Aufgabe keine Ahnung, wie ich
> das machen könnte. Wenn man sich so ein Gitter betrachtet,
> dann gibt es doch extrem viele Wege, die genommen werden
> können. Aber wieviele genau und wie kann man das schnell
> und präzise herausfinden ohne jeden einzelnen zu
> betrachten und zu zählen?
>
Wenn du dir das aufmalst:
[Dateianhang nicht öffentlich]
So siehst du das JEDER Weg aus 7 Entscheidungen nach rechts zu gehen und 5 Entscheidungen nach oben zu gehen besteht.
Also wie viele Möglichkeiten hast du?
(Stichwort: catalanschen Zahlen)
Dateianhänge:
Anhang Nr. 1 (Typ: PNG) [nicht öffentlich]
|
|
|
| |
|
Hey, danke für deine Antwort. Also ich muss gestehen, dass ich noch nie etwas von den Catalan- Zahlen gehört habe, hab aber gleich mal nachgeschaut und habe Folgendes gefunden:
[mm] C_{n} [/mm] = [mm] \bruch{(2n)!}{(n+1)!n!} [/mm] für n [mm] \ge [/mm] 0
und das ergibt die Zahlenfolge: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, … .
Wie mir das jetzt weiterhelfen soll, das weiß ich aber nicht so wirklich.
Kann man hier nicht einfach 5*7 = 35 rechen? Also, dass er 35 Möglichkeiten gibt.
Das ist doch genau wie beim Würfel oder nicht? Wenn man 2 mal würfelt und herausfinden will, wieviel Zahlenkombinationen entstehen, dann rechnet man ja 6*6=36, also 36 Zahlenkombinationen. Und hier wollen wir eigentlich das gleiche herausfinden, nur dass wir hier einmal 5 und einmal 7 haben?
|
|
|
| |
|
> Hey, danke für deine Antwort. Also ich muss gestehen, dass
> ich noch nie etwas von den Catalan- Zahlen gehört habe,
> hab aber gleich mal nachgeschaut und habe Folgendes
> gefunden:
> [mm]C_{n}[/mm] = [mm]\bruch{(2n)!}{(n+1)!n!}[/mm] für n [mm]\ge[/mm] 0
Das war eher für das spätere Nachschlagen gedacht. Die Aufgabe geht auch direkt zu lösen:
Die weihnachtliche Variante von der Aufgabe:
Du hast 5 ununterscheidbare blaue und 7 ununterscheidbare rote Kugeln am Weihnachstbaum hängen.
Wie viele Möglichkeiten gibt blaue und rote Kugeln abzunehmen?
|
|
|
| |
|
:D Ist ja süß, aber passend. Ich liebe Weihnachten, da macht die Aufgabe gleich viel mehr Spaß. Für mich macht diese Aufgabe zu der vorherigen zwar keinen Unterschied, aber ich meld mich nochmal in 15 Minuten, überdenk mir das Ganze nochmal.
|
|
|
| |
|
Kann man das nicht nur mit einem Baumdiagramm machen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:49 Mo 26.11.2012 | | Autor: | fred97 |
> Kann man das nicht nur mit einem Baumdiagramm machen?
Na klar, denn die Kugeln hängen ja am Weihnachstbaum.
FRED
|
|
|
| |
|
Die Frage ist nur, ob man das nicht noch schneller machen kann? Weil das Baumdiagramm wird ja im Endeffekt ganz schön groß und es ist ja das Gleiche wie wenn ich einfach alle Möglichkeiten nachrechne. Gibt es noch einen anderen Weg?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:00 Mo 26.11.2012 | | Autor: | Teufel |
Fred hat sich, denke ich, nur einen Scherz erlaubt. :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:06 Mo 26.11.2012 | | Autor: | fred97 |
> Fred hat sich, denke ich, nur einen Scherz erlaubt. :)
Gut erkannt !
FRED
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:37 Mo 26.11.2012 | | Autor: | wieschoo |
> > Kann man das nicht nur mit einem Baumdiagramm machen?
>
> Na klar, denn die Kugeln hängen ja am Weihnachstbaum.
>
> FRED
>
^^
Es wird Zeit, dass Weihnachten wird.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:59 Mo 26.11.2012 | | Autor: | Teufel |
Hi!
Ich komme so gut damit klar: Ich möchte also rote und blaue Weihnachtskugeln anhängen. Einen "Anhängvorgang" könnte man ja also RBBRRBRRRBBR beschreiben, wobei R für rot und B für Blau steht (und BRRR weil es im Winter normalerweise kalt ist :)).
Einen Dekorierplan kann man immer eindeutig so darstellen. Nun musst du nur noch die Wörter Zählen, die man aus 5 Bs und 7 Rs bilden kann.
|
|
|
| |
|
aber das ist doch auch nicht anderes als alle möglichkeiten durchzuzählen... gibt es denn da keine schnellere variante?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:52 Mo 26.11.2012 | | Autor: | wieschoo |
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: PNG) [nicht öffentlich]
|
|
|
| |
|
Ich habe absolut keine Ahnung was mir das bringen soll ... Ich verstehe schon, was du da gemacht hast. Im Endeffekt weiß ich jetzt, dass es immer 12 Schritte sind vom Punkt A bis zum Punkt Z.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:17 Mo 26.11.2012 | | Autor: | wieschoo |
Man erkannt erkennt das Pascalsche Dreieck...
|
|
|
| |
|
ich habe jetzt 1584 raus, ist das ein realistischer wert? ich denke das ist viel zu viel oder?
|
|
|
| |
|
Hallo Milchschelle,
natürlich sind es immer 12 Schritte. Davon gehen 5 nach oben und 7 nach rechts (oder war es umgekehrt? Ist für die Rechnung egal).
Also gibt es genau [mm] \vektor{12\\5}=\vektor{12\\7} [/mm] Möglichkeiten. Das ist die Zahl der möglichen Positionen von 5 (oder 7) aus 12.
Und [mm] \vektor{12\\5}=792
[/mm]
> ich habe jetzt 1584 raus, ist das ein realistischer wert?
> ich denke das ist viel zu viel oder?
Dein Gefühl ist richtig.
Grüße
reverend
|
|
|
| |
|
ich habe das beides addiert ^^.
aber ich weiß jetzt, dass es 210 möglichkeiten gibt
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:52 Mo 26.11.2012 | | Autor: | reverend |
Hallo nochmal,
> ich habe das beides addiert ^^.
>
> aber ich weiß jetzt, dass es 210 möglichkeiten gibt
![[haee]](/images/smileys/haee.gif "[haee]") Woher?
Das ist falsch.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:45 Mo 26.11.2012 | | Autor: | Sax |
Hi,
nein, das ist richtig, wenn man bedenkt, dass es tatsächlich nur 6 Schritte nach rechts und 4 nach oben sind.
Gruß Sax.
|
|
|
| |
|
also ich hab es mit dem pascal'schen dreieck gemacht. einfach das ganze aufgeschrieben bis n= 10 und dann so umgedreht, dass es wie ein gitter aussieht und die zahlen so weit aufgeschrieben, dass auf der waagerechten 7 und auf der senkrechten 5 zahlen stehen.
dann steht ganz oben rechts 210. jedoch muss ich gestehen, dass ich die zusammenhänge nicht verstehe , also wieso man hierfür überhaupt das pascalsche dreieck verwenden kann...? ich meine die zahlen stehen doch für [mm] (a+b)^{n} [/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:11 Di 27.11.2012 | | Autor: | reverend |
Hallo nochmal,
> also ich hab es mit dem pascal'schen dreieck gemacht.
> einfach das ganze aufgeschrieben bis n= 10 und dann so
> umgedreht, dass es wie ein gitter aussieht und die zahlen
> so weit aufgeschrieben, dass auf der waagerechten 7 und auf
> der senkrechten 5 zahlen stehen.
Wenn man in (0;0) losläuft, müssen es waagerecht 8 und senkrecht 6 Zahlen sein. Nach (1;1) gibt es doch 2 mögliche Wege, nicht einen. Das nur zur Kontrolle.
> dann steht ganz oben rechts 210. jedoch muss ich gestehen,
> dass ich die zusammenhänge nicht verstehe , also wieso man
> hierfür überhaupt das pascalsche dreieck verwenden
> kann...? ich meine die zahlen stehen doch für [mm](a+b)^{n}[/mm]
Oh, sie stehen für vieles, darunter auch für die Binomialkoeffizienten. So werden sie ja auch normalerweise bezeichnet. Aber z.B. stehen sie auch dafür, wieviele Mannschaften aus k Spielern gebildet werden können, wenn n Sportler zur Verfügung stehen: [mm] \vektor{n\\k}.
[/mm]
Du begegnest den Bin.koeff. in der Kombinatorik andauernd, und es ist nicht immer offensichtlich, warum sie da so angewandt werden. Das braucht manchmal ein bisschen Denkarbeit und/oder eine gute Deutung.
Wie viele Möglichkeiten gibt es, die Zahl 10 in drei Summanden aufzuteilen, wenn die Reihenfolge der Summanden beachtet wird (also 2+3+5 eine andere Lösung ist als 3+5+2)? Antwort: [mm] \vektor{12\\2}. [/mm] Das gilt aber nur, wenn auch 0 ein erlaubter Summand ist. Wenn jeder Summand mindestens 1 sein muss, dann gibt es nur [mm] \vektor{9\\2} [/mm] Möglichkeiten.
Das ist mit der Betrachtung von [mm] (a+b)^n [/mm] aber nicht mehr zu erklären, auch nicht mit dem Pascalschen Dreieck.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:03 Di 27.11.2012 | | Autor: | reverend |
Hallo Sax,
> nein, das ist richtig, wenn man bedenkt, dass es
> tatsächlich nur 6 Schritte nach rechts und 4 nach oben
> sind.
Dass [mm] \vektor{10\\4}=\vektor{10\\6}=210 [/mm] ist, bestreite ich nicht.
Aber die Aufgabe lautete so:
> Wieviele monotone Wege gibt es in einem Gitter mit Kantenlängen
> 7 × 5 zwischen den diagonal gegenüberliegenden Eckpunkten A und Z?
> Monoton bedeutet, dass der Weg von A nach Z von jedem besuchten
> Gitterpunkt aus nur nach rechts oder oben verlaufen darf, nicht
> nach links oder unten.
Wo steht da bitte, dass man nicht im Ursprung losläuft (also in (0;0)), sondern in (1;1)?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:13 Di 27.11.2012 | | Autor: | Sax |
Hi,
ich hab' Wieschos Skizze aus seinem ersten Beitrag genommen und angefangen zu zählen, was leider falsch war.
Gruß Sax.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:57 Di 27.11.2012 | | Autor: | wieschoo |
Ja da fehlt leider jeweils eine Kante.
Das war dann eben nicht maßstabsgetreu... ![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]")
|
|
|
|
