Schwere Aufgabe mit Kombination

22.03.2005, 16:35

maths

Schwere Aufgabe mit Kombination

Könntet ihr mir bitte die folgende Aufgabe helfen?
Ich wäre sehr dankbar für eure Hilfe!! smile

Es gibt einen Kreis, n Buchstabe A und m Buchstabe b. Um den Kreis legen wir die Buchstaben A und B. Die Frage ist:
Wieviele Möglichkeiten gibt es um die Buchstaben A und B um den Kreis zu stellen?

mgf,
maths

22.03.2005, 17:23

yeti777

Auf diesen Beitrag antworten »

RE: Schwere Aufgabe mit Kombination
Hallo maths,

ich würde so denken: Du hast $\begin{eqnarray*} m+n \end{eqnarray*}$ Plätze, um die $\begin{eqnarray*} m \end{eqnarray*}$ A's und die $\begin{eqnarray*} n \end{eqnarray*}$ B's zu verteilen. Jetzt verteilst du zuerst die $\begin{eqnarray*} m \end{eqnarray*}$ A's. Dafür gibt es $\begin{eqnarray*} \begin{pmatrix} m+n \\ n \end{pmatrix} \end{eqnarray*}$ Möglichkeiten. Die restlichen Plätze werden von den $\begin{eqnarray*} n \end{eqnarray*}$ B's eingenommen. Wenn du mit den B's anfängst, erhältst du dasselbe Resultat, da ein Resultat aus der Kombinatorik lautet: $\begin{eqnarray*} \begin{pmatrix} m+n \\ n \end{pmatrix} = \begin{pmatrix} m+n \\ (m+n)-n \end{pmatrix} = \begin{pmatrix} m+n \\ m \end{pmatrix} \end{eqnarray*}$ .
(Wäre froh, wenn ein Stochastiker dieses Resultat überprüfen würde).

Gruss yeti

22.03.2005, 17:36

hummma

Auf diesen Beitrag antworten »

Also ich wuerds so berechnen. Des ist ein runder Tisch mit $\begin{eqnarray*} m+n \end{eqnarray*}$ gleichen Plaetzen. Es gibt $\begin{eqnarray*} (m+n-1)! \end{eqnarray*}$ Moeglichkeiten die As und Bs zu verteilen, dann sie aber unterscheidbar. Um die gleichen Kombinationen wegzubringen wuerd ich noch mal durch n!*m! Teilen. Also :

$\begin{eqnarray*} \frac{(m+n-1)!}{n!m!} \end{eqnarray*}$

Fuer die Stochastik gilt mein Komment allerdings nicht fröhlich

22.03.2005, 18:42

yeti777

Auf diesen Beitrag antworten »

Kombinatorik-Aufgabe
Hallo humma,

ich bin mir meines Resultats nicht sicher. Da muss ein Profi her.

Arthur, HILFE !!!!

Gruss yeti

22.03.2005, 18:47

Auf diesen Beitrag antworten »

RE: Kombinatorik-Aufgabe
@yeti777

Du hast die Hilfe gar nicht nötig - stimmt ja alles. Freude

Der runde Tisch bringt mich allerdings etwas ins Grübeln: Was ist, wenn Sitzordnungen nur dann als unterschiedlich gelten, wenn sie nicht durch Drehung des Tisches (um eine beliebige Anzahl Plätze) ineindander übergehen? Dann wird's etwas ekliger - aber warten wir mal ab, was der Fragesteller dazu meint.

EDIT: Ich seh grade, im Original war gar nicht von einem Tisch die Rede. Ohje, dann ist vielleicht doch die eben angesprochene ekligere Variante gemeint. Na, ich denk mal drüber nach, bis dann.

22.03.2005, 18:55

yeti777

Auf diesen Beitrag antworten »

RE: Kombinatorik-Aufgabe
Hallo Arthur!

Deine Zustimmung geht mir runter wie Honig, jawohl das geht sie smile

! Auch die für die Aufgabe mit dem Hypothesentest beim Münzwurf. Herzlichen Dank.

Mit der Drehung des Tisches will ich jetzt lieber nicht noch anfangen. Würde mir direkt das Erfolgserlebnis des Tages vermasseln.

Gruss Heinz

22.03.2005, 21:33

hummma

Auf diesen Beitrag antworten »

Ich hab noch mal nach geschaut und eine Aufgabe gefunden die denk ich im prinzip das gleiche ist:

Es werden 5 Herren und 4 Damen an einen runden Tisch gesetzt und es soll nur nach Herren und Damen unterschieden werden. Dann gibts:

$\begin{eqnarray*} \frac{8!}{5!*4!} \end{eqnarray*}$ Moeglichkeiten, weil von (9-1)! Moeglichkeiten 5! der Anordung der Maenner bzw 4! der Damen gleich sind.

22.03.2005, 21:47

Auf diesen Beitrag antworten »

Die Formel $\begin{eqnarray*} \frac{(m+n-1)!}{m!n!} \end{eqnarray*}$ - gleichgültig, für welche der oben diskutierten Interpretationsvarianten - kann schon allein deswegen nicht für alle m,n gelten, weil da manchmal etwas Nicht-Ganzzahliges rauskommt!!!

Bsp. m=2, n=2: $\begin{eqnarray*} \frac{(m+n-1)!}{m!n!}=\frac{3!}{2!2!}=1.5 \end{eqnarray*}$

EDIT: korrigiert, s.u.

22.03.2005, 21:57

hummma

Auf diesen Beitrag antworten »

1. chill mal

2. Auch wieder war. Es gibt aufjeden fall (n-1)! Moeglichkeiten n Personen an einen Runden Tisch zu setzen. Du stimmst mir aber zu dass das im Prinzip zwei gleiche Aufgaben sind. Warum stimmt beim einen dann die Loesung und beim andrern nicht?

3. Vieleicht faellts mir beim Schafkopfen was ein.

22.03.2005, 22:25

Auf diesen Beitrag antworten »

So, jetzt kommt zur Kombinatorik noch etwas Zahlentheorie hinzu:

1.) Die Formel von humma ist richtig, falls m und n teilerfremd sind. In diesem Fall kann man nämlich irgendeine Sitzordnung - wie z.B. AAABABBAB im Fall m=5,n=4 - durch Drehen um 1...(m+n-1) Positionen NICHT in sich selbst überführen. Somit kann man jeweils genau (m+n) der von yeti777 berechneten Varianten zu einer "nicht fixierten" Variante zusammenfassen, deren Gesamtanzahl dann natürlich die bereits erwähnte Formel

$\begin{eqnarray*} \frac{1}{m+n}{m+n \choose m}=\frac{(m+n-1)!}{m!n!} \end{eqnarray*}$

ergibt.

2.) Sind m und n dagegen nicht teilerfremd, dann sind für bestimmte Konstellationen solche Drehungen möglich, das Zusammenfassen von jeweils (m+n) Varianten klappt dann i.a. nicht mehr!

Beispiel für m=4,n=4: AABBAABB geht nach Drehung um 4 Positionen in sich selbst über.

In diesem Fall ist die Anzahlberechnung deutlich schwieriger (ich überblick's im Moment nicht) - jedenfalls ist der Wert $\begin{eqnarray*} \frac{(m+n-1)!}{m!n!} \end{eqnarray*}$ hier nur als eine (nicht scharfe) untere Schranke zu gebrauchen.

22.03.2005, 22:37

maths

Auf diesen Beitrag antworten »

Vielen Dank für eure Hilfe!

Ich habe auch die Formel wie bei humma gefunden:
(m+n)!/(n!*m!*(m+n))

Aber wie Athur gesagt hat, es geht nur mit dem Fall, dass m und n teilerfremd sind unglücklich

hat jemand noch eine Idee?

Vielen Dank vielmalsssssssssssssssssssssss

mfg,
maths

23.03.2005, 08:20

Egal

Auf diesen Beitrag antworten »

Also für mich sieht das so aus als wenn die Permutationen die Ordnung teilen müsste. Erste Diagnose die Anzahl der möglichen Permuationen ist $\begin{eqnarray*} ggt(\tau([A]),\tau([B]) \end{eqnarray*}$

23.03.2005, 09:18

Auf diesen Beitrag antworten »

@egal

Etwas ausführlicher wäre nicht schlecht: Von welchen Permutationen sprichst du hier (da gibt es hier mehrere Deutungsmöglichkeiten), und was ist dieses $\begin{eqnarray*} \tau \end{eqnarray*}$ ? verwirrt

Bin leider nur eine normalsterblicher Mathematiker und kann daher deine Gedankengänge nicht nachvollziehen.

23.03.2005, 11:00

Frooke

Auf diesen Beitrag antworten »

Hy! Nur zwei kleine Sachen:
1. Will das nicht jemand nach «Stochastik» verschieben?

2. Yetis Formel stimmt ja so. Wenn man nun «echt» unterschiedliche Kombinationen haben will, so muss man doch einfach die Möglichkeit der Vertauschung der A's und B's «herausdividieren». Im Sinne von humma also:

$\begin{eqnarray*} \frac{\begin{pmatrix} m+n \\ n \end{pmatrix}}{n!m!} \end{eqnarray*}$

Oder was kommt dabei heraus?

Und Egals Ausführung ist mir auch unklar verwirrt

EDIT: Sorry, stimmt wohl überhaupt nicht, was ich da labere, das gibt nämlich - wenn ich mich nicht verrechnet habe -
$\begin{eqnarray*} \frac{(m+n)!}{(n!)^2(m!)^2} \end{eqnarray*}$
Argh! Kann ja wohl übrhaupt nicht sein... unglücklich

Nun ja, diesen Post bitte ignorieren...

23.03.2005, 14:59

Auf diesen Beitrag antworten »

Zitat:

Original von Frooke
1. Will das nicht jemand nach «Stochastik» verschieben?

Zu Analysis gehört es nicht, stimmt schon. Aber ich würde die Kombinatorik auch nicht als Teilgebiet der Stochastik ansehen, nur weil vielleicht in der Schule dieser Eindruck verbreitet wird.

----------------

Zurück zum Thema:

Ich denke, ich habe jetzt eine Formel für die Anzahl U(m,n) der unfixierten Konfigurationen im allgemeinen Fall gefunden:

$\begin{eqnarray*} U(m,n)=\frac{1}{m+n}\sum\limits_{\substack{t\geq 1:\\ t\mid\mathrm{ggT}(m,n)}}\varphi(t)\cdot F\left(\frac{m}{t},\frac{n}{t}\right) \end{eqnarray*}$

mit $\begin{eqnarray*} F(m,n)={m+n \choose m} \end{eqnarray*}$ und der Eulerschen $\begin{eqnarray*} \varphi \end{eqnarray*}$ -Funktion.

Bei Interesse am Beweis, bitte melden. Da muss ich dann erstmal noch sehen, wie ich den noch vereinfachen kann - in der gegenwärtigen Form ist er für Außenstehende unerträglich.

23.03.2005, 17:21

maths

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
$\begin{eqnarray*} U(m,n)=\frac{1}{m+n}\sum\limits_{\substack{t\geq 1:\\ t\mid\mathrm{ggT}(m,n)}}\varphi(t)\cdot F\left(\frac{m}{t},\frac{n}{t}\right) \end{eqnarray*}$

mit $\begin{eqnarray*} F(m,n)={m+n \choose m} \end{eqnarray*}$ und der Eulerschen $\begin{eqnarray*} \varphi \end{eqnarray*}$ -Funktion.

Bei Interesse am Beweis, bitte melden. Da muss ich dann erstmal noch sehen, wie ich den noch vereinfachen kann - in der gegenwärtigen Form ist er für Außenstehende unerträglich.

Ich habe für den Fall U(2,2) gerechnet und bekomme die Ergebnisse:
14/4 unglücklich

Ich habe gerechnet wie folgende:

$\begin{eqnarray*} 1/4*[ 1 * (4!/2!) + 1* (2!/1!)]= 14/4 \end{eqnarray*}$

Arthur Dent, könntest du mir bitte genauer erklären?
Ich danke dir vielmalsss!

mgf,
maths

23.03.2005, 18:08

Auf diesen Beitrag antworten »

Zitat:

Original von maths
Ich habe für den Fall U(2,2) gerechnet und bekomme die Ergebnisse:
14/4 unglücklich

Ich habe gerechnet wie folgende:

$\begin{eqnarray*} 1/4*[ 1 * (4!/2!) + 1* (2!/1!)]= 14/4 \end{eqnarray*}$

Man muss natürlich richtig in den Binomialkoeffizienten einsetzen:

$\begin{eqnarray*} 1/4*[ 1 * (4!/(2!2!)) + 1* (2!/(1!1!))]= 8/4 = 2 \end{eqnarray*}$ Augenzwinkern

23.03.2005, 18:25

Leopold

Auf diesen Beitrag antworten »

In einem Mathematikbuch für einen Grundkurs fand sich die folgende Aufgabe:

Vier Engländer, vier Franzosen und vier Deutsche, von denen jeder nur seine Muttersprache beherrscht, setzen sich auf gut Glück um einen runden Tisch. Wie groß ist die Wahrscheinlichkeit, daß sich mindestens eine Person mit einem ihrer Nachbarn unterhalten kann?

In späteren Ausgaben dieses Buches war die Aufgabe nicht mehr vorhanden. Weiß jemand warum? Augenzwinkern

EDIT
Ich habe als Lösung 5641/5775.

23.03.2005, 19:25

Frooke

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent

Zitat:

Original von Frooke
1. Will das nicht jemand nach «Stochastik» verschieben?

Zu Analysis gehört es nicht, stimmt schon. Aber ich würde die Kombinatorik auch nicht als Teilgebiet der Stochastik ansehen, nur weil vielleicht in der Schule dieser Eindruck verbreitet wird.

Hmm… In meinem Stochastikbuch wird die Kombinatorik aber auch behandelt… Wozu zählt es denn???

23.03.2005, 19:50

Auf diesen Beitrag antworten »

Zitat:

Original von Frooke
Hmm… In meinem Stochastikbuch wird die Kombinatorik aber auch behandelt… Wozu zählt es denn???

Die Wikipedia und auch ich zählen sie zur Diskreten Mathematik, dafür gibt es hier im Board allerdings keine eigene Rubrik. Dass die Kombinatorik in deinem Stochastikbuch auch behandelt wird, spricht ja nicht dagegen. Auch Maßtheorie, die eigentlich der Analysis zugeordnet werden muss, wird häufig in Stochastikbüchern behandelt, aus verständlichen Gründen.

Ist alles nicht so eng zu sehen: Der Bronstein z.B. ordnet die Kombinatorik ins Kapitel "Elementarmathematik" ein. Nun ja... Augenzwinkern

23.03.2005, 20:43

Frooke

Auf diesen Beitrag antworten »

Wie indiskret von mir, sie zur Stochastik zu zählen Big Laugh

Danke für die Antwort Freude

23.03.2005, 20:52

Mathespezialschüler

Auf diesen Beitrag antworten »

Verschoben

23.03.2005, 20:59

Auf diesen Beitrag antworten »

Eine bodenlose Frechheit dieses Verschieben, und das nach meinem Beitrag oben! Big Laugh

Vielleicht sollte man die Rubrik überhaupt in Kombinatorik / Stochastik umbenennen, ist ja sowieso mehr Kombinatorik hier vertreten als "echte" Stochastik (was auch immer das ist).

23.03.2005, 22:12

Frooke

Auf diesen Beitrag antworten »

tacuissem...

Hätte ich doch bloss meine Klappe gehalten...

Sorry Arthur Gott

22.03.2006, 22:09

philinne

Auf diesen Beitrag antworten »

Vier Engländer, vier Franzosen und vier Deutsche, von denen jeder nur seine Muttersprache beherrscht, setzen sich auf gut Glück um einen runden Tisch.

Wieviele Möglichkeiten gibt es diese zu verteilen, so dass sie sich in Gruppen immernoch befinden und keiner irgendwo getrennt sitzt ?
Also keine Wahrscheinlichkeitsberechnung, sondern nur Möglichkeiten

23.03.2006, 22:34

Auf diesen Beitrag antworten »

"In Gruppen" ist etwas missverständlich: Sollen alle vier eines Landes nebeneinander sitzen? Oder reicht es, immer mindestens zwei? Letzteres könnte man in Anlehnung an Leopolds Aufgabe auch so formulieren:

Wie groß ist die Wahrscheinlichkeit, daß sich jede Person mit mindestens einem ihrer Nachbarn unterhalten kann?

Neue Frage »

Antworten »

Schwere Aufgabe mit Kombination

Verwandte Themen