Auf wie viele Arten kann man 4 aus 15 Rittern auswählen, wenn keine Tischnachbarn dabei sind?

Question

15 Ritter sitzen auf einem runden Tisch. Auf wie viele Arten lassen sich vier Ritter für die Rettung von Prinzessin Clara vor dem Drachen auswählen, wenn keine Sitznachbarn ausgewählt werden dürfen?

Die Antwort nach langem Ausprobieren mit kleineren Beispielen habe ich. Diese lautet:

( n / (n-k) ) · ( n-k über k )

Konkret heißt es hier:

15/11 · (11 über 4) = 450

Nun überlege ich, wie man das argumentiert, und komme leider nicht drauf. Kann mir vielleicht jemand helfen?

Vielen Dank in Voraus.

Grüße

Ana

Comments

Ich habe eine ähnliche Aufgabe in einem Mathe-Forum gefunden: http://matheplanet.com/default3.html?call=viewtopic.php?topic=132449

Zunächst einmal gibt es insgesamt (20*19*18)/3! = 20*19*3 = 1140 viele Möglichkeiten, Leute auszuwählen.

''3er-Blöcke'', d.h. wo alle drei ausgewählten Personen nebeneinander sitzen, gibt es insgesamt 20 (1-3,2-4,....,18-20,19-1,20-2)

Reine ''2er-Blöcke'', d.h. wo genau zwei nebeneinander sitzen und die dritte Person nicht benachbart ist, gibt es 20*16, denn es gibt 20 ''2er-Blöcke'' und die dritte Person darf nicht rechts oder links daneben sitzen, also gibt es für diese nur noch 16 Möglichkeiten.

Damit gibt es dann insgesamt 20 + 20*16 =340 viele Möglichkeiten, ''benachbarte Tripel'' zu wählen und mithin 1140-340 = 800 viele Möglichkeiten, für die Auswahl nicht-benachbarter Personen.

Habe dann versucht, meine Aufgabe nach diesem Muster zu lösen, aber irgendwas muss ich übersehen haben, denn ich komme nicht auf die richtige Lösung. Die Lösung ist die folgende:

Zunächst gibt es 15 über 4 viele Möglichkeiten, 4 aus 15 Ritter zu wählen, ohne jegliche Sitzordnung zu beachten. Das sind 1356 Arten.

Betrachte nun die Blöcke, in denen benachbarte Ritter vorkommen:

"4-er Blöcke" : alle 4 Ritter sitzen nebeneinander -> 15 Möglichkeiten.

"3-er Blöcke" : 3 Ritter sitzen nebeneinander und der vierte mit diesen nicht benachbart ist -> 15·10=150

"2-er Blöcke" : 2 Ritter sitzen nebeneinander und die anderen zwei mit denen nicht benachbart sind -> 15·11=165

Nun sollte man die Blöcke, wo benachbarte Ritter vorkommen abziehen, und ich erhalte:

1356-15-150-165 = 1026.

Das sind immer noch zu viele im Vergleich zur richtigen Lösung 450. Ich denke, ich übersehe etwas bei den 2-er Blöcken, und zwar dass die restlichen zwei Ritter auch nebeneinander sitzen können, und diese Möglichkeiten müssen auch abgezogen werden. Ich bin mir aber nicht sicher.

Sieht jemand meinen Fehler?

Answer 1

"3-er Blöcke" : 3 Ritter sitzen nebeneinander und der vierte mit diesen nicht benachbart ist -> 15·10=150

"2-er Blöcke" : 2 Ritter sitzen nebeneinander und die anderen zwei mit denen nicht benachbart sind -> 15·11*10/2=1650/2 = 825

Ich ergänze das hier zu 11*10/2 : Die Plätze der übrigen beiden Ritter, weil die Reihenfolge egal ist: durch 2.

Nun habe ich aber die Varianten mit 2 Zweierblöcken 15*10/2=75 doppelt in der Rechnung drinn. Also wieder subtrahieren.  (Wiederum Reihenfolge(hier der 2erBlöcke) irrelevant. Daher durch 2)

Nun sollte man die Blöcke, wo benachbarte Ritter vorkommen abziehen, und ich erhalte:

1365-15-150-(825-75) = 450

1365 = (15 tief 4)

Das sind immer noch zu viele im Vergleich zur richtigen Lösung 450. Ich denke, ich übersehe etwas bei den 2-er Blöcken, und zwar dass die restlichen zwei Ritter auch nebeneinander sitzen können, und diese Möglichkeiten müssen auch abgezogen werden. Ich bin mir aber nicht sicher.

Ich vermute, dass es jetzt stimmt, da 450 rauskommt…

Comments

Vielen Dank Lu!!

Weißt du, wie man auf die Formel kommt?

---

Meinst du jetzt auf deine Formel? Da hab ich im Moment keine Idee.
Wenn du den Anfang nachgezählt hast, müsstest du das vermutlich über einen Induktionsbeweis versuchen.