Die Mathe-Redaktion - 15.10.2019 04:16 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
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. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

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

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Anzahl Wörter ohne Teilwort 01 bestimmen
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Anzahl Wörter ohne Teilwort 01 bestimmen
pram
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 21.09.2019
Mitteilungen: 9
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-09-22 21:16


Hallo zusammen,

ich bitte euch um Hilfe in folgender Frage. Ich muss Anzahl der Wörter der Länge \(n \in \mathbb N \) über \(\sum = \{0, 1 \}\) bestimmen, die nicht das Teilwort 01 enthalten.

Ich gehe folgendermaßen vor. Sei \(M_n\) die Menge der Wörter aus \(\sum^n\), die nicht das Teilwort 01 enthalten.

Es gilt \(|M_0|\) = 1 => nur das leere Wort enthalten; \(|M_1|\) = 2 => 0 und 1 enthalten.

Nun betrachten wir ein Wort \(w \in M_{n+1} \)\(\), dann können wir \(w\) schreiben als \(w = xab\) mit \(a, b \in \{0,1\} \) und \(x \in M_{n-1} \).

Falls \(b\) = 0, dann ist für \(xa\) ein beliebiges Wort aus \(M_n\) möglich.
Falls \(b\) = 1, dann muss \(a\) = 1 gelten, und das ganze Wort \(x\) muss aus 1ern bestehen.

Somit |\(M_{n+1}\)| = |\(M_{n}\)| + 1.

Ist das korrekt? Danke euch für jede Hilfe!



  Profil  Quote  Link auf diesen Beitrag Link
PrinzessinEinhorn
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2017
Mitteilungen: 2217
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-09-22 21:45


Hallo,

ja, dass Resultat ist korrekt.
Allgemein gilt also $|M_n|=n+1$. Das ist vielleicht 'besser' als deine rekursive Formel, wenn du einen geschlossenen Ausdruck angibst.

Ich finde deinen Beweis in Ordnung.
Man könnte ihn vielleicht besser aufschreiben.

Du leitest hier ja eine Art Induktion ein, ohne dann eine formelle Induktion (Induktionsanfang, Induktionsvoraussetzung, Induktionsschritt) durchzuführen.

Der Beweis ist dann ja im Grunde wie deiner, nur ein wenig geordneter und vielleicht auch prägnanter.

Etwa:

Falls b = 1, dann muss a = 1 gelten, und das ganze Wort x muss aus 1ern bestehen.

Hier ist natürlich klar, was du meinst. Die Begründung fällt aber ein wenig vom Himmel, auch wenn wohl jeder deinem Gedankengang folgen kann, warum das entsprechende Wort eben nur aus 1'en bestehen kann.

Auch gibst du zum Beispiel zwei Beispiele $|M_0|=1$ und $|M_1|=2$. Was natürlich alles richtig ist. Für die Induktion bräuchtest du natürlich nur eines. Auch wenn man natürlich auch eine Vermutung für die Anzahl entwickeln muss, also ist es immer gut mehr Beispiele zu betrachten. Aber ist das was du in dem Absatz schreibst wirklich für den Beweis entscheidend?

Dann nimmst du $w\in M_{n+1}$ mit $w=xab$ wobei $x\in M_{n-1}$.
Wieso schreibst du nicht $w=xa$ mit $x\in M_n$ und $a\in \{0,1\}$.
Das ist meiner Meinung nach deutlicher und ja auch genau das, was du im Induktionsschritt tun würdest.

Dort würdest du ja deine Menge $M_{n+1}$ als disjunkte Vereinigung von zwei Mengen schreiben. Nämlich jene die die Worte der Form $x0$ und $x1$ enthalten.

Mit deinen gemachten Überlegungen beendest du dann auch diesen Schritt leicht.

Kurzum:

Dein Beweis geht so wohl in Ordnung, aber das strukturierte Beweisverfahren der vollständigen Induktion könnte dir helfen deine Ideen prägnanter zu formulieren und auf das wesentliche zu reduzieren, was letztendlich einen Beweis ergibt, der sich schöner lesen würde.

:)



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


Hm, macht ihr euch das Leben hier nicht unnötig schwer? Die Wörter ohne 01 haben doch alle die Form
000...000
100...000
110...000
...
111...110
111...111

Also eine Folge von Einsen gefolgt von einer Folge von Nullen. Wenn die Wortlänge n betragen soll, gibt es davon genau n+1 Stück.



  Profil  Quote  Link auf diesen Beitrag Link
PrinzessinEinhorn
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2017
Mitteilungen: 2217
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-09-22 22:10


Wie sich die Worte der Menge kombinatorisch konstruieren lassen, ist ja klar. Auf einer 0 kann nur eine 0 folgen etc.

Einfach auflisten würde ich sie jedoch nicht, da hätte ich dann schon ein paar Bauchschmerzen, aber das muss ja nichts heißen.



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


Hallo PrinzessinEinhorn,

hier hätte ich allerdings keine Bauchschmerzen. Klar ist: Wenn man behauptet, dass eine Aussage trivial ist, sollte man ohne lange zu überlegen in der Lage sein, die Aussage formal zu beweisen. Allerdings muss man nicht jede triviale Aussage formal beweisen.

Wo die Grenze ist, ist natürlich Auslegungssache. (In meiner Zeit als Korrektor in den Anfängervorlesungen habe ich schon mal Punktabzug gegeben, wenn ein Student 30 Seiten - kein Witz! - abgegeben und jedes My bewiesen hat, obwohl das aufgrund der Vorlesung alles klar war.)



  Profil  Quote  Link auf diesen Beitrag Link
PrinzessinEinhorn
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2017
Mitteilungen: 2217
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-09-22 22:45


Da stimme ich dir zu.
Ich glaube ich übertreibe es manchmal auch, wenn ich Beweise durcharbeite und dann der Meinung bin sämtliche Lücken füllen zu müssen.

An anderer Stelle habe ich dann oftmals das Gefühl, dass diese Vorgehensweise der mathematischen Intuition nicht dienlich ist.



  Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5161
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2019-09-22 23:02


2019-09-22 22:45 - PrinzessinEinhorn in Beitrag No. 5 schreibt:
1. Ich glaube ich übertreibe es manchmal auch, wenn ich Beweise durcharbeite und dann der Meinung bin sämtliche Lücken füllen zu müssen.

2. An anderer Stelle habe ich dann oftmals das Gefühl, dass diese Vorgehensweise der mathematischen Intuition nicht dienlich ist.

Zu 1: Natürlich musst du jede Lücke füllen! Wenn es für dich selbst nicht "trivial" ist, musst du es beweisen. (Das kann sehr sehr anstrengend sein!)

Zu 2: Das habe ich nicht ganz verstanden eek




  Profil  Quote  Link auf diesen Beitrag Link
PrinzessinEinhorn
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2017
Mitteilungen: 2217
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-09-23 09:39



Zu 1: Natürlich musst du jede Lücke füllen! Wenn es für dich selbst nicht "trivial" ist, musst du es beweisen. (Das kann sehr sehr anstrengend sein!)

Zu 2: Das habe ich nicht ganz verstanden

Ja, ich neige dann eben dazu auch die Dinge zu zeigen, die trivial sind.
Etwa so ganz einfache Mengenbeziehungen.
Und da denke ich mir dann, dass wenn ich sowas leichtes nicht immer wieder Haarfein beweisen würde, es sich mir doch eher als 'gegebene Wahrheit' einprägen würde und mir so dann viel eher automatisch in den Sinn kommt. Wenn du verstehst wie ich das meine.

Ist aber auch nicht so wichtig. :D



  Profil  Quote  Link auf diesen Beitrag Link
pram
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 21.09.2019
Mitteilungen: 9
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2019-09-23 11:01


Hallo zusammen,

vielen lieben Dank Euch für eure Beiträge! Sie alle haben mir enorm weitergeholfen!!



  Profil  Quote  Link auf diesen Beitrag Link
pram hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


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-2019 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]