www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Kombinatorik" - Kombinatorik
Kombinatorik < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Kombinatorik: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:40 Di 08.12.2009
Autor: capablanca

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

        
Bezug
Kombinatorik: Antwort
Status: (Antwort) fertig Status 
Datum: 22:33 Di 08.12.2009
Autor: reverend

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

Bezug
                
Bezug
Kombinatorik: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 08:13 Mi 09.12.2009
Autor: capablanca

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

Bezug
                        
Bezug
Kombinatorik: Aufgaben a und b
Status: (Antwort) fertig Status 
Datum: 10:05 Mi 09.12.2009
Autor: reverend

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

Bezug
                                
Bezug
Kombinatorik: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:57 Mi 09.12.2009
Autor: capablanca


> 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




Bezug
                                        
Bezug
Kombinatorik: Weiß wer einen anderen Ansatz?
Status: (Antwort) fertig Status 
Datum: 00:10 Do 10.12.2009
Autor: reverend

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]

> [mm]+26[/mm] (4 gleiche Buchst.)

[ok]

> [mm]+26^2[/mm] (2*2 gleiche Buchst.)

[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)

[notok]
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

Bezug
                                                
Bezug
Kombinatorik: Lösung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Kombinatorik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]