Kombinatorisches Problem < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:11 Sa 07.01.2006 | | Autor: | foo |
| Aufgabe | Geg.: Menge M = {1, 2, ..., n} und die Permutation (1, 2, ..., n).
Ges.: Anzahl aller Möglichkeiten 3 Zahlen aus dieser Permutation so auszuwählen, dass keine zwei Zahlen miteinander benachbart sind (wobei 1 und n auch als benachbart betrachtet werden) |
Hallo,
z.B. für M = {1,2,3,4,5,6} und Permutation: (1,2,3,4,5,6) sind es zwei Möglichkeiten ((1,3,5) und (2,4,6)) für M = {1,2,3,4,5,6,7} und Permutation: (1,2,3,4,5,6,7) sind es (1,3,5), (1,3,6), (1,4,6), (2,4,6), ...
Mein Problem ist, dass ich keine allgemeine Formel in Abhängigkeit von n finden kann, die mir diese Anzahl liefert.
Ohne die Bedingung das zwei nicht benachbart sein dürften wäre es ja einfach n über 3.
Vielleicht fällt ja einem von euch eine ein..
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo!
Also ich bin mir nicht 100% sicher, aber ist es nicht so, dass du am Anfang $n$ Möglichkeiten hast. Dann sind die benachbarten Zahlen verboten, das sind $2$ Stück, also hast du dann noch $n-3$ Möglichkeiten (da ja die erste gewählte Zahl auch verboten ist $3$ anstatt $2$). Für die dritte Zahl hast du somit noch $n-6$ Möglichkeiten.
Also ist die Anzahl deiner Möglichkeiten $3$ Zahlen rauszunehmen, ohne dass eine benachbarte dabei ist:
[mm] $\#\text{Mögl.}=n\cdot (n-3)\cdot [/mm] (n-6)$ Und das musst du vielleicht nochmal mit $n$ (wg. Permutationen) multiplizieren.
Wie gesagt, diese Angaben sind ohne Gewähr.
Gruß Martin
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:18 So 08.01.2006 | | Autor: | foo |
hmm, das scheint nicht zu funktionieren, ich hatte mir sowas wie (n*(n-3)*(n-5))/n! überlegt (durch die Anzahl der Permutationen teilen) aber leider kommt da auch nicht das richtige Ergebnis raus :(
|
|
|
|
