Wie viele Möglichkeiten gibt es, sich die Hand zu geben?

In einer Gruppe von 9 Menschen, denen jede Person genau die Hand schüttelt 2 der anderen Leute aus der Gruppe. Lassen X sei die Anzahl der Möglichkeiten, diese Handshakes auszuführen. Nehmen 2 Handshake-Muster (Anordnungen) unterscheiden sich genau dann, wenn mindestens 2 Menschen, die sich nach einem Muster (Arrangement) die Hand geben, geben sich nach dem anderen Muster (Arrangement) nicht die Hand. Finden X .

Ich denke, Fallarbeit ist der richtige Weg.

A schüttelt mit B & C . D schüttelt mit E & F . G schüttelt mit H & ICH .

Vielleicht könnte ich eine Wiederholungsbeziehung verwenden, aber ich sehe keinen möglichen Weg.

Insgesamt gibt es:

( 9 3 ) ⋅ ( 6 3 ) ⋅ ( 3 3 ) = 1680

Möglichkeiten, Gruppen von drei Personen zu wählen.

Aber ich tue nichts anderes zu diesem Problem, und das ist eindeutig die falsche Antwort.

Bitte nur Hinweise!

mögliches Duplikat der klassischen Handshake-Frage
Nein, es ist kein Duplikat.
In deinem Beispiel B , C , E , F , H Und ICH nur einer Person die Hand geben.

Antworten (1)

Die Handshakes können durch einen Graphen modelliert werden, dessen Anzahl Sie ermitteln möchten 2 -regelmäßige Graphen auf neun Scheitelpunkten.

Es ist bekannt 2 -reguläre Graphen haben Zyklen als zusammenhängende Komponenten.

Für die Anzahl der angeschlossenen Komponenten gibt es drei Möglichkeiten:

Eine verbundene Komponente:

In diesem Fall ist der Graph ein Zyklus an 9 Scheitelpunkten kann der Zyklus als Permutation beginnend mit angesehen werden 1 Scheitelpunkte der Reihe nach auflisten. Es gibt 8 ! solche Permutationen, aber sie geben uns jeden Zyklus zweimal (einmal in jeder Reihenfolge).

Daher gibt es 8 ! 2 = 20 , 160 solche Zyklen. Es wird gut sein, die folgende Formel zu beachten: Es gibt ( k − 1 ) ! 2 Möglichkeiten, einen Zyklus mit zu machen k Eckpunkte.

Zwei verbundene Komponenten:

Wir müssen je nach Größe der beiden Komponenten unterteilen:

3 Und 6 : Wählen Sie zuerst die drei Scheitelpunkte in ( 9 3 ) Wege, nach obiger Formel gibt uns 2 ! 2 5 ! 2 Möglichkeiten, die Zyklen zu bilden. Es gibt sie also ( 9 3 ) 2 ! 2 5 ! 2 = 5 , 040 Zyklen dieser Art.

4 Und 5 : Wählen Sie zuerst die vier Scheitelpunkte in ( 9 4 ) Wege, nachdem die obige Formel uns gibt 3 ! 2 4 ! 2 Möglichkeiten, die Zyklen zu bilden. Es gibt sie also ( 9 4 ) 3 ! 2 4 ! 2 = 4 , 536

Drei verbundene Komponenten:

Es gibt ( 9 3 , 3 , 3 ) Möglichkeiten, die neun Scheitelpunkte in die drei Gruppen aufzuteilen. Dies unterscheidet natürlich jeden der Faktoren, so dass die Antwort tatsächlich lautet ( 9 3 , 3 , 3 ) 1 3 ! = 280

Also letzte Antwort ist 20 , 160 + 5 , 040 + 4 , 536 + 280 = 30 , 016

gute Antwort. Aber: (1) Was meinst du mit "einen Zyklus machen mit k Scheitelpunkte?" (2) Wie haben Sie hergeleitet: ( k − 1 ) ! / 2 ?
Nun, wenn Sie haben k vetices 1 , 2 , 3 … k Auf wie viele Arten können wir Kanten hinzufügen, sodass sie einen Kreis bilden? Der üblichste Zyklus wäre das Verbinden 1 mit 2 Und k und zu verbinden k mit k − 1 Und 1 . Und verbinden Sie jede andere Nummer J mit J − 1 Und J + 1 . Dies ist einer der möglichen Zyklen. Aber es gibt noch viele andere Zyklen. Sie können einen Zyklus beschreiben, indem Sie eine Liste angeben, die in beginnt 1 und enthält jeden Scheitelpunkt 1 . Zum Beispiel: 1 , 2 , 3 , 4 … k beschreibt den eingangs erwähnten Kreislauf. Jeder Zyklus kann mit einer solchen Liste charakterisiert werden. Jeder Zyklus hat jedoch zwei Listen.
Hinweis zum Beispiel 1 , 2 , 3 … k Und 1 , k , k − 1 , k − 2 … 3 , 2 Geben Sie uns den gleichen Zyklus. Weil dort sind ( k − 1 ) ! Permutationen der Elemente 2 , 3 , 4 , 5 … k und jeder zwei dieser Permutationen entspricht ein Zyklus, wir folgern, dass es gibt ( k − 1 ) ! 2 Zyklen auf den Elementen ( 1 , 2 , 3 , 4 , … k )
Mehr als ein "Hinweis" :-) aber ich denke, diese Antwort ist der richtige Weg.
Oh, das tut mir leid. Aus irgendeinem Grund hat mein Gehirn diesen Teil der Frage nicht analysiert, ich habe es erst jetzt begriffen, es muss die Hitze sein.
@dREaM, kein Problem, das ist eine großartige Antwort. Nur ein bisschen mehr Verwirrung. Meinen Sie mit "Zyklus", wie viele Sitzordnungen möglich sind? Auch keine Permutationen richtig? Aber für die Permutationen, warum hast du das weggelassen? 1 ? Sie sagten: „Permutationen der Elemente 2 , 3 , 4 , 5 , . . . , k und zu allen zwei dieser Permutationen ...". Warum nicht k ! / 2 anstatt ( k − 1 ) ! / 2 ?
@dREaM, meinst du mit Zyklus, wie viele Händeschütteln möglich sind? Oder wie die Reihenfolge der Anordnung?
@Amad27, wenn du platzierst N Personen in einem Kreis (Zyklus in den Grafiken), können Sie jede Anordnung bei schneiden N Stellen (zwischen jedem Paar von Personen), und dies ergibt insgesamt N ! lineare Anordnungen, also gibt es N ! / N = ( N − 1 ) ! kreisförmige Anordnungen. Aber beim Händeschütteln gibt es keine Reihenfolge von links nach rechts, also ( N − 1 ) ! / 2 .
@Amad27. Nehmen Sie alternativ den Kreis der Menschen und beginnen Sie mit dem, der da ist 1 nach links gehen. Der nächste ist einer von N − 1 andere dann N − 2 , ..., bis eben 1 Möglichkeit, das heißt ( N − 1 ) ! kreisförmige Befehle, aber die gleiche Abfolge von Personen in einer Abfolge, die nach rechts geht, ist also der gleiche Satz von Handshakes ( N − 1 ) ! / 2 .
@vonbrand, Sie finden also, wie viele mögliche Anordnungen richtig sind? Nicht standortbezogen? Weil Sie einen Punkt richtig fixieren?
@Amad27, ja.
Wie viele Möglichkeiten gibt es, sich die Hand zu geben?
AntwortenHierDatenschutz-Bestimmungen1y, 0v