Bälle in Felder füllen

28.11.2021, 12:38	elips53	Auf diesen Beitrag antworten »
Bälle in Felder füllen Hallo zusammen Ich habe sechs Linien mit 12 Spalten. Ich habe 6x12 Bälle die mit a, b, c, d, e, f, g, h, i, j, k und l bezeichnet sind. Also 6 a Bälle, 6 b Bälle, 6 g Bälle etc. Frage eins: Nun muss ich die Bälle in die Felder füllen. In jeder Linie und in jeder Spalte darf nur einmal ein Ball mit derselben Bezeichnung vorkommen. Wie viele Kombinationen sind möglich? Frage zwei; Ich habe sechs Linien mit 12 Spalten. Die Spalten 1-6 sind blau und die Spalten 7-12 sind rot. Ich habe 6x6 blaue Bälle die mit a, b, c, d, e, f bezeichnet sind und 6x6 rote Bälle, mit der Bezeichnung g, h, i, j, k, l. Also 6 blaue a Bälle, 6 blaue b Bälle, 6 rote g Bälle etc. Ich darf die blauen Bälle nur in die blauen Felder füllen und die roten Bälle nur in die roten Felder. In jeder Linie und in jeder Spalte darf nur einmal ein Ball mit derselben Bezeichnung vorkommen. Die ersten beiden Linien sind vorgegeben (zum Beispiel): 1. Linie blaue Felder: 1. Feld a, 2. Feld b, 3. Feld c, 4. Feld d, 5. Feld e, 6. Feld f, 2. Linie blaue Felder: 1. Feld f, 2. Feld e, 3. Feld d, 4. Feld c, 5. Feld b, 6. Feld a, 1. Linie rote Felder: 7. Feld g, 8. Feld h, 9. Feld i, 10. Feld j, 11. Feld k, 12. Feld l. 2. Linie rote Felder: 7. Feld l, 8. Feld k, 9. Feld j, 10. Feld i, 11. Feld h, 12. Feld g. Wie viele Kombinationen sind hier möglich?
28.11.2021, 14:55	HAL 9000	Auf diesen Beitrag antworten »
Ich hab mir nur Frage 1 angeschaut: Für nur zwei statt sechs Linien ist das Problem bekannt als das der fixpunktfreien Permutationen, und bereits das ist ziemlich haarig mit komplizierter Endformel. Man kann natürlich versuchen, die Methode von zwei Linien (Siebformel mit 12 Mengen) auch auf das Problem mit sechs Linien anzuwenden - wird aber eine ziemlich längliche Angelegenheit: Diesmal wären es dann $\begin{eqnarray} 12\cdot \binom{6}{2} = 180 \end{eqnarray}$ Mengen für die Siebformel, wobei es sehr verschiedene Arten von Mengendurchschnitten gibt, deren Klassifizierung und Abzählung nach einer Unmasse Arbeit klingt - ich würde mir damit nicht den ersten Advent versauen wollen. Ein vollständiges Bruteforce über alle $\begin{eqnarray} 13!^5\approx 9.4\cdot 10^{48} \end{eqnarray}$ ist ein aussichtsloses Unterfangen, aber man könnte sich zumindest mit Monte Carlo eine Schätzung für den relative Anteil derjenigen Anordnungen verschaffen, die den Bedingungen der Aufgabe genügen. -------------------------------------------------------------------------------------------------- Der Versuch einer groben Schätzung: Pro Spalte ist die Wahrscheinlichkeit $\begin{eqnarray} q=\frac{12!}{6!\cdot 12^6} \approx 0.2228 \end{eqnarray}$ , keine Bälle mehrfach in der Spalte zu haben. Als Schätzung für die Gesamtwahrscheinlichkeit nimmt man dann $\begin{eqnarray} q^{12}\approx 1.5\cdot 10^{-8} \end{eqnarray}$ , dieser Rechnung basiert auf der (sicher falschen) Annahme, dass die Spaltenbesetzungen voneinander unabhängig sind. Bei zwei Linien klappt die ähnliche Näherung $\begin{eqnarray} \left(1-\frac{1}{12}\right)^{12}\approx \frac{1}{e} \end{eqnarray}$ noch ganz gut, also warum nicht hier probieren. Ich hab keine Ahnung, wie sich der Fehler durch die falsche Annahme auf das Endergebnis quantitativ auswirkt - ich kann nicht mal sagen, ob das wahre Ergebnis größer oder kleiner als diese Schätzung ist.
29.11.2021, 16:54	elips53	Auf diesen Beitrag antworten »
Hallo HAL Vielen Dank für Deine Antwort. Ich dachte da gibt es eine einfache Lösungs-Formel. Es scheint also doch eine schwierigere Sache zu sein. Ich hoffe, da kommt noch eine einfacher Lösung. Liebe Grüße Emil

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »