(Twitter)
0
Ich wage mal einen Versuch, unter der Voraussetzung, dass ich das richtig verstanden habe.
Dein Problem ist in der gestellten Formulierung aus meiner Sicht nicht lösbar.
Du schreibst: "Dabei darf die Reihenfolge der A1 jedoch nicht verändert werden, nur die Position". Wenn die Reihenfolge der A1 nicht verändert werden kann, dann kann es keine 252 verschiedenen Anordnungen geben, sondern nur eine. Das ist erstmal ein Widerspruch.
Möglichkeit 1: Du möchtest alle Möglichkeiten haben - dann bekomme ich 184756 Möglichkeiten heraus. Das berechnet sich dann genauso, wie Du auf die 252 kommst. Vielleicht kannst Du mal mitteilen, wie Du auf 252 kommst - dann weiß ich, ob ich Dich wirklich richtig verstanden habe.
Möglichkeit 2: Du wählst ein festes A1 aus. Wenn Du dann wissen möchtest, wie viele Möglichkeiten es gibt, dann gibt es nicht eine feste Zahl als Ergebnis, sondern das Ergebnis hängt davon ab, wie A1 aussieht. Auch hier empfehle ich Dir, einmal aufzuschreiben, welche Möglichkeiten es gibt (Du kannst ja mit weniger Elementen arbeiten um das nachzuvollziehen)
Dein Problem ist in der gestellten Formulierung aus meiner Sicht nicht lösbar.
Du schreibst: "Dabei darf die Reihenfolge der A1 jedoch nicht verändert werden, nur die Position". Wenn die Reihenfolge der A1 nicht verändert werden kann, dann kann es keine 252 verschiedenen Anordnungen geben, sondern nur eine. Das ist erstmal ein Widerspruch.
Möglichkeit 1: Du möchtest alle Möglichkeiten haben - dann bekomme ich 184756 Möglichkeiten heraus. Das berechnet sich dann genauso, wie Du auf die 252 kommst. Vielleicht kannst Du mal mitteilen, wie Du auf 252 kommst - dann weiß ich, ob ich Dich wirklich richtig verstanden habe.
Möglichkeit 2: Du wählst ein festes A1 aus. Wenn Du dann wissen möchtest, wie viele Möglichkeiten es gibt, dann gibt es nicht eine feste Zahl als Ergebnis, sondern das Ergebnis hängt davon ab, wie A1 aussieht. Auch hier empfehle ich Dir, einmal aufzuschreiben, welche Möglichkeiten es gibt (Du kannst ja mit weniger Elementen arbeiten um das nachzuvollziehen)
Diese Antwort melden
Link
geantwortet
joergwausw
Punkte: 2.37K
Punkte: 2.37K
Vielen Dank für die schnelle Antwort.
Ich habe mich tatsächlich widersprüchlich ausgedrückt. Wenn man sich den ganzen Satz, den du zitiert hast, wegdenkt, ist es meiner Meinung nach richtig. Möglichkeit 1 ist das, was ich gesucht habe. Könntest du mir vielleicht genauer erläutern, wie du auf die 184756 kommst?
Auf die 252 komme ich so: Ich habe 5 identische Elemente einer Art und 5 identische Elemente einer anderen Art. 252 ist die Anzahl der möglichen Anordnungen, wenn man alle Elemente benutzen muss. Das berechne ich mit n!/(k1!*k2!), also 10!/(5!*5!) = 252. Wenn wir es dann kombinieren, haben wir also dann insgesamt 20 Elemente und davon sind zwei mal 10 identisch. Wenn ich es, wie du sagst, genauso berechne wie die 252, komme ich zwar auch auf 184756, jedoch setzt das ja voraus, dass alle Möglichkeiten mit 20 Elementen, von denen 2 mal 10 identisch sind, meine Voraussetzungen erfüllen und das wissen wir ja nicht.
─ karinxy 21.10.2021 um 18:17
Ich habe mich tatsächlich widersprüchlich ausgedrückt. Wenn man sich den ganzen Satz, den du zitiert hast, wegdenkt, ist es meiner Meinung nach richtig. Möglichkeit 1 ist das, was ich gesucht habe. Könntest du mir vielleicht genauer erläutern, wie du auf die 184756 kommst?
Auf die 252 komme ich so: Ich habe 5 identische Elemente einer Art und 5 identische Elemente einer anderen Art. 252 ist die Anzahl der möglichen Anordnungen, wenn man alle Elemente benutzen muss. Das berechne ich mit n!/(k1!*k2!), also 10!/(5!*5!) = 252. Wenn wir es dann kombinieren, haben wir also dann insgesamt 20 Elemente und davon sind zwei mal 10 identisch. Wenn ich es, wie du sagst, genauso berechne wie die 252, komme ich zwar auch auf 184756, jedoch setzt das ja voraus, dass alle Möglichkeiten mit 20 Elementen, von denen 2 mal 10 identisch sind, meine Voraussetzungen erfüllen und das wissen wir ja nicht.
─ karinxy 21.10.2021 um 18:17
Meine Lösung setzt voraus, dass in beiden Mengen A1 und A2 jeweils das gleiche drin ist.
-> in diesem Fall bekommst Du mit der Formel alle Möglichkeiten heraus, wenn Alle Möglichkeiten von A1 mit allen Möglichkeiten von A2 kombiniert werden. Denn dann ist es egal, ob A2 am Stück bleibt oder nicht, denn es werden alle Möglichkeiten genau einmal gezhält. Da kommen also sämtliche Kombinationen für A2 an allen Stellen vor.
-> Wenn in A1 und in A2 jeweils komplett unterschiedliche Elemente drin sind, dann gilt Deine verworfene Lösung von oben mit 11*252^2, ─ joergwausw 21.10.2021 um 18:46
-> in diesem Fall bekommst Du mit der Formel alle Möglichkeiten heraus, wenn Alle Möglichkeiten von A1 mit allen Möglichkeiten von A2 kombiniert werden. Denn dann ist es egal, ob A2 am Stück bleibt oder nicht, denn es werden alle Möglichkeiten genau einmal gezhält. Da kommen also sämtliche Kombinationen für A2 an allen Stellen vor.
-> Wenn in A1 und in A2 jeweils komplett unterschiedliche Elemente drin sind, dann gilt Deine verworfene Lösung von oben mit 11*252^2, ─ joergwausw 21.10.2021 um 18:46
Da A2 immer zusammen ist, heißt das ja, dass es in jeder Kombination 10 aufeinanderfolgende Elemente gibt unter denen sich genau fünf identische Elemente einer Art und 5 identische Elemente einer anderen Art befinden. Mit meiner Frage wollte ich herausfinden, ob die Anzahl der Kombinationen, bei denen genau das gilt (also dass es in jeder Kombination 10 aufeinanderfolgende Elemente gibt unter denen sich genau fünf identische Elemente einer Art und 5 identische Elemente einer anderen Art befinden) sich von der Anzahl der möglichen Kombinationen bei 20 Elementen und 2 mal 10 identischen Elementen unterscheidet. Also das wäre dann quasi der Beweis dafür, dass es in jeder möglichen Kombination bei 20 Elementen mit 2 mal 10 identischen Elementen 10 aufeinanderfolgende Elemente gibt, die aus 5 identischen Elemente einer Art und 5 der anderen Art bestehen.
Wenn ich jetzt jedoch sage: Die Anzahl der möglichen Kombinationen ist 20!/(10!*10!) und die Anzahl der Kombinationen, die die Voraussetzungen erfüllen, ist das gleiche, weil alle Kombinationen für A2 an allen Stellen vorkommen.
Dann ist das ja kein vollständiger Beweis.
Kann man diesen Satz "Denn dann ist es egal, ob A2 am Stück bleibt oder nicht, denn es werden alle Möglichkeiten genau einmal gezählt" mathematisch beweisen?
─ karinxy 21.10.2021 um 19:30
Wenn ich jetzt jedoch sage: Die Anzahl der möglichen Kombinationen ist 20!/(10!*10!) und die Anzahl der Kombinationen, die die Voraussetzungen erfüllen, ist das gleiche, weil alle Kombinationen für A2 an allen Stellen vorkommen.
Dann ist das ja kein vollständiger Beweis.
Kann man diesen Satz "Denn dann ist es egal, ob A2 am Stück bleibt oder nicht, denn es werden alle Möglichkeiten genau einmal gezählt" mathematisch beweisen?
─ karinxy 21.10.2021 um 19:30
Ok, das wäre dann Möglichkeit 3....
Du möchtest also alle die Ergebnisse raussortieren, die keine Teilsequenz der Größe haben, in der sich genau 5+5 Elemente befinden.
Wie ich schon schrieb - einfach dürfte das nicht sein.
Ich hatte mir ein Beispiel aufgeschrieben: Wenn A2 die Sequenz (AAAAABBBBB) ist, dann gibt es mehr gültige Elemente als wenn die Sequenz (ABABABABAB) vorliegt. Also diese gesuchte Anzahl als Multiplikation darzustellen, wird nicht einfach.
Vermutlich klappt es durch genaues Aufsummieren (also zu Fuß).
Mir war beim der Internet-Recherche das "Manhattan-Problem" über den Weg gelaufen.
Im Prinzip hast Du mit deinem Problem einen solchen 10x10-Block-Stadtplan, in dem ein 5x5-Block durchlaufen werden muss. Gehe alle möglichen Positionen des 5x5-Blocks auf dem 10x10-Block durch, ermittele, wie viele Möglichkeiten es jeweils gibt um an den Anfang und an das Ende zu kommen, und zähle anschließend alles zusammen...
Das wäre jetzt mein Ansatz. Guck mal, ob Du damit etwas anfangen kannst.
Ob sich dann daraus hinterher eine einfachere Formel ergeben kann, müsste dann erforscht werden - oder vielleicht hat es auch schon jemand gemacht...?
Ich hoffe, das hilft Dir weiter. Lass mich wissen, was Du herausfindest. ─ joergwausw 21.10.2021 um 20:01
Du möchtest also alle die Ergebnisse raussortieren, die keine Teilsequenz der Größe haben, in der sich genau 5+5 Elemente befinden.
Wie ich schon schrieb - einfach dürfte das nicht sein.
Ich hatte mir ein Beispiel aufgeschrieben: Wenn A2 die Sequenz (AAAAABBBBB) ist, dann gibt es mehr gültige Elemente als wenn die Sequenz (ABABABABAB) vorliegt. Also diese gesuchte Anzahl als Multiplikation darzustellen, wird nicht einfach.
Vermutlich klappt es durch genaues Aufsummieren (also zu Fuß).
Mir war beim der Internet-Recherche das "Manhattan-Problem" über den Weg gelaufen.
Im Prinzip hast Du mit deinem Problem einen solchen 10x10-Block-Stadtplan, in dem ein 5x5-Block durchlaufen werden muss. Gehe alle möglichen Positionen des 5x5-Blocks auf dem 10x10-Block durch, ermittele, wie viele Möglichkeiten es jeweils gibt um an den Anfang und an das Ende zu kommen, und zähle anschließend alles zusammen...
Das wäre jetzt mein Ansatz. Guck mal, ob Du damit etwas anfangen kannst.
Ob sich dann daraus hinterher eine einfachere Formel ergeben kann, müsste dann erforscht werden - oder vielleicht hat es auch schon jemand gemacht...?
Ich hoffe, das hilft Dir weiter. Lass mich wissen, was Du herausfindest. ─ joergwausw 21.10.2021 um 20:01
Ok, danke. Ich schaue es mir auf jeden Fall mal an.
─
karinxy
21.10.2021 um 20:04
Guten Tag, mir ist ein Zusammenhang aufgefallen, bei dem ich vermute, dass er mir bei der Aufgabe weiterhilft:
Wenn wir insgesamt 20 Elemente hätten und davon aber 4 mal 5 Elemente identisch sind, ist die Anzahl der möglichen Anordnungen ja 20!/((5!)^4). Wenn man das nun zweimal durch die Anzahl der Möglichkeiten dividiert, die es bei 10 Elementen gibt, von denen 2 mal 5 Elemente identisch sind, ist das Ergebnis 20!/((5!)^4) / ((10!/(5!*5!)))^2 = 184756. Das ist ja genau die Anzahl der Möglichkeiten bei 20 Elementen, von denen 2 mal 10 identisch sind.
Hast du eine Idee, wie das alles zusammenhängen könnte? ─ karinxy 24.10.2021 um 12:23
Wenn wir insgesamt 20 Elemente hätten und davon aber 4 mal 5 Elemente identisch sind, ist die Anzahl der möglichen Anordnungen ja 20!/((5!)^4). Wenn man das nun zweimal durch die Anzahl der Möglichkeiten dividiert, die es bei 10 Elementen gibt, von denen 2 mal 5 Elemente identisch sind, ist das Ergebnis 20!/((5!)^4) / ((10!/(5!*5!)))^2 = 184756. Das ist ja genau die Anzahl der Möglichkeiten bei 20 Elementen, von denen 2 mal 10 identisch sind.
Hast du eine Idee, wie das alles zusammenhängen könnte? ─ karinxy 24.10.2021 um 12:23
2 Dinge:
- mir ist zwischendurch mal aufgefallen, dass das mit der Stadtplan-Idee auch noch den Haken hat - die doppelten werden auch nicht gefunden...
- bei dem ersten Satz kann ich nicht folgen.
1) Wenn Du 20 Elemente hast mit 10+10 verschiedenen Elementen, dann kann es nicht 4 5er-Gruppen Stück geben, die alle aus den gleichen Elementen bestehen (wegen der ungeraden Anzahl). Oder ist das jetzt eine andere Grund-Anordnung?
2) Wieso hoch 4?
Die Idee hinter der 252 ist eigentlich diese (aber vielleicht ist auch Deine Idee gültig - das habe ich aber bisher nicht nachvollziehen können, und habe auch nicht die Zeit, da jetzt hinterherzuforschen):
Du hast 10 Stellen, davon 5 mal eine 1 und 5 mal eine 0.
Wenn Du nun 5 von den 10 Stellen mit Einsen füllst, dann wählst Du jedesmal 5 Stellen aus. Das ist eine 5-elementige Teilmenge von einer 10-elementigen Menge. Die mögliche Anzahl ist $\binom{10}{5}=252$. Der wird ja berechnet als $\frac{n!}{(n-k)!\cdot k!}$. Nur weil $n-k = k$ ist, wird hier zweimal durch $5!$ dividiert.
Ich würde jetzt denken, dass ich bei 20 Elementen nun $\binom{20}{5}$ möglichkeiten habe, die erste Element-Sorte auszuwälen, dann $\binom{15}{5}$ für die zweite unde $\binom{10}{5}$ für die dritte. Die restlichen Ziffern sind dann für die vierte Sorte übrig...
Da kommt dann übrigens das gleiche heraus wie bei Deinem ersten Term (mit der 20!). Vielleicht kannst Du den in Bezug setzen mit meiner Argumentation und dann Gemeinsamkeiten finden?
(Hinweis: ich kenne die Antwort auch nicht, sondern überlege nur ein bisschen mit und hoffe, dass es hilft)
Letztlich hilft Dir dieser Zusammenhang aber auch nicht bei Deiner urprünglichen Fragestellung weiter, wie Du diejenigen da rausfischst, bei denen es keine der gewünschten Teil-Sequenzen gibt. ─ joergwausw 24.10.2021 um 13:57
- mir ist zwischendurch mal aufgefallen, dass das mit der Stadtplan-Idee auch noch den Haken hat - die doppelten werden auch nicht gefunden...
- bei dem ersten Satz kann ich nicht folgen.
1) Wenn Du 20 Elemente hast mit 10+10 verschiedenen Elementen, dann kann es nicht 4 5er-Gruppen Stück geben, die alle aus den gleichen Elementen bestehen (wegen der ungeraden Anzahl). Oder ist das jetzt eine andere Grund-Anordnung?
2) Wieso hoch 4?
Die Idee hinter der 252 ist eigentlich diese (aber vielleicht ist auch Deine Idee gültig - das habe ich aber bisher nicht nachvollziehen können, und habe auch nicht die Zeit, da jetzt hinterherzuforschen):
Du hast 10 Stellen, davon 5 mal eine 1 und 5 mal eine 0.
Wenn Du nun 5 von den 10 Stellen mit Einsen füllst, dann wählst Du jedesmal 5 Stellen aus. Das ist eine 5-elementige Teilmenge von einer 10-elementigen Menge. Die mögliche Anzahl ist $\binom{10}{5}=252$. Der wird ja berechnet als $\frac{n!}{(n-k)!\cdot k!}$. Nur weil $n-k = k$ ist, wird hier zweimal durch $5!$ dividiert.
Ich würde jetzt denken, dass ich bei 20 Elementen nun $\binom{20}{5}$ möglichkeiten habe, die erste Element-Sorte auszuwälen, dann $\binom{15}{5}$ für die zweite unde $\binom{10}{5}$ für die dritte. Die restlichen Ziffern sind dann für die vierte Sorte übrig...
Da kommt dann übrigens das gleiche heraus wie bei Deinem ersten Term (mit der 20!). Vielleicht kannst Du den in Bezug setzen mit meiner Argumentation und dann Gemeinsamkeiten finden?
(Hinweis: ich kenne die Antwort auch nicht, sondern überlege nur ein bisschen mit und hoffe, dass es hilft)
Letztlich hilft Dir dieser Zusammenhang aber auch nicht bei Deiner urprünglichen Fragestellung weiter, wie Du diejenigen da rausfischst, bei denen es keine der gewünschten Teil-Sequenzen gibt. ─ joergwausw 24.10.2021 um 13:57
1) Ja, es ist eine neue Grundanordnung.
2) Man berechnet die Anzahl der Möglichkeiten bei n Elementen, von denen k Elemente identisch sind mit n!/k!. Wenn mehrere identisch sind mit n!/(k1!*k2!....). Also bei 20 Elementen, von denen immer 5 identisch sind, ist die Anzahl der Möglichkeiten 20!/(5!*5!*5!*5!) = 20!/((5!)^4). Habe ich da etwas falsch verstanden?
Vielleicht brauche ich einen anderen Ansatz.
─ karinxy 24.10.2021 um 14:26
2) Man berechnet die Anzahl der Möglichkeiten bei n Elementen, von denen k Elemente identisch sind mit n!/k!. Wenn mehrere identisch sind mit n!/(k1!*k2!....). Also bei 20 Elementen, von denen immer 5 identisch sind, ist die Anzahl der Möglichkeiten 20!/(5!*5!*5!*5!) = 20!/((5!)^4). Habe ich da etwas falsch verstanden?
Vielleicht brauche ich einen anderen Ansatz.
─ karinxy 24.10.2021 um 14:26
Das sieht ganz richtig aus - ich habe wohl zu kompliziert gedacht.
Aber wie das bei dem Original-Problem weiterhilft, sehe ich noch nicht... :-( ─ joergwausw 24.10.2021 um 15:54
Aber wie das bei dem Original-Problem weiterhilft, sehe ich noch nicht... :-( ─ joergwausw 24.10.2021 um 15:54