Kodierung

15.11.2015, 15:29	Boom	Auf diesen Beitrag antworten »
Kodierung Hallo, ich hänge gerade bei einer Aufgabe zur Kombinatorik... "a) Wie viele verschiedene Anordnungen ohne Wiederholungen von n Symbolen gibt es? Man wähle als Symbol für die Elemente zum Beispiel Buchstaben aus dem Alphabet oder die ersten Zahlen von 0 bis n-1, falls n<25 oder n<=10 und beginne mit n=1, dann 2, dann 3 und finde das Bildungsgesetz mit Hilfe des Prinzips der vollständigen Induktion! Hinweis: n=2 es nur ab und ba, n=3 es gibt acb, bac, bca, cab, cba. b) Wie in a), seinen n Symbole gegeben. Definition: Ein Wort der Länge k besteht aus k Symbolen (mit Wiederholungen), k aus $\begin{eqnarray} \mathbb N \end{eqnarray}$ . Wie viele verschiedene Wörter gibt es für ein gegebenes k?" Mein Problem fängt schon bei a) an. Wie groß ist k?! Ist es richtig, dass n ein Mal kleiner als 25 (als 24) ist und ein Mal 10?!
15.11.2015, 19:39	Dopap	Auf diesen Beitrag antworten »
es gibt auch noch als sechste Permutation "abc" Aber was ist jetzt eigentlich deine Frage
15.11.2015, 19:58	Boom	Auf diesen Beitrag antworten »
Die habe ich wohl einfach vergessen einzutragen, Entschuldigung! Die grundsätzliche Frage bei a lautet "Wie viele verschiedene Anordnungen ohne Wiederholungen von n Symbolen gibt es?" Allerdings verstehe ich diese Aufgabe nicht, weil dann doch auch gegeben sein müsste wie groß k ist, oder? ...oder habe ich die Aufgabe ganz falsch verstanden und ich soll nur durch vollständige Induktion die Gesetzmäßigkeit dafür bilden?
15.11.2015, 20:42	Bjoern1982	Auf diesen Beitrag antworten »
Das sind im Endeffekt nur ganz klassiche Abzählformeln (sogar die einfachsten davon), die du durch einfaches Googeln eigentlich schon längst hättest finden können. Bei a) geht es um die Formel für die Anzahl der Möglichkeiten mit Beachtung der Reihenfolge OHNE Wiederholung, wobei hier KEIN Auswahlproblem vorliegt, sondern es einfach um n feste Symbole geht, die es gilt anzuordnen. Bei b) hingegen geht es um ein so genanntes Auswahlproblem (man wählt aus n Symbolen k Symbole für ein Wort aus), wobei die Reihenfolge ebenso eine Rolle spielt und zudem dieses Mal Wiederholungen erlaubt sind. Schau mal, was du dazu findest. Eigentlich braucht man die Formeln auch gar nicht, denn diese Dinge folgen auch aus dem allgemeinen Zählprinzip (Produktregel), siehe z.B. hier: https://www.stark-verlag.de/upload_file/Muster/940091m1.pdf
16.11.2015, 06:35	Boom	Auf diesen Beitrag antworten »
Ach so! Ich dachte die ganze Zeit ich hätte bei a) eine Kombination ohne Wiederholungen. Davon bin ich ausgegangen, weil ich dachte, dass die Reihenfolge nicht beachtet wird...das ist ja aber falsch! So brauche ich also auch kein k Wenn die Reihenfolge beachtet wird sollte die "Formel" n! bzw. n(n-1)(n-2)...1=n! sein. Wie soll ich so etwas denn mit einer vollständigen Induktion herleiten? Eigentlich ist das hier: n(n-1)(n-2)...1=n! doch schon die Herleitung.
16.11.2015, 10:13	Dopap	Auf diesen Beitrag antworten »
ja, das könnte man meinen, weil es offensichtlich (trivial ) ist. Trotzdem enthält die Aussage eine Variable und muss erst bewiesen werden. Und das ist gerade bei so einfachen Dingen gar nicht so einfach ------------------------------------------------------ n Elemente lassen sich auf $\begin{eqnarray} n! = n\cdot(n-1)\cdots (2)\cdot 1 \end{eqnarray}$ Arten permutieren. 2 Elemente haben 2 Permutationen. Ein neues Element kann man in jede Permutation an (n+1) Positionen einfügen. ( (n-1) Lücken + Anfang + Ende = (n+1)). Also gibt es $\begin{eqnarray} n!(n+1) \end{eqnarray}$ Permutationen für (n+1) Elemente. Und mit Induktionsvoraussetzung folgt: $\begin{eqnarray} n!\cdot(n+1) = \underbrace {n\cdot(n-1)\cdots (2)\cdot 1}_{=n!}\cdot (n+1)=(n+1)! \end{eqnarray}$ was aber die Aussage für (n+1) Elemente ist.
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »