Hinweis auf die DSGVO: Auf unserer Seite werden keine Dritt-Anbieter-Cookies verwendet und nur Daten erfasst, welche für das Minimum an Board-Funktionalität notwendig sind.
Bevor Sie sich registrieren oder das Board verwenden, lesen Sie bitte zusätzlich die DSGVO-Erklärung, welche in der Navigationsleiste verlinkt ist.

Kurzfassung der unserer Meinung nach wichtigsten DSGVO-Punkte:
Es kann vorkommen, dass Benutzer eigenverantwortlich Videos oder sonstige Medien in ihren Beiträgen verlinken, welche beim Aufruf der Forenseite als Teil der Seite samt zugehörigem Material mitgeladen werden. Sollten Sie dies nicht wünschen, verwenden Sie beim Benutzen des Forums einen Blocker wie z.B. uMatrix, welcher das Laden von Inhaltsblöcken von Fremd-URLs effektiv unterbinden kann.
Wir blenden keine Werbung ein und schränken die Inhalte in keinster Weise bei Benutzung von Addblockern ein. Dadurch ist die Grundfunktionalität des Forums auch bei vollständigem Blockieren von Drittanbieter-Inhalten stets gegeben.

Cookies werden unsererseits nur verwendet um das Einloggen des Benutzers für die Dauer der Forenbenutzung zu speichern. Es steht dem Benutzer frei die Option 'Angemeldet bleiben' zu verwenden, damit der Cookie dauerhaft gespeichert bleibt und beim nächsten Besuch kein erneutes Einloggen mehr notwendig ist.
EMail-Adressen werden für Kontakt bei wichtigen Mitteilungen und zur Widerherstellung des Passwortes verwendet. Die verwendeten IPs können von uns ohne externe Hilfsmittel mit keiner realen Person in Verbindung gebracht werden und werden nach spätestens 7 Tagen gelöscht. Diese IPs werden höchstens verwendet um Neuanmeldungen unerwünschter oder gesperrter Nutzer zu identfizieren und zu unterbinden. Wir behalten uns daher vor bei Verdacht, die Frist für die IP-Löschung auf maximal 14 Tage zu verlängern.
Unsere Webseite läuft auf einem virtuellen Linux-Server, welcher von einem externen Anbieter gehostet wird. Etwaige Verstöße der DSGVO-Auflagen seitens dieses deutschen Hosters können wir nicht feststellen und somit auch nicht verfolgen.
Wir halten Backups unserer Datenbanken, welche in regelmäßigen Abständen als Schutz vor Katastrophen, Hackerangriffen und sonstigen Ausfällen erstellt werden. Sollte ein Nutzer die Löschung seiner Daten wünschen, betrachten wir es als Unzumutbar die Backups auch von den Daten zu befreien, da es sich hierbei um eine mehrtägiges Unterfangen handelt - dies ist für eine Einzelperson beim Betrieb eines privaten Forums nicht zumutbar möglich ohne das Backup komplett zu löschen.
Sollten Sie etwas gegen die dauerhafte anonyme Speicherung ihrer EMail-Adresse, ihres Pseudonyms und ihrer Beiträge in einem Backup haben, sehen Sie von der Registrierung in diesem Forum ab. Für Mitglieder, welche vor dem 25.05.2018 registriert waren steht jedoch das Recht im Raum, eine Löschung der Datenbank-Backups zu beantragen.



Wenn dies Ihr erster Besuch hier ist, lesen Sie bitte zunächst die FAQs sowie die wesentlichen Regeln zur Benutzung des Forums.
Um an den Diskussionen teilnehmen zu können, müssen Sie sich zunächst registrieren.

n!

Mathematische Fragestellungen
Antworten
Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 2071
Registriert: 9. Jul 2010, 04:02

n!

Beitrag von Pippen » 25. Sep 2015, 21:26

Man sagt, dass n! die Anzahl der Anordnungsmöglichkeiten von n Gegenständen ist. Wie beweist man das? ME müsste es so ähnlich gehen, wie bei der vollst. Induktion. Man zeigt es für 2! und dann zeigt man, dass es für n+1! irgend eine Gesetzmäßigkeit gibt. Kennt jmd. den Beweis?

Benutzeravatar
gradient
wohnt hier!
wohnt hier!
Beiträge: 417
Registriert: 3. Nov 2006, 09:25

Re: n!

Beitrag von gradient » 25. Sep 2015, 22:07

Hallo Pippen,

wenn man mal etwas über vollständige Induktion bewiesen hat, dann müsste das doch jetzt quasi automatisch gehen. Hast du es mal selbst versucht? Wir haben n+1 unterscheidbare Kugeln und wollen zeigen, dass es (n+1)! Reihenfolgen gibt. Man wählt eine Kugel und will diese platzieren, wofür es n+1 Möglichkeiten gibt. Die restlichen n Kugeln können nach Induktionsvoraussetzung in n! Reihenfolgen untergebracht werden, so dass es (n+1)*n!=(n+1)! Möglichkeiten gibt. Fertig.

MfG
Patrick

Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 2071
Registriert: 9. Jul 2010, 04:02

Re: n!

Beitrag von Pippen » 25. Sep 2015, 22:49

gradient hat geschrieben:Hallo Pippen,

wenn man mal etwas über vollständige Induktion bewiesen hat, dann müsste das doch jetzt quasi automatisch gehen. Hast du es mal selbst versucht? Wir haben n+1 unterscheidbare Kugeln und wollen zeigen, dass es (n+1)! Reihenfolgen gibt. Man wählt eine Kugel und will diese platzieren, wofür es n+1 Möglichkeiten gibt. Die restlichen n Kugeln können nach Induktionsvoraussetzung in n! Reihenfolgen untergebracht werden, so dass es (n+1)*n!=(n+1)! Möglichkeiten gibt. Fertig.

MfG
Patrick
Wenn ich dich recht verstehe, dann willst du beweisen, dass wenn n! korrekt ist, dann auch (n+1)! Mein Problem ist aber, ob n! überhaupt wirklich die Anzahl aller Anordnungsmöglichkeiten von n Gegenständen benennt. Wie kann man das beweisen bzw. umgekehrt: wie weiß man, ob nicht 14568675! doch nicht gleich aller Kombinationsmöglichkeiten von 14568675 Gegenständen ist?

Benutzeravatar
gradient
wohnt hier!
wohnt hier!
Beiträge: 417
Registriert: 3. Nov 2006, 09:25

Re: n!

Beitrag von gradient » 25. Sep 2015, 23:07

Hallo Pippen,
Pippen hat geschrieben: Wenn ich dich recht verstehe, dann willst du beweisen, dass wenn n! korrekt ist, dann auch (n+1)! Mein Problem ist aber, ob n! überhaupt wirklich die Anzahl aller Anordnungsmöglichkeiten von n Gegenständen benennt.
Dann hast du das Prinzip der vollständigen Induktion nicht verstanden. Ich dachte, breaker und tomS hätten das bereits ausführlich mit dir diskutiert...

MfG
Patrick

TheTheorist
Rookie
Beiträge: 40
Registriert: 22. Aug 2015, 21:35
Wohnort: Jenseits von Raum und Zeit :D

Re: n!

Beitrag von TheTheorist » 26. Sep 2015, 08:02

Ja klar, das erinnert mich an die Schule, wo wir mit Fakultäten berechnet haben, wie viele Autoschilder es geben kann, wenn man einen gewissen Ort kennt.
In der Wissenschaft beginnt alles Neue damit, daß jemand brummt 'Hmmm...ist ja komisch. -- Isaac Asimov

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: n!

Beitrag von tomS » 26. Sep 2015, 08:14

Man beweist es für n = 1 (trivial bzw. offensichtlich) oder meinetwegen noch n = 2. Dann schließt man von n = 2 auf n = 3.

Gegeben seinen n = 3 Objekte A, B, C; gesucht die Zahl der Anordnungen A(3).

Für n = 2 Objekte (z.B. A, C) gibt es A(2) = 2! Anordnungen (bereits bewiesen). Für n+1 = 3 Objekte gibt es 3 Möglichkeiten, jeweils ein Objekt wegzulassen (z.B. B). D.h. es handelt sich um insgs. 3 Varianten der Anordnungen von jeweils n = 2 Objekten, also {A,B}, {A,C} und {B,C}. Für jede einzelne dieser 3 Varianten aus 2 Objekten gibt es A(2) = 2! Anordnungen; für alle zusammen dann A(3) = 3 * 2! = 3!

Dieses Schema funktioniert für jedes n, d.h. es liefert uns den gesuchten Schluss von n auf n+1. Daher folgt für die Anzahl A der Anordnungen von n Objekten A(n) = n! Genauer: der Induktionsstart gilt z.B. nach elementarem Beweis für n = 1 bzw. n = 2; der Induktionschritt funktioniert dann wie üblich von einem bewiesenen A(n) = n! auf das zu beweisende A(n+1) = (n+1) * n! = (n+1)!

q.e.d.

EDIT: Ich habe hier noch viel mehr getan, als eigtl. notwendig, denn
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Skeltek
Site Admin
Site Admin
Beiträge: 5081
Registriert: 25. Mär 2008, 23:51
Wohnort: Stuttgart, Germany
Kontaktdaten:

Re: n!

Beitrag von Skeltek » 27. Sep 2015, 08:18

Wie will man etwas so elementares in noch kleinere Schritte zerkleinern?
Außerdem ist n! nicht die Anzahl der Möglichkeiten, n verschiedene Objekte anzuordnen.
Das gilt nur für den Spezialfall einer eindimensionalen Wohlgeordneten Anordnung mit ausgezeichneter Vorzugsrichtung.

Wieviele Möglichkeiten gibt es denn, 3 Kugeln im Dreieck anzuordnen? Wo ist oben, wo ist unten? Gibt es eine Vorzugsrichtung? Sollen Drehungen zu 120° unterscheidbar sein?

Übrigens halte ich es für intuitiver, die Formel per regressiver Induktion herzuleiten statt progressiv.
Man geht von n aus und zhlt runter statt anders herum.
Letztlich gibt es keinen Beweis, man vergleicht ja dann nur das entstehende Konstrukt mit der Fakultätsformel und stellt dann lediglich fest, dass es dieselbe Struktur hat...
Gödel für Dummies:
  • Unentscheidbarkeit - Dieser Satz ist wahr.
  • Unvollständig - Aussage A: Es existiert nur ein Element A.
  • Widersprüchlich - Dieser Satz ist falsch.

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: n!

Beitrag von tomS » 27. Sep 2015, 08:44

Skeltek hat geschrieben:Außerdem ist n! nicht die Anzahl der Möglichkeiten, n verschiedene Objekte anzuordnen.
Das gilt nur für den Spezialfall einer eindimensionalen Wohlgeordneten Anordnung mit ausgezeichneter Vorzugsrichtung.
Bisschen kleinlich, oder? Eigtl. wusste jeder, was gemeint ist.
Skeltek hat geschrieben:Übrigens halte ich es für intuitiver, die Formel per regressiver Induktion herzuleiten statt progressiv.
So habe ich im Einzelschritt letztlich argumentiert (es gibt den Begriff aber m.E nicht). Dennoch gilt das Induktionsprinzip nur in Vorwärtsrichtung.
Skeltek hat geschrieben:Letztlich gibt es keinen Beweis, man vergleicht ja dann nur das entstehende Konstrukt mit der Fakultätsformel und stellt dann lediglich fest, dass es dieselbe Struktur hat...
Was ist das anderes als ein Beweis? Anders gefragt, was fehlt dir am üblichen Beweis, um ihn als solchen anzuerkennen?
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 2071
Registriert: 9. Jul 2010, 04:02

Re: n!

Beitrag von Pippen » 1. Okt 2015, 01:27

Also doch vI:

Man beweist zunächst, dass 2! gleich aller Kombinationen für n-Gegenstände ist, nämlich 2 (Induktionsanfang). Dann beweist man, dass wenn n!, dann auch n+1! (Induktionsschritt) Gradient schreibt dazu: Wir haben n+1 unterscheidbare Kugeln und wollen zeigen, dass es (n+1)! Reihenfolgen gibt. Man wählt eine Kugel und will diese platzieren, wofür es n+1 Möglichkeiten gibt. Die restlichen n Kugeln können nach Induktionsvoraussetzung in n! Reihenfolgen untergebracht werden, so dass es (n+1)*n!=(n+1)! Möglichkeiten gibt.

Ich verstehe nun nicht, warum (n+1)*n!=(n+1)! sein soll, ich komme da bei der Klammerauflösung der linken Gleichungsseite auf (n*n!) + (n!) und das ergibt höchstens n * 2n! Das verstehe ich nicht, sonst würde ich es verstehen, leider haperts bei mir auch an den Grundlagen wie Umformungen, ich hoffe, da kann jmd. helfen.

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: n!

Beitrag von tomS » 1. Okt 2015, 02:01

Pippen hat geschrieben:Man beweist zunächst, dass 2! gleich aller Kombinationen für n-Gegenstände ist, nämlich 2 (Induktionsanfang). Dann beweist man, dass wenn n!, dann auch n+1! (Induktionsschritt) Gradient schreibt dazu: Wir haben n+1 unterscheidbare Kugeln und wollen zeigen, dass es (n+1)! Reihenfolgen gibt. Man wählt eine Kugel und will diese platzieren, wofür es n+1 Möglichkeiten gibt. Die restlichen n Kugeln können nach Induktionsvoraussetzung in n! Reihenfolgen untergebracht werden, so dass es (n+1)*n!=(n+1)! Möglichkeiten gibt.
Genau; entspricht auch meiner Argumentation.
Pippen hat geschrieben:Ich verstehe nun nicht, warum (n+1)*n!=(n+1)! sein soll, ich komme da bei der Klammerauflösung der linken Gleichungsseite auf (n*n!) + (n!) und das ergibt höchstens n * 2n!
Das ist einfach falsch; was rechnest du da? Du musst nur die Definition der Fakultät ansetzen.

Zunächst ist per def. n! = 1 * 2 * 3 * ... * n

Damit ist auch per def. (n+1)! = 1 * 2 * 3 * ... * n * (n+1) = n! * (n+1)

q.e.d.

(das hat noch nichts mit der Abzählung der Permutationen zu tun sondern ist rein die Anwendung der Definition der Fakuktät)
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Skeltek
Site Admin
Site Admin
Beiträge: 5081
Registriert: 25. Mär 2008, 23:51
Wohnort: Stuttgart, Germany
Kontaktdaten:

Re: n!

Beitrag von Skeltek » 1. Okt 2015, 11:40

tomS hat geschrieben:
Pippen hat geschrieben:Man beweist zunächst, dass 2! gleich aller Kombinationen für n-Gegenstände ist, nämlich 2 (Induktionsanfang).
[...]
Genau; entspricht auch meiner Argumentation.
Da ist ja schon der Induktionsanfang falsch ^^
tomS hat geschrieben:
Pippen hat geschrieben:Ich verstehe nun nicht, warum (n+1)*n!=(n+1)! sein soll, ich komme da bei der Klammerauflösung der linken Gleichungsseite auf (n*n!) + (n!) und das ergibt höchstens n * 2n!
Das ist einfach falsch; [...]
Es ist richtig; die Klammer hat er richtig aufgelöst. Und der Rückschluss
(n+1)! = (n+1)*n! <= 2n*n! ist auch richtig.
Die Frage ist eher, wieso er glaubt, dass 2n * n! kleiner sein soll als (n+1) * n! = (n+1)!; man skann ja erkennen, dass 2n >= (n+1) ist.
Pippen hat geschrieben:Ich verstehe nun nicht, warum (n+1)*n!=(n+1)! sein soll
(n+1)! = m! = 1*2*3*4* ... * (m-2)*(m-1)*(m+0)
ergibt sich direkt wenn man
m! umschreibt mit n+1=m.
Man multipliziert alle Zahlen von 1 bis m, mehr ist das nicht.
tomS hat geschrieben:
Skeltek hat geschrieben:Übrigens halte ich es für intuitiver, die Formel per regressiver Induktion herzuleiten statt progressiv.
So habe ich im Einzelschritt letztlich argumentiert (es gibt den Begriff aber m.E nicht). Dennoch gilt das Induktionsprinzip nur in Vorwärtsrichtung.
Das Prinzip des Widerspruchsbeweises durch infiniten Regresses ist bereits seit Fermat bekannt (er war damals ganz stolz auf seine Methode).
Es ist beweisbar, dass jede existente natürliche Zahl durch eine arithmetische Folge mit Schrittweite=1 auf die 1 zurückgeführt werden kann, sonst wäre sie nicht endlich.
Egal bei welcher Zahl man anfängt, wird die streng monoton fallende Folge zwangsläufig in endlichen Schritten bei der 1 enden.
Es ist theoretisch völlig egal, ob man beim Produkt oben oder unten anfängt, es ist von 1 beginnend lediglich "eingebürgerter"; da dies für viele Beweise so verwendet wird und man nicht absichtlich gegen die Gewöhnung arbeiten möchte.
Ob man bei n beginnend und abwärts zählend bei 1 oder 0 ankommt ist genauso fraglich, wie ob man bei 1 beginnend nach endlichen Schritten bei n ankommt.
Gödel für Dummies:
  • Unentscheidbarkeit - Dieser Satz ist wahr.
  • Unvollständig - Aussage A: Es existiert nur ein Element A.
  • Widersprüchlich - Dieser Satz ist falsch.

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: n!

Beitrag von tomS » 1. Okt 2015, 21:16

Zu 2! = 2
nein, der Induktionsanfang ist nicht falsch; für n = 1 ist das offensichtlich trivial; für n = 2 beweist man das explizit; ab n = 3 läuft die eigtl. Induktion, das ist völlig OK.

Zu 2n * n!
wenn es nur so wäre; Pippen schreibt nicht 2n * n! sondern n * 2n! was ich als n * (2n)! lese - und das ist falsch.

Zur "regressive Induktion"
ich weiß nicht, was du eigtl. erklären willst; geht es um die Definition von n! oder um den Beweis der Anzahl der Permutationen P(n) = n! ? Ersteres kannst du definieren wie du möchtest, aber darum geht es hier nicht. Es geht aber um letzteres. Wie führst du diesen Beweis? Das verstehe ich nicht.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Skeltek
Site Admin
Site Admin
Beiträge: 5081
Registriert: 25. Mär 2008, 23:51
Wohnort: Stuttgart, Germany
Kontaktdaten:

Re: n!

Beitrag von Skeltek » 2. Okt 2015, 09:44

tomS hat geschrieben: wenn es nur so wäre; Pippen schreibt nicht 2n * n! sondern n * 2n! was ich als n * (2n)! lese - und das ist falsch.
Wenn du gedanklich eine Klammer setzt, wo keine hingehört...
tomS hat geschrieben: Zur "regressive Induktion"
ich weiß nicht, was du eigtl. erklären willst; geht es um die Definition von n! oder um den Beweis der Anzahl der Permutationen P(n) = n! ? Ersteres kannst du definieren wie du möchtest, aber darum geht es hier nicht. Es geht aber um letzteres. Wie führst du diesen Beweis? Das verstehe ich nicht.
Ich meinte nur, es sei intuitiver n*(n-1)* ... *2*1 zu rechnen statt 1*2* ... *(n-1)*n.
(n+1)! = n*(n-1)! = n*(n-1)*(n-2)! = ... lässt sich rekursiv viel einfacher handhaben als (n+1)! = 1* (n+1)!/1! = 1 * 2* (n+1)! / 2! = ... = n!*(n+1) * (n+1)! / (n+1)!
Wüsste jedoch nicht wirklich, was man an ersterem noch groß beweisen müsste.
Aber wenn man es denn unbedingt für (n+1)! beweisen will, dann geht man auch so vor, dass man (n+1)*(n!) von oben beginnend anfängt und dann sofort im ersten Schritt feststellt, dass es der Definition der Fakultät entspricht...
Gödel für Dummies:
  • Unentscheidbarkeit - Dieser Satz ist wahr.
  • Unvollständig - Aussage A: Es existiert nur ein Element A.
  • Widersprüchlich - Dieser Satz ist falsch.

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: n!

Beitrag von tomS » 2. Okt 2015, 19:02

Es geht auch nicht um den Beweis von (n+1)! = (n+1) * n!, denn das ist einfach eine Definition ohne Beweis. Es geht um den Beweis von P(n) = n! Und da kommst du um Induktion m.E. nicht herum.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Skeltek
Site Admin
Site Admin
Beiträge: 5081
Registriert: 25. Mär 2008, 23:51
Wohnort: Stuttgart, Germany
Kontaktdaten:

Re: n!

Beitrag von Skeltek » 3. Okt 2015, 12:12

Doch, rekursiv.
Du transferierst durch Ziehen nach und nach alle Elemente aus der ungeordneten Menge A zur geordneten Menge B und schaust bei jedem Ziehen, wieviele Möglichkeiten du hast aus A zu wählen(rekursive Herangehensmethode)
Du willst durch Ziehen alle Elemente der geordneten Menge A zur nicht geordneten Menge B transferieren, also ziehst du aus A in einer linearen Reihenfolge und schaust wieviele Möglichkeiten du hast sie bei B einzugliedern.

Wo liegt denn jetzt für dich der Unterschied, ob du die Permutation P oder deren Inverses P' direkt konstruierst?
Gödel für Dummies:
  • Unentscheidbarkeit - Dieser Satz ist wahr.
  • Unvollständig - Aussage A: Es existiert nur ein Element A.
  • Widersprüchlich - Dieser Satz ist falsch.

Benutzeravatar
gradient
wohnt hier!
wohnt hier!
Beiträge: 417
Registriert: 3. Nov 2006, 09:25

Re: n!

Beitrag von gradient » 3. Okt 2015, 12:15

Hallo Skeltek,

auch Rekursionsgleichungen müssen induktiv bewiesen werden.

MfG
Patrick

Skeltek
Site Admin
Site Admin
Beiträge: 5081
Registriert: 25. Mär 2008, 23:51
Wohnort: Stuttgart, Germany
Kontaktdaten:

Re: n!

Beitrag von Skeltek » 4. Okt 2015, 02:03

Hallo gradient,

das kommt komisch rüber von jemandem, der bereits im ersten Antwort-Posting das ganze rekursiv beschrieben hat.
gradient hat geschrieben: Man wählt eine Kugel und will diese platzieren, wofür es n+1 Möglichkeiten gibt. Die restlichen n Kugeln können nach Induktionsvoraussetzung in n! Reihenfolgen untergebracht werden, so dass es (n+1)*n!=(n+1)! Möglichkeiten gibt.
Du beschreibst hier
(n+1)!= (n+1) * n! = (n+1)! * n * (n-1)! ...
und das ist rekursiv.

Induktiv wäre zu zeigen, dass zu jeder einzelnen Permutation von n Elementen das Hinzufügen eines weiteren Elementes auf n+1 verschiedene Arten möglich ist.
Bei der induktiven Methode zeigst du, dass es n+1 verschiedene Möglichkeiten gibt eine zusätzliche Kugel in die Menge von n bereits sortierten Kugeln einzufügen.

Ich bevorzuge nunmal (n+1)! auf n! zurückzuführen, statt von n auszugehen und daraus (n+1)! zu bilden. Das halte ich für intuitiver, ob ihr wollt oder nicht.
Gödel für Dummies:
  • Unentscheidbarkeit - Dieser Satz ist wahr.
  • Unvollständig - Aussage A: Es existiert nur ein Element A.
  • Widersprüchlich - Dieser Satz ist falsch.

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: n!

Beitrag von tomS » 4. Okt 2015, 10:08

Das ist auch gar nicht das Problem.

Wenn du unter der Voraussetzung der Kenntnis von P(n) den Wert von P(n+1) ableitest, also P(n+1) auf P(n) zurückführst, dann gehst du in diesem einen Schritt rekursiv vor. Insgesamt gehst du jedoch induktiv vor. Du setzt nämlich P(n) voraus, ohne es in diesem Schritt bewiesen zu haben, und berechnest P(n+1).
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Benutzeravatar
gradient
wohnt hier!
wohnt hier!
Beiträge: 417
Registriert: 3. Nov 2006, 09:25

Re: n!

Beitrag von gradient » 4. Okt 2015, 10:37

Hallo Skeltek,

auf Toms Aussage
Es geht um den Beweis von P(n) = n! Und da kommst du um Induktion m.E. nicht herum.
hast du mit
Doch, rekursiv.
geantwortet. Daraus folgere ich, dass du meinst, dass man keine vollständige Induktion benötigt. Falls ja, bin ich auf einen Beweis gespannt.

Vielleicht verstehst du unter "induktiv" allerdings auch etwas anderes. Was ich im ersten Beitrag gemacht habe, war ein ganz normaler Beweis durch vollständige Induktion, wobei ich den Induktionsanfang nicht mehr hingeschrieben habe (den hatte Pippen noch hinbekommen). Wie Tom schon geschrieben hat, habe ich lediglich mit Hilfe der Induktionsvoraussetzung festgestellt, dass P(n)=n! => P(n+1)=(n+1)!, und in diesem Induktionsschritt darf man sehr wohl rekursiv vorgehen.

MfG
Patrick

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: n!

Beitrag von tomS » 4. Okt 2015, 12:36

Wie wär's mit folgendem Ansatz:

Gegeben sind n Plätze ___..._ sowie n Gegenstände {1,2,3,...,n}

Für den ersten Platz gibt es n Möglichkeiten, Gegenstände zu setzen, also P[down]1[/down] =n; rechts daneben stehen jeweils die noch verbleibenden Gegenstände.

1__..._: {,2,3,...,n}
2__..._: {1,3,...,n}
...
n__..._: {1,2,3,...,n-1,}

Für den zweiten Platz gibt es dann noch jeweils (n-1) Möglichkeiten, Gegenstände zu platzieren, also P[down]1,2[/down] = n(n-1).

12_..._: {,,3,...,n}
...

Damit gelangt man rekursiv zu

P[down]1,2,...,n[/down] = P(n) = n!

Ich denke, dieser Beweis kommt ohne Induktion aus. Insbs. setze ich nicht voraus, dass die einen Wert P für n-1 Gegenstände bereits kenne.

@skeltek: hattest du so etwas im Sinn?
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Skeltek
Site Admin
Site Admin
Beiträge: 5081
Registriert: 25. Mär 2008, 23:51
Wohnort: Stuttgart, Germany
Kontaktdaten:

Re: n!

Beitrag von Skeltek » 6. Okt 2015, 01:30

Sorry, hatte eigentlich schon eine Antwort gepostet, sehe sie hier aber irgendwie nicht mehr.

Ja, sowas hatte ich im Sinn.
Es gibt eigentlich zwei Herangehensweisen:
Elemente E={a,b,c,d,e...,x,y,z}.
und
Plätze P={1,2,3,4,...,24,25,26}

entweder Methode A:
Man kann nun sagen, man hat 26 verschiedene Elemente und wählt, welches Element man auf Platz 1 setzt.
Danach hat man 25 Elemente aus denen man das für Platz 2 wählen kann usw.
Damit erhält man letztlich 26*25*24*...*3*2*1 Möglichkeiten.
oder Methode B:
Man wählt als erstes Element a und weist ihm einen Platz rechts zu und erhält P(1)={a}.
Danach nimmt man b und weist ihm einen Platz in P zu und erhält entweder P(2)={a,b} oder P(2)={b,a}; man hat also 2 verschiedene Plätze b einzugliedern, entweder vor a oder nach a). Danach mach man mit c weiter bei dem man dann 3 verschiedene Plätze hat es einzusortieren.
Das ergibt dann 1*2*3*...*24*25*26 Möglichkeiten.

Der wesentliche reinformale Unterschied der beiden ergibt sich dann, wenn zur ausgangsmenge E ein weiteres Element hinzukommt.
Bei ersterer Methode A fängt man mit 27 Möglichkeiten an und hat es nach nur einem Schritt auf den Fall mit 26 Elementen zurückgeführt.
Bei zweiter Methode B hat man 26! Permutationen wie die ersten 26 Elemente gegliedert sein können und im induktiv gewonnenen 27sten Schritt bei allen bisherigen 26! Permutationen 26+1 verschiedene Möglichkeiten das 27ste Element einzugliedern.

Methode B erschien mir nicht ganz so intuitiv, da man da von einer ganzen Menge an verschiedenen Permutationen(26! Stück) ausgeht und jede einzelne dieser Permutationen dann mit 27 durchmultipliziert.
Gödel für Dummies:
  • Unentscheidbarkeit - Dieser Satz ist wahr.
  • Unvollständig - Aussage A: Es existiert nur ein Element A.
  • Widersprüchlich - Dieser Satz ist falsch.

Antworten