Gruppenbildung (4 aus 20) < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:26 Di 11.04.2006 | | Autor: | Fuechsl |
| Aufgabe 1 | a) Wie viele 4er-Gruppen kann ich aus sagen wir 20 Personen bilden, wobei den Gruppen immer komplett verschiedene Personen zugehören müssen?
Beispiel: Gruppenmitglieder seien 1-20. Gruppen 1-2-3-4 und 2-5-6-7 sind komplett verschieden, 1-2-3-4 und 2-3-5-7 nicht, da 2 und 3 in beiden vorkommen.
|
| Aufgabe 2 | b) Wenn ich die 20 Personen jeweils in fünf 4er-Gruppen aufteilen will, wie viele solche Kombinationen kann ich herstellen, so dass die Bedingung aus a) immer noch erfüllt ist? (Ist das dieselbe Aufgabe wie a? Beweis?)
|
4 aus 20 ohne Wiederholung ist ja klar, 20 tief 4. Allerdings sind dann die Fälle 1-2-3-4 und 2-3-5-6 beide drin; ich weiss nicht, wie ich die geschickt ausschliessen kann. Ich habe mal mit Excel etwas experimentiert, aber meine Lösung von rund 2800 Möglichkeiten scheint mir einfach zu hoch!
Vielen Dank für eure Mithilfe im Voraus!
Mit freundlichem Gruss
Martin Lacher
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:28 Di 11.04.2006 | | Autor: | Karl_Pech |
Hallo Fuechsl,
> a) Wie viele 4er-Gruppen kann ich aus sagen wir 20 Personen
> bilden, wobei den Gruppen immer komplett verschiedene
> Personen zugehören müssen?
>
> Beispiel: Gruppenmitglieder seien 1-20. Gruppen 1-2-3-4 und
> 2-5-6-7 sind komplett verschieden
Aber die 2 kommt doch in beiden Gruppen vor?
Zwar bin ich mir jetzt nicht sicher, aber ich glaube, daß du hier einfach bis [mm]n = 20[/mm] zählst, und dann deine Zahlen in soviele [mm]k\texttt{-Bl"ocke}[/mm] wie möglich unterteilst:
1,2,3,4,|5,6,7,8|,9,10,11,12|,13,14,15,16|,17,18,19,20
Dann zählst du die Anzahl dieser Blöcke, die jetzt zahlenmäßig voneinander komplett verschieden sind. Aber dieses Zählen entspricht doch genau der ganzzahligen Division (nach unten Runden). Damit gibt es [mm]\left\lfloor\frac{n}{k}\right\rfloor[/mm] Möglichkeiten aus einer Menge natürlicher Zahlen [mm]\{1,\dotsc,n\}[/mm] disjunkte [mm]k\texttt{-elementige}[/mm] Teilmengen zu bilden. Ist aber wie gesagt, bloß meine Vermutung.
Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:17 Mi 12.04.2006 | | Autor: | Fuechsl |
Hallo Karl,
Danke vielmals für deine schnelle Antwort. Zu deiner Bemerkung bezüglich der 2: Es geht darum, dass nie eine Person wieder mit einer anderen Person in eine Gruppe kommt, mit der sie bereits mal in einer Gruppe war. Wenn ich also die Gruppe 1-2-3-4 bilde, kann ich danach die Gruppe 2-5-6-7 bilden (weil die noch nie zusammen in einer Gruppe waren) aber nicht die Gruppe 2-3-5-6, weil 2 und 3 bereits zusammen in einer Gruppe waren.
Mein Hauptproblem ist eigentlich b), aber ich weiss nicht recht, ob es sogar identisch mit a) sein könnte...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:36 Di 18.04.2006 | | Autor: | Fuechsl |
Ich bin nicht sicher, ob ich dieses Forum richtig bedient habe, weil ich jetzt seit längerer Zeit keine weiteren Tipps mehr erhalten habe. Gibt es da draussen keine schlauen Kombinatoriker, die etwas Zeit für mich bzw. meine Frage haben?
Vielen Dank im Voraus
Martin
|
|
|
| |
|
Hallo und guten Morgen,
Du fragst also in der (a) nach der maximalen Anzahl von Teilmengen
[mm] G_1,\ldots G_N\subseteq\{1,\ldots , 20\} [/mm] der Größe 4 so,
dass für [mm] 1\leq i
Ein paar Betrachtungen dazu in loser Reihenfolge:
(i) Wenn wir eine solche Familie von Gruppen [mm] G_1\ldots G_N [/mm] betrachten, so
schauen wir uns mal diejenigen an, die die 1 enthalten: Seien diese zB [mm] G_1,\ldots G_n [/mm] mit [mm] n\leq [/mm] N.
Dann sind
[mm] G_1\setminus \{1\},\ldots G_n\setminus\{1\} [/mm] paarweise disjunkte Teilmengen von [mm] \{2,\ldots , 20\}.
[/mm]
(ii) Die Anzahl der 2-elem. Teilmengen von [mm] \{1,\ldots 20\} [/mm] ist [mm] {20\choose 2} [/mm] =190 (oder so).
Jedenfalls stellt eine Familie [mm] G_1,\ldots G_N [/mm] wie oben insbesondere eine Partition der Menge der 2-elem. Teilmengen
von [mm] \{1,\ldots 20\} [/mm] dar, denn keine 2-er-Menge darf in zwei versch. Gruppen vorkommen.
Die Partition muss so sein, dass alle entstehenden Klassen 4-er Mengen bilden.
Dabei muss eine Klasse aus 2 oder 3 Zweiermengen bestehen: 2, wenn die beiden disjunkt sind, und drei sonst...
Auch das hilft mir noch nicht richtig weiter...
Werde am Ball bleiben.
Vorerst Grüße,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:06 Mo 24.04.2006 | | Autor: | mathiash |
Hallo zusammen,
noch ein Gedanke/ Ansatz (?):
Wir definieren einen Graphen G=(V,E) wie folgt:
[mm] V=\{T\subseteq\{1,\ldots 20\}\: |\: |T|=4\}
[/mm]
und
[mm] E=\{\{T,T'\}\: |\: |T\cap T'|\geq 2\}
[/mm]
Dann gilt
N:= |V|= {20 [mm] \choose [/mm] 4},
und G ist ein d-regulärer Graph mit
d= [mm] {4\choose 2}\cdot {16\choose 2}
[/mm]
Wir suchen in G nach einer unabhängigen Knotenmenge (Independent Set)
maximaler Kardinalität.
Vielleicht sieht man mit diesem Modell ja noch etwas mehr ?
Gruss,
Mathias
Zusatz. Hilft vielleicht eine induktive Konstruktion von G = [mm] G_n, [/mm] hier n=20 ?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 06:15 Di 25.04.2006 | | Autor: | mathiash |
Hallo und guten Morgen,
da jede zweielementige Teilmenge in höchstens einer Vierermenge vorkommen darf und man für
eine Vierermenge mindestens zwei zweielementige Teilmengen verbraucht, ist
[mm] \frac{1}{2}\cdot [/mm] { [mm] n\choose 2}=\frac{1}{2}\cdot \frac{n\cdot (n-1)}{2} [/mm]
eine obere Schranke für die Anzahl der Vierermengen in einer solchen Familie.
Viele Grüße,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:35 Di 25.04.2006 | | Autor: | Fuechsl |
Hallo Matthias,
erstens mal vielen Dank für dein Mitdenken und deine Hilfe. Der letzte Ansatz tönt einfach und viel versprechend. Wieso aber schreibst du, dass in einer Vierergruppe MINDESTENS zwei Zweierteilmengen verbraucht werden und nicht GENAU zwei?
Ich stell mir deinen Ansatz bildlich vor: Du schreibst auf [mm] \vektor{n \\ 2} [/mm] Zettel alle möglichen verschiedenen Zweiergruppen. Bei n=20 sind das also 170. Nun nimmst du jeweils zwei dieser Zettel und machst daraus eine Vierergruppe. Dann wäre es aber möglich, dass du den Zettel { 1, 2} und den Zettel {1, 3} zu einer Vierergruppe kombinierst, die dann aber gar keine Vierergruppe sondern nur eine 3er-Gruppe ist... Schreibst du deshalb "mindestens"? Das bringt mich aber nicht weiter, wenn ich die genaue Anzahl wissen will.
Ich frage mich, ob es kombinatorisch Möglichkeiten gibt, die Fälle auszuschliessen, in denen sich wiederholende Kombinationen vorkommen.
Gruss, Martin
|
|
|
| |
|
Hallo Martin und einen freundlichen Gruss nach Luzern !
Also es ist ja sicher eine obere Schranke, die nicht schart ist. Nun hast Du ja sicher recht, wenn Du schreibst / andeutest,
dass die Vierergruppen jeweils aus disjunkten Paaren gebildet werden können, d.h. ich kann jede solche Familie von Vierergruppen
erzeugen als Familie von je zwei disjunkten Paaren.
Weiterhin fallen doch damit vier weitere Paare weg:
Wenn ich [mm] \{a,b,c,d\} [/mm] über die Paare [mm] \{a,b\}, \{c,d\} [/mm] bilde, fallen genau die Paare
[mm] \{a,c\}, \{b,c\}, \{a,d\}, \{b,d\} [/mm] weg, ich darf sie nicht spaeter fuer eine weitere Vierergruppe verwenden. Alle anderen Paare darf ich, was
die Vierergruppe [mm] \{a,b,c,d\} [/mm] angeht, noch fuer weitere Vierergruppen verwenden.
Also kann ich von 6 Paaren zwei nehmen, bekomme eine Vierergruppe und darf alle 6 nicht mehr nehmen.
Ist damit die maximale Anzahl also
gleich [mm] \frac{1}{6}\cdot [/mm] {n [mm] \choose [/mm] 4} ?
Jedenfalls wäre das eine neue verbesserte obere Schranke.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:38 Fr 28.04.2006 | | Autor: | Fuechsl |
Hallo Matthias,
Ich werde die Grüsse ausrichten... 
Wie berechne ich diesen Ausdruck? Ich weiss nicht, was n () 4 bedeutet.
Gruss, Martin
|
|
|
| |
|
Hallo Martin,
das sollte n ueber 2 sein, der Formeleditor macht da scheinbar nicht das, was ich von ihm will.
Gruss + schönes Wochenende,
Mathias
Stellungnahme zur Kennzeichnung als fehlerhaft:
In der Tat hatte ich in dem vorherigen Beitrag [mm] 1\slash [/mm] 6 mal n über 4 geschrieben - es ist aber
aus Gründen, die in unten stehender Antwort auf die Nachfrage hierzu beschrieben sind, auch
[mm] 1\slash [/mm] 6 mal n über 2 eine obere Schranke.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:17 Sa 29.04.2006 | | Autor: | Fuechsl |
Hallo Matthias,
Es sollte wohl n tief 4 heissen und nicht n tief 2. Zudem kann deine Formel nicht die exakte Anzahl Gruppen liefern, denn wie ein praktischer Versuch bei n=20 zeigt, gäbe es dann eine nicht-natürliche Anzahl Gruppen, was ja nicht sein kann.
Zudem verstehe ich nicht, wieso du genau 6 Gruppen ausschliesst. Ich kann ja auch die Kombination {a, b, e, f} bilden. Das heisst, ich habe [mm] \vektor{n-2 \\ 2} [/mm] Möglichkeiten, um aus n Personen Gruppen zu bilden, die das Paar {a, b } enthalten...
Da mich diese Überlegungen gestern den halben Schlaf gekostet haben und ich mit strengen mathematischen Mitteln nicht weiterkomme, habe ich mich an den Computer gesetzt und in Excel schnell ein Programm geschrieben, das mir halt einfach alle komplett verschiedenen 4er-Gruppen bei n Personen generiert. Hier kannst du es runterladen: ![[a]](/images/paperclip.gif "Dateianhänge") Datei-Anhang. Du musst allerdings die Makros einschalten (Extras/Sicherheit/Makrosicherheit und dann Excel neu starten).
Bedienung: Einfach eine neue Zahl bei Anzahl Personen eingeben. Die Statuszeile zeigt den Berechnungsstatus. Alt-F11 liefert übrigens den Code.
Mit müden Grüssen (da gestern übernächtigt) aus der Schweiz
Martin
Dateianhänge:
Anhang Nr. 1 (Typ: xls) [nicht öffentlich]
|
|
|
| |
|
Hallo und guten Morgen,
ja , da steht ja auch zuerst [mm] \frac{1}{6}\cdot \vektor{n \\4} [/mm] (hab's jetzt mit dem Befehl vektor gemacht, die choose-Funktion kann ich hier scheinbar nicht
richtig bedienen. Soll aber n ueber 4 heissen.
Also nochmal: Das ist eine obere Schranke.
Übrigens ist aber [mm] \frac{1}{6}\cdot \vektor{n\\2} [/mm] auch eine (bessere) obere Schranke: Fuer jede Vierermenge schmeiss ich 6 Zweiermengen weg, die in keiner
anderen Vierermenge mehr enthalten sein dürfen.
Also ich hab noch keine exakte Loesung parat, hab's auch mal Kollegen erzählt. Falls ich was neues weiss. melde ich mich wieder. Schon ärgerlich, dass man
offenbar so wenig Kombinatorik kann, dass man bei einer solch natuerlich klingenden Aufgabe nicht weiterkommt. Immerhin haben wir eine quadratische obere Schranke.
Könnt denn [mm] \frac{1}{6}\cdot \vektor{n\\2} [/mm] scharf sein ? Kannst es ja mal experimentell testen oder so.
Viele Gruesse,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:44 Fr 12.05.2006 | | Autor: | DirkG |
Nochmal zur oberen Schranke:
Original von mathiash:
Wenn wir eine solche Familie von Gruppen [mm] $G_1\ldots G_N$ [/mm] betrachten, so schauen wir uns mal diejenigen an, die die 1 enthalten: Seien diese zB [mm] $G_1,\ldots G_n$ [/mm] mit [mm] $n\leq [/mm] N$. Dann sind [mm] $G_1\setminus \{1\},\ldots G_n\setminus\{1\}$ [/mm] paarweise disjunkte Teilmengen von [mm] $\{2,\ldots , 20\}$.
[/mm]
Richtig, und sie enthalten jeweils 3 Elemente. Also ist [mm] $n\leq \left\lfloor\frac{19}{3}\right\rfloor [/mm] = 6$.
Das kann man statt für 1 auch für [mm] $2,\ldots,20$ [/mm] so betrachten und erhält [mm] $N\leq \frac{6\cdot 20}{4}=30$, [/mm] da ja jede der Teilmengen viermal gezählt wird.
Entschuldigt, falls diese banale obere Schranke 30 von euch schon irgendwo oben erwähnt wurde, mir ist es bloß nirgendwo aufgefallen.
|
|
|
| |
|
Hallo zusammen,
hallo Martin !
Nach all den oberen Schranken möcht ich nun mal mit unteren Schranken anfangen:
Ich wage zu behaupten, dass sowas wie [mm] \Theta (n\cdot \log [/mm] (n))
eine untere Schranke ist.
Skizze zur Begründung: Schreiben wir die Zahlen 1 bis n auf einen Kreis. Dann nehmen wir zuerst Vierermengen von
benachbarten vier Zahlen, die sich jeweils in einer Zahl ''überlappen''. Dann nehmen wir 4 solche benachbarte Vierermengen und biden mit
deren Zahlen mindestens zwei neue Vierermengen (es geht mehr , d.h. besser). Dann von 8 und so weiter.
Das liefert schon die untere Schranke [mm] \Theta (n\cdot \log [/mm] (n)).
Gruss,
Mathias
|
|
|
|
