Die Mathe-Redaktion - 18.11.2017 03:28 - Registrieren/Login
Auswahl
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 251 Gäste und 5 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » n Masten, k Flaggen (Induktionsbeweis)
Druckversion
Druckversion
Autor
Kein bestimmter Bereich J n Masten, k Flaggen (Induktionsbeweis)
bruschkov
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 29.06.2016
Mitteilungen: 7
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2017-09-12


Hallo liebe Matroider,

folgende Aufgabe aus Norbert Henze - "Stochastik für Einsteiger":



Durch probieren und überlegen habe ich folgende Formel gefunden, die mir für alle Werte von n und k  (so die Induktionsannahme) das richtige Ergebnis liefert und die ich nun per Induktion (zunächst über n) beweisen möchte:

<math>n+1 := Anzahl\ der\ Masten,\ k:= Anzahl\ der\ Flaggen</math>

<math>
k^{\underline{k}}*n^{\overline0} + k^{\underline{k-1}}*n^{\overline1} + ... + k^{\underline{0}}*n^{\overline{k}}=
\sum_{i=0}^{k} k^{\underline{k-i}}*n^{\overline{i}} =
\sum_{i=0}^{k} \frac{k!}{i!}*\frac{(n-1+i)!}{(n-1)!}
</math>

Allerdings will mir die Umformung der Gleichung in <math>(n+1)^{\overline{k}}</math>, und damit die Vervollständigung des Beweises, nicht gelingen...

Ich würde mich über jede Hilfe freuen, leider beiße ich mir an diesem Problem schon einige Tage die Zähne aus.

(P.S.: Induktionsanfang etc. habe ich der Kürze wegen weggelassen, kann ich bei Bedarf aber ergänzen.)



  Profil  Quote  Link auf diesen Beitrag Link
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 728
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2017-09-13


Hallo bruschkov,

mir ist gerade nicht klar, was du da nun mit Induktion zeigen möchtest? Die Begründung ist doch recht einfach. Mal dir doch mal deine Masten (z.B 3 Stück) hin und verteile deine Flaggen (z.B. 5 Stück). Wie viele Möglichkeiten hast du für deine erste Flagge? Wie viele dann für die nächste Flagge?

Gruß,

Küstenkind



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 3636
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2017-09-13


2017-09-13 17:08 - Kuestenkind in Beitrag No. 1 schreibt:
Wie viele Möglichkeiten hast du für deine erste Flagge? Wie viele dann für die nächste Flagge?

Ich denke, so einfach ist es nicht. Ich würde zunächst alle Flaggen auf einen langen Mast aufziehen und den dann in n Stücke zersägen.

Grüße
StrgAltEntf



  Profil  Quote  Link auf diesen Beitrag Link
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 728
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2017-09-13


Hallo StrgAltEntf,

was stört dich denn genau? Für die erste Flagge hat man <math>n</math> Möglichkeiten (Masten). Für jede weitere Flagge kommt ein neuer Platz dazu, nämlich direkt unter oder über der letzten Flagge. Und damit landen wir direkt bei der Definition der aufsteigenden Faktoriellen.

Gruß,

Küstenkind



  Profil  Quote  Link auf diesen Beitrag Link
bruschkov
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 29.06.2016
Mitteilungen: 7
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2017-09-13


2017-09-13 17:31 - Kuestenkind in Beitrag No. 3 schreibt:
Hallo StrgAltEntf,

was stört dich denn genau? Für die erste Flagge hat man <math>n</math> Möglichkeiten (Masten). Für jede weitere Flagge kommt ein neuer Platz dazu, nämlich direkt unter oder über der letzten Flagge. Und damit landen wir direkt bei der Definition der aufsteigenden Faktoriellen.

Gruß,

Küstenkind

Hallo Kuestenkind,

danke für die Antwort. Ja, das ist wahrscheinlich die einfachste Art, dies zu beweisen und auch die im Buch gegebene Lösung.

2017-09-13 17:08 - Kuestenkind in Beitrag No. 1 schreibt:
Hallo bruschkov,

mir ist gerade nicht klar, was du da nun mit Induktion zeigen möchtest? Die Begründung ist doch recht einfach. Mal dir doch mal deine Masten (z.B 3 Stück) hin und verteile deine Flaggen (z.B. 5 Stück). Wie viele Möglichkeiten hast du für deine erste Flagge? Wie viele dann für die nächste Flagge?

Gruß,

Küstenkind

Das ist ja letzlich auch die Aussage von "meiner" rekursiven Formel: <math>k^{\underline{k}} </math> Möglichkeiten, alle Flaggen auf den ersten Mast zu verteilen.  <math>k^{\underline{k-1}} </math> Möglichkeiten, alle Flaggen bis auf eine an den ersten Mast zu hängen und <math>n^{\overline{1}} </math> Möglichkeiten, die verbleibende Flagge auf die verbleibenden Masten zu verteilen. Usw.

Es gibt wahrscheinlich keinen guten Grund, diese Formel über Induktion zu beweisen, außer der Neugier: interessieren, wie es ginge, würde es mich schon…



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 3636
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2017-09-13


2017-09-13 17:31 - Kuestenkind in Beitrag No. 3 schreibt:
was stört dich denn genau? Für die erste Flagge hat man <math>n</math> Möglichkeiten (Masten). Für jede weitere Flagge kommt ein neuer Platz dazu, nämlich direkt unter oder über der letzten Flagge. Und damit landen wir direkt bei der Definition der aufsteigenden Faktoriellen.

Hallo Kuestenkind,

doch, das scheint zu funktionieren, obwohl ich die Konstruktion nicht gerade offensichtlich finde. Deinen ersten Beitrag hatte ich erst anders verstanden.

[Die Antwort wurde nach Beitrag No.3 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 3510
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2017-09-13


@bruschkov

Um zu beweisen, dass n(n+1)...(n+k-1) tatsächlich die Anzahl der Möglichkeiten unter den gegebenen Voraussetzungen beschreibt, würde ich induktiv nach k folgendermaßen vorgehen, wobei ich annehme, dass auch Küstenkind das so gemeint hat:

Für k=1, also nur eine Flagge habe ich tatsächlich nur die n Möglichkeiten sie an einer der n Masten zu befestigen, d.h., die Formel ist korrekt.  Sind dann k Flaggen schon befestigt, wofür es nach Induktionsannahme n(n+1)...(n+k-1) Möglichkeiten gibt, so kann ich die (k+1)-te Flagge entweder zuoberst an einen der n Masten aufhängen oder auch direkt unterhalb von einer der k bereits aufgehängten Flaggen, was in Summe n+k Möglichkeiten ergibt. Zusammengenommen, d.h., kombiniert mit allen Möglichkeiten für die Setzung der k Flaggen davor, ergibt das dann tatsächlich insgesamt n(n+1)...(n+k-1)(n+k) Möglichkeiten alle k+1 Flaggen an einer der n Masten zu befestigen, was die Richtigkeit der Formel dann auch für k+1 Flaggen beweist.

[Die Antwort wurde nach Beitrag No.4 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 728
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2017-09-13


Huhu bruschkov,

meinst du das?

<math>\displaystyle \sum\limits_{i=0}^{k} \frac{k!(n-1+i)!}{i!(n-1)!}=k!\sum\limits_{i=0}^{k} \binom{i+n-1}{i}</math>

Mit <math>j:=n-1</math>:

<math>\displaystyle k!\sum\limits_{i=0}^{k} \binom{i+j}{i}=k!\binom{k+j+1}{k}</math>

Und somit:

<math>\displaystyle  k!\binom{k+n}{k}=\frac{k!(k+n)!}{k!n!}=\frac{(k+n)!}{n!}=\frac{((n+1)+k-1)!}{((n+1)-1)!}=(n+1)^{\overline{k}}</math>

Die Induktion für <math>\displaystyle \sum\limits_{i=0}^{k} \binom{i+j}{i}=\binom{k+j+1}{k}</math> überlasse ich dir.  razz

Gruß,

Küstenkind




  Profil  Quote  Link auf diesen Beitrag Link
bruschkov
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 29.06.2016
Mitteilungen: 7
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2017-09-16


2017-09-13 21:12 - Kuestenkind in Beitrag No. 7 schreibt:
Huhu bruschkov,

meinst du das?

<math>\displaystyle \sum\limits_{i=0}^{k} \frac{k!(n-1+i)!}{i!(n-1)!}=k!\sum\limits_{i=0}^{k} \binom{i+n-1}{i}</math>

Mit <math>j:=n-1</math>:

<math>\displaystyle k!\sum\limits_{i=0}^{k} \binom{i+j}{i}=k!\binom{k+j+1}{k}</math>

Und somit:

<math>\displaystyle  k!\binom{k+n}{k}=\frac{k!(k+n)!}{k!n!}=\frac{(k+n)!}{n!}=\frac{((n+1)+k-1)!}{((n+1)-1)!}=(n+1)^{\overline{k}}</math>

Die Induktion für <math>\displaystyle \sum\limits_{i=0}^{k} \binom{i+j}{i}=\binom{k+j+1}{k}</math> überlasse ich dir.  razz

Gruß,

Küstenkind



Hallo Küstenkind,
genau das meinte ich. Wow und danke, da wäre ich wahrscheinlich in 10 Jahren nicht selber drauf gekommen.

@weird: Ebenfalls danke für deinen Ansatz, der auch einfacher gewesen wäre als meiner.

Ich lerne also: Die richtige Beweisstrategie spart unter Umständen viel Arbeit. smile

Als Bonus für den interessierten Leser hier der Beweis für  <math>\displaystyle \sum\limits_{i=0}^{k} \binom{i+j}{i}=\binom{k+j+1}{k}</math> (Deswegen auch die verspätete Antwort...)

Es gilt: <math>\displaystyle \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}</math>

Also kann man umformen:
<math> \displaystyle
\binom{k+j+1}{k} =\binom{k+j}{k} + \binom{k+j}{k-1} = \binom{k+j}{k} + \binom{k+j-1}{k-1} + \binom{k+j-1}{k-2} =
</math>
...
<math> \displaystyle
= \binom{k+j}{k} + \binom{k+j-1}{k-1} + ... + \binom{k+j-(k-1)}{k-(k-1)} + \binom{k+j-(k-1)}{k-k}
</math>

<math> \displaystyle
= \binom{k+j}{k} + \binom{k+j-1}{k-1} + ... + \binom{j+1}{1} + \binom{j+1}{0}
</math>

<math> \displaystyle
= \binom{k+j}{k} + \binom{k+j-1}{k-1} + ... + \binom{j+1}{1} + \binom{j}{0}
</math>

<math> \displaystyle =\sum\limits_{i=0}^{k} \binom{i+j}{i} </math>

Mit dieser Umformung wäre die Gleichung bewiesen, eine Induktion ist dann mehr nötig?



  Profil  Quote  Link auf diesen Beitrag Link
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 728
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2017-09-17


Hallo bruschkov,

jap - das sollte so durchgehen. Gut gemacht! Hier dann noch die Indoktrination (nach <math>k</math>):

Den IA lasse ich mal weg.

<math>\displaystyle \sum\limits_{i=0}^{k+1} \binom{i+j}{i}=\sum\limits_{i=0}^{k} \binom{i+j}{i}+\binom{k+1+j}{k+1}=\binom{k+j+1}{k}+\binom{k+j+1}{k+1}=\binom{k+1+j+1}{k+1}</math>

Abschließen möchte ich dann mit einem wunderbaren Zitat von dir:


Es gibt wahrscheinlich keinen guten Grund, diese Formel über Induktion zu beweisen, außer der Neugier: interessieren, wie es ginge, würde es mich schon…

Dieser Satz hat mich erst veranlasst zu meinem Beitrag bzw. weiter über dieses Problem nachzudenken. Bewahre dir bitte diese Neugier! Wenn doch nur jeder meiner Schüler so denken würde - Schule wäre ein noch schönerer Ort.  smile

Gruß (und einen schönen Sonntag wünscht),

Küstenkind



  Profil  Quote  Link auf diesen Beitrag Link
bruschkov hat die Antworten auf ihre/seine Frage gesehen.
bruschkov hat selbst das Ok-Häkchen gesetzt.
bruschkov wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 

 AQA

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]