Wieviel Kombinationen

Neue Frage »

brunor Auf diesen Beitrag antworten »
Wieviel Kombinationen
Meine Frage:
Nachgefragt

Ich stricke mir im siebten Anlauf nun doch eine
bunte Kuscheldecke.

Die Decke fügt sich aus 7 Quadraten in der Breite
und 14 Quadraten in der Höhe zusammen und wird
mit 49 verschiedenen Farben gestrickt, d.h., jede
Farbe oder Farbkombination kommt 2x unter den
98 Quadraten vor. Nun interessiert mich, wieviel
Kombinationsmöglichkeiten ergeben sich daraus?

Um dies herauszufinden suche ich die anzuwendende
Formel, finde sie aber nicht. Vielleicht kannst du
mir weiterhelfen!

Meine Ideen:
Ich erinnere, dass es zu dieser Problemstellung eine Formel gibt, ich habe sie vergessen.
Elvis Auf diesen Beitrag antworten »

Mit 98 Farben gäbe es 98! (sprich: achtundneunzig fakultät) =1*2*3*...*98 Möglichkeiten. Je 2 gleichfarbige Quadrate kann man bei 49 Farben vertauschen, ohne dass die Kuscheldecke sich verändert. Spielt es eine Rolle, dass die Decke genau so aussieht wie die um 180° gedrehte Decke (halbiert das die Anzahl der Möglichkeiten)?
 
 
Dopap Auf diesen Beitrag antworten »

ohne Symmetrien bin ich momentan für

BrunoRogalla Auf diesen Beitrag antworten »

Die Decke besteht aus 98 farbigen Quadraten, jeweil 2 Quadrate sind gleichfarbig, die Anordnung der Quadrate
soll keinen Regeln folgen sondern vom Zufall bestimmt sein. Daraus ergeben sich aus meinem Verständnis fast
endlose Kombinationsmöglichkeiten. Ich zemater mir das Hirn, wievie sind es?
+
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Elvis
Spielt es eine Rolle, dass die Decke genau so aussieht wie die um 180° gedrehte Decke (halbiert das die Anzahl der Möglichkeiten)?

Nicht ganz, d.h., diese Anzahl ist etwas größer als die Hälfte! Der Grund dafür ist, dass es Muster gibt, die bei Drehung um 180° in sich selbst übergehen ... Stichwort Burnside's Lemma .
BrunoRogalla Auf diesen Beitrag antworten »

Natürlich spielt das keine Rolle!
Dopap Auf diesen Beitrag antworten »

Zitat:
Original von Dopap
ohne Symmetrien bin ich momentan für



oder

d.h.die 98 Felder sind gekennzeichnet wie auf dem Schachbrett. Symmtrische Stellungen werden mitgezählt obwohl sie für das "Spiel" ohne Bedeutung wären .



1.) Für die Farbe #0 im Doppelpack gibt es Kombinationen von Feldnummern = Koordinaten, die per se Teilmengen = ungeordnete Stichproben von 98 Koordinaten sind. Das entspricht umgerechnet der Anzahl 2 weiße Könige auf dem Schachbrett zu platzieren ( 64 über 2)

2.) Für die Farbe#1 im Doppelpack gibt es noch Kombinationen der Positionen. Das entspricht umgerechnet der Anzahl 2 weiße Läufer auf dem restlichen Schachbrett zu platzieren ( 62 über 2)

...

49.) Für die Farbe #48 im Doppelpack gibt es Kombinationen der Position. Das entspricht umgerechnet der Anzahl 2 weiße Türme auf dem Schachbrett zu platzieren ( 2 über 2)

insgesamt also Möglichkeiten.

Zur Vereinfchahung gibt man zu jedem Faktor noch den Faktor 2 hinzu und erhält und gleicht das jeweils im Nenner mit einer 2 aus.

Hinweis: dieses "Schach" kennt 32 x 2 verschiedene weiße Figuren aber keine Bauern!
(König, Läufer, Turm, Springer, Fee, Krieger, Bote, Lord, Knecht, Samurai, Frau Holle, Teufel, Drache, Narr, Jungfrau, Bettler, etc.... ) Augenzwinkern
und somit Möglichkeiten. Ungefähr soviel wie die Zahl der Atome im Universum.
Zu deiner Flickendecke fällt mir aber gar Nichts mehr ein.
Huggy Auf diesen Beitrag antworten »

Zitat:
Original von Dopap
ohne Symmetrien bin ich momentan für


Oder vielleicht doch:

Elvis Auf diesen Beitrag antworten »

Bruno verstehe ich gar nicht und Burnside ist auch nicht leicht zu verstehen. Ich rate mal, dass "Huggys Formel ohne Symmetrie" noch durch 4 dividiert werden muss.
Huggy Auf diesen Beitrag antworten »

Bei einer 2x3-Decke ergibt die Formel



Durch 4 geteilt ergibt das 22.5.

Hm, ja, äh???
Scotty1701D Auf diesen Beitrag antworten »

Zitat:
Original von Huggy
Zitat:
Original von Dopap
ohne Symmetrien bin ich momentan für


Oder vielleicht doch:


Der Index ist um 1 verschoben, für die erste Farbe ist , für die zweite , usw.
Für Farben erhält man
,
also

und entsprechend für die 2x3-Decke

Warum sollte man das noch mal durch 4 teilen verwirrt
Huggy Auf diesen Beitrag antworten »

Zitat:
Original von Scotty1701D
Warum sollte man das noch mal durch 4 teilen verwirrt

Weiß ich auch nicht. Genau deshalb habe ich ein Beispiel gemacht, das ganz offensichtlich zeigt, dass dieses Teilen nicht korrekt sein kann.

Wenn man Konfigurationen separat zählt, die unterschiedlich sind, die aber durch eine Symmetrieoperation ineinander überführt werden können, gibt es keinen Grund durch irgendetwas zu teilen.
Elvis Auf diesen Beitrag antworten »

Ups
Dopap Auf diesen Beitrag antworten »

Das mit der Nummerierung und eventueller Indexänderung und der "letzten" Farbe war mir schon klar, wollte aber das noch offen lassen.

Ja richtig, auch die letzte Farbe erfordert eine 2 im Nenner ( insgesamt 2^49) aber angesichts von 10^139 im "praktischen Sinne" unbedeutend.

statt momentan N= hätte es auch ein getan.

Die Decke liegt immer mit Naht nach oben und Waschhinweis am Fußende Augenzwinkern
Elvis Auf diesen Beitrag antworten »

Wie verträgt sich damit, dass ich auch bei bestem Willen nur die beiden Möglichkeiten und bei einer quadratischen Kuscheldecke mit 2 Farben und 4 Quadraten finden kann und die 4 Möglichkeiten bei einer rechteckigen Kuscheldecke mit 2 Farben und 4 Quadraten ?
Scotty1701D Auf diesen Beitrag antworten »

Zitat:
Original von Elvis
Wie verträgt sich damit, dass ich auch bei bestem Willen nur die beiden Möglichkeiten und bei einer quadratischen Kuscheldecke mit 2 Farben und 4 Quadraten finden kann und die 4 Möglichkeiten bei einer rechteckigen Kuscheldecke mit 2 Farben und 4 Quadraten ?


Weil du die Fälle

bzw.

nicht berücksichtigt hast Augenzwinkern
Kongruente Konfigurationen sollen ja separat gezählt werden.

Will man das nicht, dann glaube ich nicht, dass es eine einfache (evtl. rekursive) Formel gibt. unglücklich
Wie man sieht, spielt dann schließlich auch die Form der Decke eine Rolle.
Dopap Auf diesen Beitrag antworten »

genau deshalb sprach ich von nummerierten Plätzen oder Koordinaten.
Elvis Auf diesen Beitrag antworten »

Das ist nicht sonderlich praxisnah. Eine Kuscheldecke muss man gelegentlich waschen, und wenn sie aus der Waschmaschine kommt, kann man die Fälle nicht unterscheiden. Eine gestrickte Decke hat keine Koordinaten. Augenzwinkern
Huggy Auf diesen Beitrag antworten »

Zitat:
Original von Scotty1701D
Kongruente Konfigurationen sollen ja separat gezählt werden.

Will man das nicht, dann glaube ich nicht, dass es eine einfache (evtl. rekursive) Formel gibt.

Wenn man nur rechteckige Decken betrachtet, die nicht quadratisch sind, sollte das schon möglich sein. Die einzige Symmetrieoperation ist dann die Drehung um 180°. Damit jede Farbe zweimal verwendet werden kann, muss mindestens eine Seite des Rechtecks gerade sein. Die Zahl der Felder des Rechtecks sei . Damit schreibt sich die bisherige Formel:



Wenn man kongruente Konfigurationen nicht separat zählen möchte, braucht man die Zahl der Konfigurationen, die bei einer Drehung um 180° in sich selbst übergehen. Das sind Stück. Man füllt die Hälfte des Rechtecks, wobei man jede Farbe nur einmal verwendet. Die Füllung der anderen Hälfte ergibt sich aus der Drehung.

Die bisher betrachtete Zahl von Konfigurationen abzüglich dieser symmetrischen Konfigurationen ist zu halbieren und dann sind die symmetrischen Konfigurationen hinzuzufügen. Damit ergibt sich die Zahl der von Elvis gesuchten Konfigurationen ( wenn ich mich nicht irre, um es mit Sam Hawkins zu sagen) zu

[email protected] Auf diesen Beitrag antworten »
ichrechnenichtmehr
Und wieviel Kombinationsmöglichkeiten kommen bei
Anwendung dieser Formel dann raus?
Dopap Auf diesen Beitrag antworten »

etwa die Hälfte wie zuvor



In Worten kann ich das nicht ausdrücken unglücklich
Huggy Auf diesen Beitrag antworten »

Ziemlich ungenau! Big Laugh




Dieter30 Auf diesen Beitrag antworten »

Die Zahl lautet etwa 873 Billionen Vigtillionen. Aber nützen tut diese Erkentnis nichts. Man sieht nur immer wieder wie falsch man von vornherein die Sachlage einstuft.

Wohl niemand hätte anfangs gedacht, dass sich bei dieser harmlos wirkenden Aufgabe eine dermaßen hohe Anzahl an Kombinationsmöglichkeiten ergibt, welche die Zahl der Atome im sichtbaren Universum bei weitem übersteigt.
HAL 9000 Auf diesen Beitrag antworten »

Man muss eben so ausreichend viele Stellen angeben, um überhaupt einen Unterschied zu



festzustellen. Augenzwinkern
[email protected] Auf diesen Beitrag antworten »
ichrechnenichtmehr
Eine junge Frau brachte mich in einer FB-Gruppe zu folgender Lösung:

Ich denke mir vor meinem geistigen Auge ein Raster, 7 Quadrate Schmalseite, 7 Quadrate Breite, 14 Quadrate Länge, fülle nun dies Raster mit 98 vorgefertigten Quadraten. Für das erste Quadrat ergeben sich 98 Möglichkeiten,
für das 2. Quadrat 97 Möglichkeiten, ein Feld ist bereits besetzt.
Daraus ergibt sich folgende Rechnung

98 x 97 x 96 x 95 ........x 2 x 1

Und, was sagt ihr dazu??
Dieter30 Auf diesen Beitrag antworten »

Brunor, sogar ich Mathe Laie erkenne, dass dies sofern die Experten recht haben sollten falsch ist. Deine vermeintlich Lösung bedeutet einfach 98!. Hal 9000 gab aber als Lösung für die Aufagabe 98/ 2^50 an
Elvis Auf diesen Beitrag antworten »

Das ist nur der Zähler des ersten Bruchs. Also viel zu hoch geschätzt, ca. 15 Größenordnungen daneben, das reicht für 1000000000000000 Kuscheldecken. Das wäre richtig, wenn alle Farben paarweise verschieden wären.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Dieter30
Hal 9000 gab aber als Lösung für die Aufagabe 98/ 2^50 an

Nein, ich gab nur den Wert der Zahl an. Den tatsächlichen Lösungswert hatte Huggy vorher schon angegeben. Augenzwinkern


Übrigens, die Rechnung von Huggy entspricht dem sehr einfachen Anwendungsfall des Burnside-Lemmas, dass die dort erwähnte Bewegungsgruppe nur aus den zwei Elementen "Identität" und "180°-Drehung" besteht.
Dieter30 Auf diesen Beitrag antworten »

Elvis, dies reicht aber nur für 10^15 Kuscheldecken, sofern diese nicht als Ganzes aufgefasst werden sollen. Ist dies nicht der Fall kann sich brunor mit Potenztürmen und der Pfeilschreibweise vertraut machen.
HAL 9000 Auf diesen Beitrag antworten »

Nochmal zum Thema Burnside-Lemma:

Zitat:
Angenommen, wir betrachten eine quadratische Decke der Maße mit verschiedenen Farben, die jeweils genau viermal auftreten. Wie viele verschiedene Muster gibt es dann, wenn man zwei durch Drehung (aber NICHT durch "Umdrehen" der Decke) ineinander übergehende Muster als gleich ansieht?

Hier enthält die Drehungsgruppe vier Elemente, nämlich Identität 0°, sowie die Drehungen 90°, 180° und 270°.

Welche Anzahlen an invarianten Mustern bei den diversen Drehungen gibt es:

0°: Alle Permutationen.

180°: In einer Deckenhälfte müssen alle Farben je genau zweimal vertreten sein, die andere Hälfte ist durch die 180°-Drehung dann bereits festgelegt. Die Anzahl ist .

90°,270°: In einem quadratischen Deckenviertel muss jede der Farben je genau einmal vertreten sein, die anderen drei Viertel sind durch die Drehung dann festgelegt. Diese Anzahl ist .

Gemäß Burnside ist nun die gesuchte Anzahl gleich

,

so ergibt sich z.B. und .


P.S.: Auch interessant wäre das Originalproblem, wenn man zudem noch das "Umdrehen" der Decke zulässt. smile
BrunoRogalla Auf diesen Beitrag antworten »

Ja, wenn die Experten Recht haben, werd ich das auch als Laie erkennen
Huggy Auf diesen Beitrag antworten »

Das klingt nicht so, als ob dir klar wäre, weshalb



falsch ist.
HAL 9000 Auf diesen Beitrag antworten »

Ich widme mich mal noch dem Problem mit dem "Umdrehen":

Zitat:
Wir betrachten eine Decke mit den Maßen mit ungeradem (!) , wo jede der verschiedenen Farben je genau zweimal vorkommt. Zwei Deckenmuster werden als gleich angesehen, wenn sie durch Drehung der Decke um 180° oder durch Herumdrehen der Decke (egal ob horizontal oder vertikal) ineinander übergehen.

Wieviel verschiedene Deckenmuster gibt es hier?

Zur Anwendung kommt wieder Burnside, diesmal mit einer Bewegungsgruppe bestehende aus vier Elementen. Nun zu den Anzahlen invarianter Muster bei den entsprechenden Bewegungen:

1) Identität: Da sind alle invariant.

2) Drehung 180°: Wie oben gesehen, die "Hälfte" enthält jeder der Farben genau einmal, die andere Hälfte ist dann festgelegt. Ergibt invariante Muster.

3) Umdrehen entlang der -Achse: Genau wie 2), d.h., invariante Muster.

4) Umdrehen entlang der -Achse: Der Fall ist etwas komplizierter.

Zunächst teilen wir die Decke auf in drei Bereiche "oben", "Mitte" und "unten". Offenbar dürfen bei Invarianz sowohl in "oben" als auch "unten" jeweils nur maximal ein Quadrat jeder Farbe vorkommen, und es kommen dieselben Farben oben wie unten vor. D.h., in der Mitte kommen die restlichen Farben vor, jeweils doppelt. Da mit dem Festlegen von "oben" dann auch "unten" festgelegt ist, dürfen wir nur "oben" und "Mitte" frei permutieren; zusätzlich dürfen wir aber auch noch die Farben für "Mitte" auswählen. Nach dieser langen Vorrede kommen wir zur Anzahlformel in diesem Fall:



Summa summarum über Burnside ergibt sich die Gesamtmusterzahl

.

Im Fall vereinfacht sich das zu , das bedeutet etwa und .


P.S.: Wem es Spaß macht, der kann ja mal alle Muster aufschreiben, angefangen von

123
123

123
132

...
[email protected] Auf diesen Beitrag antworten »
ichrechnenichtmehr
Wie soll ich s verstehen, wenn es mir niemand erklärt??
Dieter30 Auf diesen Beitrag antworten »

Sei getrost brunor, um diese Sachverhalte zu verstehen braucht man mindestens ein Mathematikstudium. Mich irritiert auch ein wenig, was diese Zahlentrupp bei HAL 9000 da unten soll. Zumindest hat´s was von militärischer Moral. Buschmann

123

123

...
Dopap Auf diesen Beitrag antworten »

jeder Block ist eine Decke von 6 kleinen Quadraten im Format 2x3.Es werden die Farben 1, 2 und 3 verwendet. Jede Farbe wird 2 mal benutzt.

1. Decke
123
123

2. Decke
123
132
....

27. Decke
Huggy Auf diesen Beitrag antworten »
RE: ichrechnenichtmehr
Zitat:
Original von [email protected]
Wie soll ich s verstehen, wenn es mir niemand erklärt??

Mach es dir mal an einer Decke klar, die aus nur 4 Quadraten besteht. Wenn man sie mit 4 verschiedenen Farben färbt, dann ist die Überlegung richtig, für das erste Quadrat gibt es 4 Möglichkeiten, für das 2 Quadrat noch 3, für das dritte Quadrat noch 2 und für das letze Quadrat eine. Die Zahl der Konfigurationen ist also



Wenn man aber nur 2 Farben verwendet, die jede doppelt vorkommt, gibt es nur 6 Möglicheiten. Die kannst du leicht per Hand aufmalen. Du wirst nicht mehr als 6 Möglichkeiten finden. Nimm mal an, eine der Farben sei rot. Jeden tun wir mal so, als könne man die beiden Rots unterscheiden. Nennen wir sie und . Dann könnte man z. B. Quadrat 1 mit färben und Quadrat 3 mit . Man könnte es aber auch genau umgekehrt machen, Quadrat 1 mit färben und Quadrat 3 mit . Das wären 2 Möglichkeiten, aber nur, wenn man und untercheiden könnte, das also eigentlich verschiedene Farben wären. Wenn das aber die gleiche Farbe ist, hat man eben auf Quadrat 1 rot und auf Quadrat 3 rot. Das ist nur eine Möglichkeit.

Man muss also die vorher ausgerechneten 24 Möglichkeiten wegen der beiden gleichen Rots durch 2 teilen. Ebenso muss für die beiden gleichen anderen Farben durch 2 teilen. Die Zahl der Konfigurationen ist also jetzt



in Übereinstimmung mit dem, was man durch händisches Aufmalen gefunden hat. Hat man nun Quadrate mit je doppelt vorkommenden Farben, so lautet die Formel

Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »