Kombinatorik < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Wir betrachten Wörter der Länge n, die aus den 26 Buchstaben des Alphabets
bestehen. Wie viele
a) beliebige solche Wörter,
b) Wörter mit (auch sich wiederholenden) Buchstaben in lexikographischer
(alphabetischer) Reihenfolge,
c) Wörter ohne mehrfach vorkommende Buchstaben in lexikographischer
Reihenfolge,
d) Wörter ohne mehrfach vorkommende Buchstaben in beliebiger Reihenfolge
gibt es? |
Hallo, habe wieder mal eine schöne Aufgabe aus dem Kombinatorikbereich.
mein Ansatz:
[mm] a)\pmat{ n +26 & -1 \\ 26 } ->\pmat{ n +k & -1 \\ k }
[/mm]
[mm] b)n^{26} ->n^k
[/mm]
[mm] c)\bruch{n!}{(n-26)!} ->\bruch{n!}{(n-k)!}
[/mm]
[mm] d)\vektor{n \\ 26} [/mm] -> [mm] \vektor{n \\ k} [/mm] Binomialkoeffizient
sind die Formeln richtig?
gruß Alex
|
|
| |
|
Hallo Alex,
das Leben ist auch außerhalb der Kombinatorik schön. Hast Du heute schon etwas anderes gemacht? 
Die Lösungen sehen für mich alle falsch aus. Lösung b) trifft m.E. für Aufgabe a) zu. Aber vielleicht kannst Du Deine Lösungen ja begründen? Dann ist es leichter zu sehen, wo es stimmt und wo nicht.
Zu c) und d) bedenke, dass hier [mm] n\le{26} [/mm] vorausgesetzt ist. Schon daher können Deine Ansätze nicht stimmen.
lg
reverend
|
|
|
| |
|
Guten Morgen, danke für die Antwort!
Für mich gibt es nichts schöneres als Kombinatorik
Also die Formeln ( vier Grundaufgaben der Kombinatorik) habe ich alle einfach nach Definitionen ausgesucht z.B
$ [mm] a)\pmat{ n +26 & -1 \\ 26 } ->\pmat{ n +k & -1 \\ k } [/mm] $ weil Definition nach (ungeordnet mit zurücklegen) = belibig solche wörter
$ [mm] b)n^{26} ->n^k [/mm] $ -> geordnet mit zurücklegen = (auch sich wiederholenden) Buchstaben in lexikographischer (alphabetischer) Reihenfolge,
$ [mm] c)\bruch{n!}{(n-26)!} ->\bruch{n!}{(n-k)!} [/mm] $ geordnet ohne zurücklegen = ohne mehrfach vorkommende Buchstaben in lexikographischer Reihenfolge
$ [mm] d)\vektor{n \\ 26} [/mm] $ -> $ [mm] \vektor{n \\ k} [/mm] $ ungeordnet ohne zurücklegen = Wörter ohne mehrfach vorkommende Buchstaben in beliebiger Reihenfolge
aber so einfach geht das wohl nicht.
Ok für a) [mm] n^k [/mm] also z.B [mm] 26^1=26 [/mm] (Wort mit einem Buchstaben) Möglihkeiten, mit [mm] 26^2 [/mm] (Wort mit zwei Buchstaben) gibt es 676 Möglichkeiten u.s.w
b)26*n! weil die alphabetischer Reihenfolge eingehalten werden muss.
soweit richtig?
gruß Alex
|
|
|
| |
|
Hallo Alex,
ich kann Deinen Begründungen zwar folgen, aber in den meisten hast Du n und k nicht richtig eingesetzt. Gemeinerweise kommt ja auch eine Variable n in der Aufgabenstellung vor, und das führt gern zu Verwirrung. Denn es gibt keinen Zusammenhang zwischen diesen beiden n's. Um Verwechslung zu vermeiden, ist es dann geschickt, die Variable in der Aufgabe umzubenennen, sagen wir in "m". Alle vorkommenden Wörter sind also ab jetzt m Buchstaben lang.
> Für mich gibt es nichts schöneres als Kombinatorik
Für mich schon, obwohl ich Kombinatorik durchaus mag.
Sie dürfte auf meiner Hitliste schöner Dinge im Leben weit vorne stehen, etwa auf Platz 33. Ernst gemeint.
[...]
> aber so einfach geht das wohl nicht.
Definitionen sind gut, aber ihre Anwendung nicht immer einfach. 
> Ok für a) [mm]n^k[/mm] also z.B [mm]26^1=26[/mm] (Wort mit einem Buchstaben)
> Möglihkeiten, mit [mm]26^2[/mm] (Wort mit zwei Buchstaben) gibt es
> 676 Möglichkeiten u.s.w
Genau. Die Lösung ist also [mm] 26^n.
[/mm]
> b)26*n! weil die alphabetischer Reihenfolge eingehalten
> werden muss.
Na, versuchen wirs mal für Wörter mit drei Buchstaben Länge.
1. Möglichkeit: drei verschiedene Buchstaben: 26*25*24, allerdings jede Kombination sechsmal gezählt, obwohl die Anordnung doch eindeutig ist. Ach ja, hier wird die allgemeine Lösung [mm] \vektor{26\\m} [/mm] sein, hier also [mm] \vektor{26\\3}=2600
[/mm]
2. Möglichkeit: drei gleiche Buchstaben: 26 Möglichkeiten, unabhängig von m.
3. Möglichkeit: zwei gleiche Buchstaben: 26*26 Möglichkeiten, keine Vervielfachung wg. Anordnung, da lexikalisch geordnet.
Zusammen also [mm]2600+26+26*26=26(100+26+1)=3302[/mm]
Die ersten beiden Möglichkeiten sind für m Buchstaben mit [mm] m\le{26} [/mm] leicht zu bestimmen, aber die 3. wird der schwierige Zweig. Bei m=4 werden hier ja schon die Möglichkeiten "drei gleiche", "zweimal zwei gleiche" und "zwei gleiche und zwei verschiedene" zu berücksichtigen sein.
Das kannst Du nun rekursiv untersuchen oder als Unteraufgabe nehmen:
| Aufgabe | | Aus den 26 Buchstaben des Alphabets werde ein Wort der Länge [mm] m\ge{3} [/mm] so gebildet, dass mindestens zwei gleiche Buchstaben darin vorkommen, aber nicht alle Buchstaben gleich sind. Das Wort sei lexikalisch angeordnet. Wieviele solche Wörter gibt es? |
1. Tipp: hypergeometrische Verteilung
2. Tipp: 3302=26*127 ist ein guter Hinweis, dass eine einfache Multiplikation von Fakultäten und Potenzen nicht genügen wird. 127 ist nämlich prim.
> soweit richtig?
>
> gruß Alex
lg
reverend
|
|
|
| |
|
> Für mich schon, obwohl ich Kombinatorik durchaus mag.
> Sie dürfte auf meiner Hitliste schöner Dinge im Leben
> weit vorne stehen, etwa auf Platz 33. Ernst gemeint.
Mit deinen Kenntnissen über die Wahrscheinlichkeit könntest du im Casino was dazu verdienen Und es ist doch so, dass man im Leben die Dinge mag, die man gut kann ich aber komme trotz der ausführlichen Antwort leider nicht viel weiter.
Also über die hypergeometrische Verteilung hatten wir leider noch nichts in der Vorlesung aber ist die nicht dafür da um Wahrscheinlichkeit zuberechnen, oder kann man damit auch Möglichkeiten ausrechnen?
Ich kann leider kein Logarithmus finden mit dem ich die Formel erstellen kann: also nach deiner Erklährung ist das mir jetzt klar mit wie man die Möglichkeiten für ein Wort mit bis zu 3 Buchstaben berechnet für 4 würde ich folgende Formel anwenden:
[mm] \vektor{26 \\ 4} [/mm] (4 versch. Buchst.) + 26 (4 gleiche Buchst.) + [mm] 26^2 [/mm] (2*2 gleiche Buchst.) + [mm] 26\vektor{26 \\ 2} [/mm] (2 gleiche und 2 versch. Buchstaben)
ich glaube die ist aber auch nicht ganz richtig.
gruß Alex
|
|
|
| |
|
Hallo Alex,
eigenartig, dass sonst niemand auf die Aufgabe "anspringt".
> Mit deinen Kenntnissen über die Wahrscheinlichkeit
> könntest du im Casino was dazu verdienen
Ich weiß gar nicht so viel, aber genug, um mich von jedem Casino fernzuhalten. Da kann man nämlich nichts dazu verdienen. So sind Spielbanken ja gerade konzipiert, von Leuten, die viel mehr über Kombinatorik und Wahrscheinlichkeiten wissen als ich.
> Und es ist
> doch so, dass man im Leben die Dinge mag, die man gut kann
> ich aber komme trotz der ausführlichen Antwort leider
> nicht viel weiter.
Ja, durchaus. Und ein paar Dinge mag man auch, die man gern besser können würde...
> Also über die hypergeometrische Verteilung hatten wir
> leider noch nichts in der Vorlesung aber ist die nicht
> dafür da um Wahrscheinlichkeit zuberechnen, oder kann man
> damit auch Möglichkeiten ausrechnen?
Ja, man kann. Es hilft einem hier aber auch nicht so viel weiter, dass ich einen stringenten Lösungsweg sehen würde. Höchstens einen alternativen.
> Ich kann leider kein Logarithmus finden mit dem ich die
> Formel erstellen kann: also nach deiner Erklährung ist das
> mir jetzt klar mit wie man die Möglichkeiten für ein Wort
> mit bis zu 3 Buchstaben berechnet für 4 würde ich
> folgende Formel anwenden:
>
> [mm]\vektor{26 \\ 4}[/mm] (4 versch. Buchst.) + 26 (4 gleiche
> Buchst.) + [mm]26^2[/mm] (2*2 gleiche Buchst.) + [mm]26\vektor{26 \\ 2}[/mm]
> (2 gleiche und 2 versch. Buchstaben)
>
> ich glaube die ist aber auch nicht ganz richtig.
In der Tat:
> [mm]\vektor{26 \\ 4}[/mm] (4 versch. Buchst.)
![[ok]](/images/smileys/ok.gif "[ok]")
> [mm]+26[/mm] (4 gleiche Buchst.)
> [mm]+26^2[/mm] (2*2 gleiche Buchst.)
![[notok]](/images/smileys/notok.gif "[notok]")
Da fehlen noch die Anordnungsmöglichkeiten unter Berücksichtigung der Symmetrie oder Austauschbarkeit, außerdem sollte da nur 26*25 stehen, wenn nicht nur die Hälfte (das hängt vom Rest der Betrachtung ab). Ich komme auf insgesamt 3*26*25=1950 mögliche Wörter dieses Typs.
> [mm]+26\vektor{26 \\ 2}[/mm] (2 gleiche und 2 versch. Buchstaben)
Auch hier fehlen die Anordnungsmöglichkeiten, deren es für jede der berechneten Buchstabenkombinationen 12 gibt, die sich aus [mm] \vektor{4 \\ 2}*\vektor{2 \\ 1} [/mm] berechnen. Insgesamt also [mm] 26*\vektor{26 \\ 2}*12
[/mm]
Außerdem fehlt noch die Variante "drei gleiche Buchstaben und ein anderer", für die es gerade $ 26*26*4=2704 $ Möglichkeiten gibt.
Zählen wir doch mal zusammen:
[mm] \vektor{26 \\ 4}+26+3*26*25+26*\vektor{26 \\ 2}*12+26*26*4=\bruch{26*25*24*23}{1*2*3*4}+26+26*3*25+26*\bruch{26*25}{1*2}*12+26*26*4=26*(25*23+1+3*25+13*25*12+26*4)=26*4655=121030
[/mm]
Hmmm. Immer noch nicht sehr hilfreich. [mm] 4655=5*7^2*19. [/mm] Das hilft ja noch nicht weiter.
Ich kann mir ehrlich gesagt nicht vorstellen, dass der Schwierigkeitsgrad dieses Aufgabenteils angemessen ist.
Die Lösung für ein Wort der Länge n aus einem Satz von m Buchstaben (mit beliebiger Wiederholung, aber lexikalisch angeordnet) und [mm] n\le{m} [/mm] ist allgemein
[mm] \summe_{i=0}^{n-1}\vektor{n-1 \\ i}\bruch{m!}{(m-i-1)!}=\summe_{i=1}^{n}\vektor{n-1 \\ i-1}\bruch{m!}{(m-i)!}
[/mm]
und nicht so schwer herzuleiten: man betrachte die Zahl der Möglichkeiten, das Wort in Summanden aufzuspalten. Eine Vereinfachung sehe ich aber nicht, und der Schwierigkeitsgrad der Lösung entspricht keineswegs den Voraussetzungen der anderen drei Aufgabenteile.
Falls jemand einen anderen Ansatz sieht oder aber eine rekursive Darstellung oder andere Vereinfachung sieht, wäre ich dankbar. Ich weiß hier sonst nicht mehr weiter.
> gruß Alex
lg
rev
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:06 Sa 12.12.2009 | | Autor: | capablanca |
Hallo reverend, danke für die Hilfe bei den Kombinatorik Aufgaben, hat mir echt geholfen!
Am kommenden donnerstag bekomme ich die Lösungen zu diesen Aufgaben, mal schauen welchen Ansatz unser Profesor für die Aufgabe verwendet, ich werde (wenn Interesse besteht?) auf jeden Fall noch seine Lösung und sein Ansatz hier mitteilen.
gruß Alex
|
|
|
|
