Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Formel beweisen für mögliche Permutationen

Formel beweisen für mögliche Permutationen

Universität / Fachhochschule

Sonstiges

Tags: Fixpunkt, Kombinatorik, permutation, Sonstiges

Underfaker aktiv_icon

13:33 Uhr, 02.12.2011

Guten Tag :-)

Ich habe aus einem anderem Forum eine Formel die ich benötige, allerdings darf ich natürlich nicht ohne Herleitung/Beweis solcher Formeln, diese so einfach benutzen.

Deshalb wollte ich fragen ob mir da jemand sagen kann wie das geht, bzw. vielleicht weiß sogar jemand wo so eine Herleitung für die Formel schon steht.

Es geht um:

N_{n, k} = \frac{n!}{k!} \cdot (\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - ... \pm \frac{1}{(n - k)!})

Ich glaube, dass man da unter Umständen mit der Siebformel hinkommt?! Aber ich hab da keine Ahnung von.

Es wäre super wenn da jemand was zu weiß :-)

Gruß und schonmal Danke

Hierzu passend bei OnlineMathe:
Mitternachtsformel

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Gemischte Aufgaben der Kombinatorik
Kombinatorik: Ziehen mit Reihenfolge und mit Zurücklegen
Kombinatorik: Ziehen mit Reihenfolge und ohne Zurücklegen
Kombinatorik: Ziehen ohne Reihenfolge und ohne Zurücklegen

hagman aktiv_icon

13:51 Uhr, 02.12.2011

Kommt drauf an, was du mit

N_{n, k}

bezeichnest

. .

Underfaker aktiv_icon

13:54 Uhr, 02.12.2011

Ah ich hab nicht gesehen, dass das nicht klar war, dachte das stünde im Titel.

N_{n, k}

beschreibt die Anzahl der Permutationen einer n-elementigen Menge mit

k

Fixpunkten.

hagman aktiv_icon

17:01 Uhr, 02.12.2011

Die n-Permutationen mit

k

Fixpunkten zerfallen in drei Teile

N_{n, k} = A_{n, k} + B_{n, k} + C_{n, k}

wie folgt:

Erstens diejenigen, bei denen

f (n) = n

ist. Durch Streichen von

n

stehen diese in Bijektion mit den Permutationnen mit einem Element und einem Fixpunkt weniger.
Die Anzahl dieser Fälle ist also

A_{n, k} = N_{n - 1, k - 1}

Zweitens diejenigen, bei denen

f (n) \neq n,

aber

f (f (n)) = n

. Betrachte die Permutatin

g

der elemente

1, ..., n - 1,

die gegeben ist durch

g (f (n)) = f (n)

sowie

g (x) = f (x)

für

x \neq f (n)

. Dann hat

g

genau

k + 1

Fixpunkte. Wir kommen von

g

zurück zu

f,

indem wir den richtigen der

k + 1

Fixpunkte auswählen und diesen mit

n

permutieren. Für die Anzahl dieser Fälle gilt also

B_{n, k} = (k + 1) \cdot N_{n - 1, k + 1}

Drittens diejenigen mit

f (f (n)) \neq n

. Betrachte die Permutatin

g

der elemente

1, ..., n - 1,

die gegeben ist durch

g (x) = f (n),

falls

g (x) = n,

und

g (x) = f (x),

falls

g (x) \neq n

. Dann hat

g

genau

k

Fixpunkte. Wir kommen von

g

zurück zu

f,

indem wir den richtigen der

(n - 1) - k

Nicht-Fixpunkte auswählen und diesen mit

n

permutieren. Für die Anzahl dieser Fälle gilt also

C_{n, k} = (n - 1 - k) \cdot N_{n - 1, k}

.

Es folgt

N_{n, k} = A_{n, k} + B_{n, k} + C_{n, k} = N_{n - 1, k - 1} + (k + 1) \cdot N_{n - 1, k + 1} + (n - 1 - k) \cdot N_{n - 1, k}

.
Das sollte doch ein Ansatz sein, um die Formel per Induktion nach

n

zu beweisen.

Underfaker aktiv_icon

17:57 Uhr, 02.12.2011

Vielen Dank schonmal.

Aber was ist denn nun bspw. dieses

N_{n - 1, k - 1},

soll das die Funktion sein, die ich angegeben habe?

Weil dein Konstrukt ist schon sehr beeindruckend und nicht grade einfach zu durchblicken, zumindestens für mich.

Wenn ich das mit Induktion beweisen soll brauche ich dann ein

k

oder funktioniert das einfach indem ich

n

zeige und dann

n + 1

ebenfalls zeige.

Ich habe noch nicht so ganz eine Vorstellung von dem Endgebilde, dass ich benutze um die Induktion anzuwenden.

Am Ende bleibt noch die Frage was ich denn einsetze um

n

zu zeigen, benötigt werden ja eigentlich n-Elementige Mengen, und mit

n = 1

dürfte doch nur für einen Fixpunkt 1 rauskommen, da keine andere Möglichkeit funktioniert.

Irgendeinen Tipp was sinnvoll für einen Anfang wäre?

Danke :-)

achja bspw dieses "+(k+1)" kommt das einfach als Produkt vor die Formel?

Underfaker aktiv_icon

18:18 Uhr, 02.12.2011

Hab das entsprechend eingesetzt (vorausgesetzt es soll auch so gemacht werden).

\Rightarrow N_{n, k} = \frac{(n - 1)!}{(k - 1)!} \cdot (\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - ... \pm \frac{1}{(n - 1 - (k - 1))!}) + (k + 1) \cdot \frac{(n - 1)!}{(k + 1)!} \cdot (\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - ... \pm \frac{1}{(n - 1 - (k + 1))!}) + (n - 1 - k) \cdot \frac{(n - 1)!}{k!} \cdot (\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - ... \pm \frac{1}{(n - 1 - k)!})

Hui das ist ziemlich lang...

Soll das nun das Konstrukt sein oder ist das Quarck?

hagman aktiv_icon

10:57 Uhr, 03.12.2011

Naja, zumindest theoretisch (und wenn ich keinen Fehler in meiner Überlegung hatte) müsste sich die rechte Seite entsprechend vereinfachen lassen und sich wie gewünscht als gleich mit der linken herausstellen. Ich hatte es aber nicht durchgerechnet.

Underfaker aktiv_icon

11:24 Uhr, 03.12.2011

Ok, danke für deine Überlegungen. :-)

Ich habe zumindestens genug Selbstkenntnis um zu wissen, dass ich (persönlich) das nicht vereinfachen kann.

Dafür stehen in den Klammern immer verschiedene Ausdrücke mal geht es bis

(n - k)

dann bis

(n - 2 - k)

usw. also immer unterschiedlich lang, wobei ich aufgrund des ks nie weiß wie lang eigentlich, dazu kommt noch das die Produkte immer unterschiedliche Faktoren an erster Stelle haben,

\frac{(n - 1)!}{(k - 1)!}

oder

\frac{(n - 1)!}{(k + 1)!}

bspw. .

In diesem Sinne bin ich wohl an der Formel gescheitert :-)

hagman aktiv_icon

13:03 Uhr, 03.12.2011

Mal schauen, was da noch geht.
Mit der Abkürzung

a_{r} := \frac{{(- 1)}^{r}}{r!}

und

s_{r} := \sum_{i = 0}^{r} a_{i}

ergibt sich für die rechte Seite

\frac{(n - 1)!}{(k - 1)!} \cdot (\frac{1}{0!} - \frac{1}{1!} \pm ... + \frac{{(- 1)}^{n - k}}{(n - k)!}) + (k + 1) \cdot \frac{(n - 1)!}{(k + 1)!} \cdot (\frac{1}{0!} - \frac{1}{1!} \pm ... + \frac{{(- 1)}^{n - k - 2}}{(n - k - 2)!}) + (n - 1 - k) \cdot \frac{(n - 1)!}{k!} \cdot (\frac{1}{0!} - \frac{1}{1!} \pm ... + \frac{{(- 1)}^{n - k - 1}}{(n - k - 1)!})

= \frac{(n - 1)!}{(k - 1)!} \cdot s_{n - k} + (k + 1) \cdot \frac{(n - 1)!}{(k + 1)!} \cdot s_{n - k - 2} + (n - 1 - k) \cdot \frac{(n - 1)!}{k!} \cdot s_{n - k - 1}

= \frac{(n - 1)!}{k!} \cdot k \cdot s_{n - k} + \frac{(n - 1)!}{k!} \cdot s_{n - k - 2} + (n - 1 - k) \cdot \frac{(n - 1)!}{k!} \cdot s_{n - k - 1}

= \frac{(n - 1)!}{k!} \cdot (k \cdot s_{n - k} + s_{n - k - 2} + (n - 1 - k) \cdot s_{n - k - 1})

= \frac{(n - 1)!}{k!} \cdot (k \cdot s_{n - k} + (s_{n - k} - a_{n - k} - a_{n - k - 1}) + (n - 1 - k) \cdot (s_{n - k} - a_{n - k}))

= \frac{(n - 1)!}{k!} \cdot (n \cdot s_{n - k} - a_{n - k - 1} - (n - k) \cdot a_{n - k})

.
Nun gilt aber

a_{n - k} = - \frac{1}{n - k} \cdot a_{n - k - 1},

so dass sich weiter ergibt

= \frac{(n - 1)!}{k!} \cdot n \cdot s_{n - k}

= \frac{n!}{k!} \cdot s_{n - k}

.
Und das ist tatsächlich der Ausdruck auf der linken Seite, nämlich die behauptete Formel für

N_{n, k}

.
Gilt also die Formel für

n - 1

(bei beliebigem

k,

denn wir verwenden ja das gesuchte

k

ebenso wie

k - 1

und

k + 1

auf der rechten Seite), so gilt sie auch für

n

(und beliebiges

k)

.
Es muss sich also noch um den Induktionsanfang gekümmert werden, also

n = 1 :

Die behauptete Formel liefert für

n = 1

und

k = 0

\frac{n!}{k!} \cdot (\frac{1}{0!} - \frac{1}{1!}) = 0

für

n = 1

und

k = 1

\frac{n!}{k!} \cdot (\frac{1}{0!}) = 1

.

Jetzt ist noch ein kleines Problem zu beachten: Die Formel ergibt nur einen Sinn, wenn

0 \leq k \leq n

gilt. Aber unsere Rekursionsformel

N_{n, k} = N_{n - 1, k - 1} + (k + 1) \cdot N_{n - 1, k + 1} + (n - 1 - k) \cdot N_{n - 1, k}

könnte in Grenzfällen aus diesem Bereich "ausbrechen":
Da wäre zunächst einmal der Fall

k = 0,

der auf

N_{n,0} = N_{n - 1, - 1} + N_{n - 1,1} + (n - 1) \cdot N_{n - 1,0}

führt, wobei also

N_{n - 1, - 1}

auftritt, für den die Fakultsformel keinen Sinn ergibt. Wie kann man diesen Fall korrekt behandeln?
Zum anderen wäre da der Fall

k = n,

der auf

N_{n, n} = N_{n - 1, n - 1} + (n + 1) \cdot N_{n - 1, n + 1} - N_{n - 1, n}

führt, sowie der Fall

k = n - 1,

der auf

N_{n, n - 1} = N_{n - 1, n - 2} + n \cdot N_{n - 1, n}

führt. Die auftretenden

N_{n - 1, n + 1}

und

N_{n - 1, n}

ergeben auch nicht recht einen Sinn. Man sollte sich hier gesondert klar machen, dass die Fakutätsformel die korrekten Werte

N_{n, n} = 1

und

N_{n, n - 1} = 0

liefert.

Underfaker aktiv_icon

16:07 Uhr, 03.12.2011

wow da hst du dir aber (zu) viel Mühe gemacht, schlechtes Gewissen...

Um zu den Punkten ganz unten zu kommen, genau da bin ich auch schon drüber gestolpert als ich das in Ansätzen probiert habe.

Soll man dann definieren wie die Ergebnisse lautet oder aber einschränken für wann jene Formel nur gilt.

Bspw. gilt die Formel nur für

0 \leq k \leq n

Der Fall

k = n

muss von der Logik her 1 ergeben, vielleicht per Definition deklarieren?

Es gibt ja nur eine Möglichkeit der Abbildung, nämlich die Menge an sich mit

i = Q (i)

bspw. also jedes Element ist ein Fixpunkt.

Für

k = n - 1

muss 0 gelten, wenn man nämlich

n - 1

Fixpunkte hat bleibt noch ein Element das einen Platz finden müsste, dieser Platz ist aber nur dort wo es wieder einen Fixpunkt gäbe, das wäre dann aber einer zuviel, also ein Widerspruch, entsprechend gibt es keine mögliche Permutation.

Für

k = 0

also keine Fixpunkte, habe ich jedoch keine Idee, es müssten ja alle Permutationen sein ohne alle Permutationen mit mindestens einem Fixpunkt, das scheint mir jedoch relativ umständlich zu sein...

Tausend Dank

=)

that's awesome

Underfaker aktiv_icon

17:01 Uhr, 03.12.2011

Um direkt schonmal weite rzu machen:

Wenn ich den Induktionsschritt machen möchte, soll ich dann wieder

k = 1

und

k = 0

benutzen?

Wenn ich folgendes mache.

n \to n + 1

(und

k = 1)

\frac{(n + 1)!}{1!} \cdot (\frac{1}{0!} - \frac{1}{1!} + ... \pm \frac{1}{n!})

und nun?

für

k = 0

\frac{(n + 1)!}{0!} \cdot (\frac{1}{0!} - \frac{1}{1!} + ... \pm \frac{1}{(n + 1)!})

Diese Form ist für mich einfach, änlich wie das Umstellen der Formel recht schwierig.

Unter Umständen ist das ja auch garnicht richtig?!

hagman aktiv_icon

18:45 Uhr, 03.12.2011

Besser sollte man wie folgt vorgehen

1 .)

Im Fall

k = n

liefert die behauptete Formel:

\frac{n!}{n!} \cdot (\frac{1}{0!})

und das ist 1. Da es genau eine Permutation mit

n

Fixpunkten gibt, habe wir die Korrektheit für

k = n

somit bereits endgültig gezeigt (also sogar ohne Induktion / Verwendung der Rekursion)

2 .)

Im Fall

k = n - 1

liefert die behauptete Formel:

\frac{n!}{(n - 1)!} \cdot (\frac{1}{0!} - \frac{1}{1!})

und das ist 0. Da es keine Permutation mit genau

n - 1

Fixpunkten gibt, habe wir die Korrektheit für

k = n - 1

somit ebenfalls bereits endgültig gezeigt.

3 .)

für den Fall

k = 0

kann es sinnvoll sein,sich die Rekursion nochmal getrennt anzuschauen: bei einer fixpunktfreien Permutation

f

von

{1, ..., n}

gilt auf jeden Fall

f (n) \neq n

. Falls

f (f (n)) = n

ist, streiche sowohl

n

als auch

f (n),

nummeriere ggf. um, und du erhältst eine fixpunktfreie Permutation von

n - 2

Objekten. Man kommt von hierher auf

n - 1

Weisen zur ursprünglichen Permutation zurück. Falls dagegen

f (f (n)) \neq n,

findet man wie oben eine fixpunktfreie Permutation von

n - 1

Objekten und kommt auf

n - 1

Weisen zurück.
Es folgt also die Rekursion

N_{n,0} = (n - 1) \cdot (N_{n - 1,0} + N_{n - 2,0})

N_{1,0} = 0

und

N_{0,0} = 1

ergibt sich bereits aus

1 .)

und

2 .)

als mit der behaupteten Formel übereinstimmend. Hiervon ausgehend sollte der Induktionsbeweis ähnlich wie oben klappen.

4 .)

Die sonstigen Fälle, also

0 < k < n - 1

behandelt man wie oben. Beachte, dass dann zwar von der Induktionsvoraussetzungen teilweise auch die Fälle

1 .), 2 .)

und

3 .)

benötigt werden, aber das ist in Ordnung, da diese ja schon gezeigt wurden.

Underfaker aktiv_icon

19:08 Uhr, 03.12.2011

Was meinst du denn mit Induktionsbeweise wie oben? Bisher gibts ja noch keine einzige vollständig abgeschlossende Induktion, sondern nur die Induktionsschritte

n = 1

mit

k = 0

und

1,

meinst du vielleicht das?

soll ich bei 3.dann eine Induktion machen, weil

n = 1

schon gezeigt ist, mit

n + 1

?
und immernoch besteht bei mir die Frage was mache ich mit dem

k,

das gilt dann auch insbesondere für 4.

Vielen dank nochmal

=)

Hab zu 3. da sgemacht:

für

n = 1

hatten wir das ja schon gezeigt, genauso wie für 0 (wie mir gerade beim erneuten Rechnen nochmal klar wurde...)

wenn ich jetzt darauf aufbaue und sage

n \to n + 1

gibt das folgendes:

N_{n + 1,0} = (n + 1 - 1) (N_{n,0} + N_{n + 1,0})

= n (n! (\frac{1}{0!} - \frac{1}{1!} + . .

\pm \frac{1}{n!}) + (n + 1)! (\frac{1}{0}! - \frac{1}{1}! + . .

\pm \frac{1}{(1 + n)!}))

bis hierher und nicht weiter, müsste da was zusammengefasst werden?
Mach ich das denn überhaupt so?

und bei 4. weiß ich ncoh nciht wie ich das zeigen soll, weil ich 4. eigentlich so wie 3. gezeigt hätte

n = 1

und dann

n \to n + 1

Underfaker aktiv_icon

19:52 Uhr, 05.12.2011

Hat nicht sollen sein, schade trotzdem vielen Dank, damit bin ich wahrscheinlich immenroch viel weiter als der Rest im Kurs :-)

948458

946772

	Status: nicht eingeloggt	Noch nicht registriert?