Forum:  Kombinatorik & Graphentheorie
Thema: Vierergruppen auf Dreiergruppen aufteilen
Themen-Übersicht
DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2504
Aus:
Themenstart: 2020-09-30 17:48

$12n$ Elemente werden auf $3n$ Vierergruppen aufgeteilt.

Anschließend werden sie auf $4n$ Dreiergruppen derart aufgeteilt, dass Elemente der gleichen Vierergruppe immer in unterschiedlichen Dreiergruppen landen.

Die Frage ist, auf wie viele verschiedene Arten das Zuteilen der Dreiergruppen möglich ist.

Für $n=1$ kommt man durch kurzes Nachdenken auf $4! \cdot 4! = 576$.
Schon für $n=2$ wird es für mich hingegen schwierig.

Hat jemand einen vielversprechenden Ansatz?


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6400
Aus: Milchstraße
Beitrag No.1, eingetragen 2020-09-30 18:59

Hallo DerEinfaeltige,

ich verstehe schon nicht, wie du auf die 576 kommst.


DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2504
Aus:
Beitrag No.2, vom Themenstarter, eingetragen 2020-09-30 19:15

Naja, wir haben drei Vierergruppen.
Jeweils ein Element muss in eine der vier Dreiergruppen.

Die Erste kann man beliebig verteilen.
Für die anderen beiden gibt es jeweils 4! Möglichkeiten, sich dazuzugesellen.


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6400
Aus: Milchstraße
Beitrag No.3, eingetragen 2020-09-30 21:55

Bist du sicher, dass die Aufgabe so gemeint ist? Für die Aufteilung der 12 Elemente auf die Vierergruppen gibt es ja auch schon jede Menge Möglichkeiten.


DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2504
Aus:
Beitrag No.4, vom Themenstarter, eingetragen 2020-09-30 22:16

Ja, das ist so gemeint.
Die 576 ist als Musterergebnis gegeben.


Wir wollen wissen, auf wie viele Arten man aus bekannten Vierergruppen Dreiergruppen bilden kann (mit der genannten Einschränkung).


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6400
Aus: Milchstraße
Beitrag No.5, eingetragen 2020-09-30 23:00

Na okay, ich finde dann die Formulierung "12n Elemente werden auf 3n Vierergruppen aufgeteilt. Anschließend ..." etwas missverständlich.

Wäre aber dann nicht die Lösung einfach \((4!)^{3n-1}\)?


DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2504
Aus:
Beitrag No.6, vom Themenstarter, eingetragen 2020-10-01 09:40

Nein, das stimmt nicht.


Wir können vielleicht mal das einfachere Problem betrachten, 3er-Gruppen auf Paare aufzuteilen.

Bei insgesamt 6 Elementen gibt es 2 Dreiergruppen und wir bilden 3 Paare.
Dafür gibt es 6 Möglichkeiten.

{{A1,B1},{A2,B2},{A3,B3}}
{{A1,B1},{A2,B3},{A3,B2}}
{{A1,B2},{A2,B1},{A3,B3}}
{{A1,B2},{A2,B3},{A3,B1}}
{{A1,B3},{A2,B1},{A3,B2}}
{{A1,B3},{A2,B2},{A3,B1}}


Bei insgesamt 12 Elementen gibt es 4 Dreiergruppen und wir bilden insgesamt 6 Paare.

Brav nach Gruppen geordnet:
{{A1,B1},{A2,B2},{A3,B3},{C1,D1},{C2,D2},{C3,D3}}

Mit einem "Austausch":
{{A1,C1},{A2,B2},{A3,B3},{B1,D1},{C2,D2},{C3,D3}}

...


Per Brute Force finde ich hier 3348 Varianten.


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6400
Aus: Milchstraße
Beitrag No.7, eingetragen 2020-10-01 16:49

Das Problem habe ich nun verstanden. Und die 3348 kann ich bestätigen.

Grüße
StrgAltEntf


DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2504
Aus:
Beitrag No.8, vom Themenstarter, eingetragen 2020-10-01 18:51

2020-10-01 16:49 - StrgAltEntf in Beitrag No. 7 schreibt:
Und die 3348 kann ich bestätigen.


Danke, dann habe ich einen weiteren Vergleichswert, falls ich einen vernünftigen Algorithmus zustande bringe. :)


Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 2408
Aus:
Beitrag No.9, eingetragen 2020-10-01 19:14
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Hallo,

ich weiß noch nicht, ob das irgendwie weiterhilft, aber ich fand es ganz hübsch:

Betrachte $4n$ Variablen $D_1,\ldots, D_{4n}$ ($D_i$ soll der $i$-ten Dreiergruppe entsprechen).

Die Anzahl der Möglichkeiten $3n$ Vierergruppen gemäß der Aufgabenstellung auf $4n$ Dreiergruppen zu verteilen ist dann gleich $\frac{(4!)^{3n}} {(4n)!} C$, wobei $C$ der Koeffizient von $D_1^3D_2^3\cdot \ldots \cdot D_{4n}^3$ im Polynom
$$ \left(\sum_{1\leq a<b<c<d\leq 4n} D_aD_bD_cD_d\right)^{3n}$$ ist.

Vielleicht kann man daraus eine Summenformel oder zumindest eine Rekursion herleiten.
\(\endgroup\)

StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6400
Aus: Milchstraße
Beitrag No.10, eingetragen 2020-10-02 21:52

Für n = 2 habe ich jetzt mal zu zählen angefangen. Mein Rechner wird damit noch sehr lange beschäftigt sein. Erinnert mich irgendwie an dies.

Woher stammt denn die Aufgabe?


DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2504
Aus:
Beitrag No.11, vom Themenstarter, eingetragen 2020-10-02 23:03

Euler Project 475 (Music Festival)


Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 2408
Aus:
Beitrag No.12, eingetragen 2020-10-02 23:14
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Ich habe meinen Ansatz jetzt mal mit ein paar Vereinfachungen, die auf der Symmetrie des Polynoms beruhen, implementiert und finde für $n=2$, also die Aufteilung von $6$ Vierergruppen auf $8$ Dreiergruppen genau
$$ 60871300 \cdot \frac{(4!)^{6}}{8!} = 288509091840$$ Möglichkeiten.

Laufzeit sind so ca. 3 Sekunden. Für größere $n$ muss ich noch ein bisschen was anpassen, damit es nicht zu Overflows kommt.

[Die Antwort wurde nach Beitrag No.10 begonnen.]
\(\endgroup\)

StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6400
Aus: Milchstraße
Beitrag No.13, eingetragen 2020-10-02 23:24

2020-10-02 23:14 - Nuramon in Beitrag No. 12 schreibt:
288509091840

Diese Zahl kennen weder OEIS noch Google anscheinend nicht. Muss natürlich nichts heißen.


Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 2408
Aus:
Beitrag No.14, eingetragen 2020-10-02 23:28

Die Zahl passt zu dem Hinweis, der in der Aufgabenstellung gegeben ist.


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6400
Aus: Milchstraße
Beitrag No.15, eingetragen 2020-10-02 23:55

Dann spricht natürlich vieles dafür, dass dein Ergebnis richtig ist. Bin gespannt, ob mein Zählprogramm dasselbe Ergebnis ausspuckt. Falls ja, sollte es nach meinen Hochrechnungen in ca. 30 Std durch sein.


Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 2408
Aus:
Beitrag No.16, eingetragen 2020-10-03 00:36
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Okay, den in ProjectEuler gesuchten Wert (also $n=50$ und Ergebnis modulo 1000000007) kann mein Programm in weniger als 2,5 Minuten berechnen.
Anscheinend war ich damit die 394te Person, die die Aufgabe gelöst hat.

Da es gegen die Regeln von ProjectEuler verstößt, will ich mein Programm hier nicht veröffentlichen. Ich kann aber bei Interesse noch ein paar Tipps oder weitere Kontrollwerte (auch für andere Gruppengrößenkonstellationen) geben.
\(\endgroup\)

DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2504
Aus:
Beitrag No.17, vom Themenstarter, eingetragen 2020-10-04 12:30

Ich habe es jetzt auch lösen können, indem ich sozusagen über die "Besetzungszustände" iterierte.

Von der Anfangsbesetzung (200,0,0,0) mit (erlaubten) Übergängen um jeweils 4 Schritte nach (0,0,0,200).
Das Tupel beschreibt dabei, wie viele Dreiergruppen 0,1,2,3 Mitglieder haben und zu jedem Tupel/Zustand wird die Multiplizität gespeichert/berechnet.

Laufzeit 45s in der Python-Konsole war weit besser als erwartet.


Danke an alle fürs Mitknobeln! :)


Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 2408
Aus:
Beitrag No.18, eingetragen 2020-10-04 15:38
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}}\)
Das klingt ähnlich, wie das, was ich am Ende auch gemacht hatte.

In meiner ersten Lösung (ebenfalls Python), hatte ich gleich den allgemeineren Fall implementiert, in dem man $k$-Gruppen auf $l$-Gruppen verteilt. Nach einem Blick in die anderen Lösungen im Project Euler Forum kam mir meine Laufzeit von ca. 2min 15s etwas hoch vor.
Darum habe ich das gleiche nochmal implementiert und zwar diesmal ausschließlich für den Fall $k=4$ und $l=3$, wie in der Aufgabe (die restliche Logik ist aber gleich geblieben). Ich bin gerade noch sehr stark davon überrascht, aber allein durch das Weglassen von ein paar scheinbar simplen List comprehensions (ersetzt durch explizite Listen der Länge drei), braucht mein Code jetzt für $n=50$ nur noch 7 Sekunden.
\(\endgroup\)



Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=249603=70
Druckdatum: 2020-11-26 01:56