Derangements < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:46 Sa 23.08.2008 | | Autor: | Hund |
| Aufgabe | | Auf wie viele Arten kann man die Buchstaben AAABBCCDEF permutieren, so dass nie zwei gleiche Buchstaben nebeneinander stehen? |
Hallo,
ich vermute, dass das auf Derangements hinausläuft. Allerdings fehlt mir der Ansatz, wie ich die Permuatation ansetzten soll. Ich komme irgendwie nicht weiter.
Ich hoffe, ihr könnt mir helfen.
Gruß
Hund
|
|
| |
|
> Auf wie viele Arten kann man die Buchstaben AAABBCCDEF
> permutieren, so dass nie zwei gleiche Buchstaben
> nebeneinander stehen?
> Hallo,
>
> ich vermute, dass das auf Derangements hinausläuft.
> Allerdings fehlt mir der Ansatz, wie ich die Permuatation
> ansetzten soll. Ich komme irgendwie nicht weiter.
Du könntest von der Gesamtzahl [mm] $\frac{10!}{3!\cdot 2!\cdot 2!}$ [/mm] der Permutationen diejenigen subtrahieren, bei denen zwei gleiche Buchstaben nebeneinander stehen.
Zum Beispiel kannst Du die Zahl der Permutationen subtrahieren, in denen zwei $A$ nebeneinander stehen. Problem: dann subtrahierst Du allerdings die Fälle, in denen sogar drei $A$ nebeneinander stehen, zweimal.
Zudem können sich diese Fälle auch für verschiedene Buchstaben überlappen: Es können z.B. gleichzeitig zwei $A$ und zwei $B$ nebeineinander stehen. Du müsstest also mit dem ![[]](/images/popup.gif) Ein/Auschlussprinzip arbeiten (auch: "Siebformel" genannt):
[mm]\frac{10!}{3!\cdot 2!\cdot 2!}-\big|\{\ldots AA\ldots\}\,\cup\, \{\ldots AAA\ldots\}\,\cup\, \{\ldots BB\ldots\}\,\cup\, \{\ldots CC\ldots\}\big|=\cdots[/mm]
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 13:12 So 24.08.2008 | | Autor: | Hund |
Hallo,
danke für deine Antwort. An Inklusion-Exklusion habe ich auch schon gedacht, nur hat man es hier dann mit jeweils 4 Mengen zu tun und da wird die Formel für Inklusion-Exklusion schon sehr lang und die Rechnung sehr aufwendig (und bei uns sind die Aufgaben immer so gewählt, dass die Lösung nur paar Zeilen lang ist).
Ich hätte vielleicht noch sagen sollen, dass ich die Aufgabe aus einem Übungsblatt habe. Dort war sie Teil b) (von a) und b)). Aufgabe a) lautete:
Wie viele Permutationen mit genau 4 Fixpunkten besitzt die Menge der Zahlen 1-13?
Die Lösung zu a) kann man ohne großes Überlegen sofort hinschreiben [mm] (\vektor{13 \\ 4}D_{9}) [/mm] und deshalb habe ich gedacht, dass man b) doch genau so einfach lösen könnte (vielleicht mit Hilfe von a)?).
Gibt es vielleicht einen einfacheren Lösungsweg oder muss man hier wirklich so eine lange Rechnung machen?
Gruß
Hund
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:23 Mi 27.08.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
Ich habe mir eine etwas einfachere Frage gestellt:
Wie gross ist die Anzahl der Permutationen einer Menge
von n Elementen, wenn unter den n Elementen eine
Anzahl k von solchen Elementen sind, welche in einer
Permutation nicht unmittelbar benachbart sein dürfen ?
(Bedingung für k: [mm] k\le \bruch{n+1}{2})
[/mm]
Mit n=7 und k=3 hätte man also z.B. die
| Aufgabe | Auf wie viele Arten kann man die Buchstaben AAABCDE permutieren,
so dass nie zwei gleiche Buchstaben nebeneinander stehen? |
Die Antwort ist in diesem konkreten Beispiel:
[mm] \bruch{5!*4!}{3!*2!}=240
[/mm]
oder allgemein:
[mm] \bruch{(n-k+1)!*(n-k)!}{k!*(n-2k+1)!}
[/mm]
Um auf diese Formel zu kommen (anhand des konkreten
Beispiels), werden zuerst die Möglichkeiten der Platzierung der
drei "A" abgezählt. Zu diesem Zweck macht man aus jedem
einzelnen "A" ein "Tandem" T = "AR" mit einem angehängten R,
welches einfach die Aufgabe hat, den Platz unmittelbar rechts
neben dem A freizuhalten. Solch ein Tandem belegt in
der Permutation die Stellen 1 und 2, 2 und 3, ..... oder 7 und 8.
(Es wird also ein zusätzlicher 8. Platz gebraucht).
Insgesamt nehmen die 3 Tandems 3*2=6 der 8 Stellen ein.
Frei bleiben weitere 2 Stellen, allgemein n+1-2k Stellen.
Belegen wir alle diese mit einem weiteren Hilfssymbol P,
so haben wir also z.B. die Folge
PTTPT
welche für "PARARPAR" steht.
Die Anzahl der Wörter aus genau 3 "T" und 2 "P" ist gleich
[mm] \bruch{5!}{3!*2!}
[/mm]
allgemein hätten wir k mal "T" und (n-2k+1) mal "P", also
die Anzahl
[mm] \bruch{(n-k+1)!}{k!*(n-2k+1)!}
[/mm]
Auf so viele Arten können wir also die "A"s platzieren.
Jetzt können wir auf die Hilfssymbole T und P verzichten,
auch auf jenes, das den zusätzlichen Platz Nr. 8 (bzw. n+1)
eingenommen hat. Diesen brauchen wir für das Folgende
nicht mehr.
Auf die frei gebliebenen 7-3=4 (bzw. n-k) Plätze
werden nun die übrigen Buchstaben B,C,D,E verteilt.
Die Anzahl der Möglichkeiten dazu ist natürlich 4! bzw.
(n-k)!.
Insgesamt haben wir also die Anzahl
[mm] \bruch{5!}{3!*2!}*4!
[/mm]
bzw.
[mm] \bruch{(n-k+1)!}{k!*(n-2k+1)!}*(n-k)!
[/mm]
an Permutationen ohne benachbarte "A".
Al-Chw.
|
|
|
|
