Kombinatorik < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Keine "Aufgabenstellung" sondern ein reales Problem bei der Programmierung automatisch erstellter Hausaufgaben |
Hallo Mathegemeinde.
Das Problem ist folgendes:
Es gibt n Arten von Objekten. Zu jeder dieser n Arten gibt es k verschiedene Objekte, wobei k gleich ist für alle Kategorien. Wieviele Pärchen (a,b) verschiedener Objekte kann ich bilden?
Diese Pärchen dürfen sich nicht wiederholen und a und b dürfen nicht aus der selben Kategorie stammen. Außerdem gilt (a,b)=(b,a).
Für k=1 kann ich das Problem mit meinem Schulwissen lösen nämlich Anzahl [mm] =\bruch{n!}{(n-2)!*2} [/mm]. Für k>1 ist diese Formel aber nicht zu gebrauchen, da sie k offensichtlich nicht berücksichtigt.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt. Und habe mir Mühe beim Formulieren gegeben, sollte doch etwas unklar sein würde ich das gerne verbessern. Würde mich sehr über Hilfe freuen.
Beste Grüße,
Kai
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:06 Fr 20.12.2013 | | Autor: | Teufel |
Hi und willkommen hier im Matheraum! :)
Stell dir mal vor, dass alle Objekte in einer Reihe liegen.
[mm] \underbrace{11, 12, \ldots, 1k}_{\text{Kategorie 1}},\underbrace{21,\ldots, 2k}_{\text{Kategorie 2}}, \ldots, \underbrace{n1, \ldots, nk}_{\text{Kategorie n}}
[/mm]
Will man 2 Objekte daraus auswählen, kommt man erst einmal auf [mm] $\vektor{nk \\ 2}$ [/mm] Möglichkeiten. Soweit kein Problem. Nun dürfen aber nicht 2 Objekte aus der gleichen Kategorie gezogen werden. Das kann man aber einfach abziehen. Auf wie viele Arten kann man Objekte der Kategorie 1 ziehen? [mm] $\vektor{k \\ 2}$ [/mm] Möglichkeiten. Das gleiche für alle anderen Kategorien. Also sind genau [mm] $n\vektor{k \\ 2}$ [/mm] Möglichkeiten dabei, die du nicht haben möchtest.
Damit kommt man auf [mm] $\vektor{nk \\ 2}-n\vektor{k \\ 2}$.
[/mm]
Für $k=1$ liefert das deine Formel, wegen [mm] \vektor{1 \\ 2}=0.
[/mm]
|
|
|
| |
|
Alternative zum Vorschlag von Teufel:
Du Suchst dir zunächst eine Kategorie aus (n Mgl.), daraus ein Objekt (k Mgl.), dann eine andere Kategorie (n-1 Mgl.) und daraus wieder ein Objekt (k Mgl.). Also hast du
n*k*(n-1)*k Möglichkeiten.
Du erhältst auf diese Weise aber zu jedem Paar (a|b) auch das Paar (b|a), also jedes Paar doppelt. Deshalb musst du noch durch 2 dividieren:
n*k*(n-1)*k/2.
Genau denselben Wert erhältst du beim Ausmultiplizieren der Binomialkoeffizienten von Teufel.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:28 Fr 20.12.2013 | | Autor: | Teufel |
Heho!
Ah das ist eigentlich viel einfacher und liefert direkt eine kürzere Formel. ;) Gut, gut!
|
|
|
|
