6mal Würfeln. - Seite 2

16.07.2010, 15:35

Zitat:

Original von mathchild
Menge der N-Tupel bei denen genau drei Zahlen übereinstimmen???

Darum geht es in der Aufgabe nicht: Es geht um die Tupel, die aus genau 3 verschiedenen Zahlen bestehen. Wie oft dann jede dieser 3 Zahlen im Tupel auftaucht, ist völlig irrelevant - nun gut, mindestens einmal sollte es natürlich jeweils sein.

Ist schon ziemlich traurig, dass dir das bis jetzt nicht klar ist. unglücklich

16.07.2010, 15:44

mathchild

Auf diesen Beitrag antworten »

Zitat:

Wie hoch ist die Wahrscheinlichkeit, dass a) 1 Zahl b) 2 Zahlen c) 3 Zahlen d) 4 Zahlen e) 5 Zahlen f) 6 Zahlen erscheinen?

Das habe ich tatsächlich falsch interpretiert, dahingehend dass 1, 2 ... 6 gleiche Zahlen erwartet werden.

Tut mir leid, wenn ich euch damit unnötig belastet habe.

16.07.2010, 16:13

Auf diesen Beitrag antworten »

Ich würde dir wirklich mal dringend raten, die Beiträge gründlicher zu lesen. Selbst wenn du die Aufgabenstellung anders aufgefasst hast, so habe ich doch bereits am 12.07.2010, 21:40 unmissverständlich geschrieben:

Zitat:

Original von Arthur Dent
Frage: Wie groß ist die Wahrscheinlichkeit $\begin{eqnarray*} p_m \end{eqnarray*}$ , dass genau $\begin{eqnarray*} m \end{eqnarray*}$ verschiedene Zahlen in der Wurffolge auftauchen?

Da bleibt kein Spielraum für Ausreden. unglücklich

16.07.2010, 19:32

mathchild

Auf diesen Beitrag antworten »

Nachdem auch ich jetzt die Aufgabe verstanden habe, will ich mal alles zusammentragen, was ich bisher gelernt habe:

Wir führen $\begin{eqnarray*} N \end{eqnarray*}$ Würfe aus, mit einem Würfel, der $\begin{eqnarray*} n \end{eqnarray*}$ gleichberechtigte Seiten aufweist.

Gesucht ist die Wahrscheinlichkeit $\begin{eqnarray*} p_m \end{eqnarray*}$ , dass genau $\begin{eqnarray*} m \end{eqnarray*}$ verschiedene Zahlen in der Wurffolge auftauchen.

Behauptung:

$\begin{eqnarray*} p_m = \frac{1}{n^N}\cdot \binom{n}{m} \cdot \sum_{k=1}^m (-1)^{m-k} \cdot \binom{m}{k} \cdot k^N \end{eqnarray*}$ für $\begin{eqnarray*} 1\leq m\leq n \end{eqnarray*}$

Beweis:

Sei $\begin{eqnarray*} G_m \end{eqnarray*}$ die Menge der N-tupel, die genau m bestimmte Zahlen enthalten, o. B. d. A. die Zahlen 1, ..., m.

Dann ist

$\begin{eqnarray*} p_m = \frac{1}{n^N}\cdot \binom{n}{m} \cdot |G_m| \end{eqnarray*}$ für $\begin{eqnarray*} 1\leq m\leq n \end{eqnarray*}$

Bleibt also noch $\begin{eqnarray*} |G_m| \end{eqnarray*}$ zu berechnen.

$\begin{eqnarray*} H_m \end{eqnarray*}$ sei die Menge der N-tupel, die höchstens die vorgegebenen m Zahlen enthalten. Dann gilt:

$\begin{eqnarray*} G_m=H_m- \bigcup_{i=1}^m H_{m-1,i} \end{eqnarray*}$ <-- ich hab zwar eine Ahnung, aber richtig verstehe ich das leider nicht!

und

$\begin{eqnarray*} \left |G_m \right |= \left | H_m \right |- \left | \bigcup_{i=1}^m H_{m-1,i}\right | \end{eqnarray*}$

Dabei sind $\begin{eqnarray*} H_{m-1,i} \end{eqnarray*}$ die Teilmengen von $\begin{eqnarray*} H_m \end{eqnarray*}$ , die die Zahl i nicht enthalten.

Es ist

$\begin{eqnarray*} |H_{m}| = m^N \end{eqnarray*}$

Außerdem ist

$\begin{eqnarray*} |H_{m-1,i}|=|H_{m-1}|= (m-1)^N \end{eqnarray*}$

Und jetzt würde ich ganz naiv versuchen die Siebformel anzuwenden:

$\begin{eqnarray*} \left |G_m \right |= \left | H_m \right |- \left | \bigcup_{i=1}^m H_{m-1,i}\right | \end{eqnarray*}$

$\begin{eqnarray*} = m^N - \sum_{k=1}^m (-1)^{k-1} \cdot {(k-1)}^N \end{eqnarray*}$

Bin ich noch auf dem richtigen Dampfer? Das passt irgendwie nicht mehr zur obigen Behauptung!

Und wie wird die Gleichung bewiesen, die ich nicht nachvollziehen kann?

16.07.2010, 20:26

mathchild

Auf diesen Beitrag antworten »

Ich sehe schon, das mit der Siebformel habe ich vollkommen falsch angewandt. Man muss ja erst noch die Sache mit den Durchschnitten bilden. Leider kann ich meinen Beitrag nicht mehr ändern!

17.07.2010, 10:47

Huggy

Auf diesen Beitrag antworten »

@ mathchild
Ich habe gezögert, noch einmal auf deine Fragen einzugehen, weil ich den Eindruck habe, dass du zwar an dem Thema interessiert bist, aber dass du nicht bereit bist, genügend Arbeit und Zeit zu investieren, wie dazu einfach notwendig ist. Mathematische Texte kann man nicht lesen wie die Tageszeitung. Man muss sich über jeden Satz, ja jedes Wort, jede Formel Gedanken machen. Man muss sich Beispiele machen, diese noch mal mit den Erklärungen vergleichen, eventuell korrigieren, noch mal vergleichen, etc. Wenn du das gemacht hättest, hätten die Miss- und Unverständnisse, die Arthur dann aufgeklärt hat, gar nicht entstehen können. Mathematik ist nun mal zu über 90 % Transpiration und nur der kleine Rest ist Inspiration.

Es war und ist nicht meine Absicht, einen vollständigen und formalen Beweis der Siebformel und der daraus resultierenden Arthur-Formel zu geben. Ich wollte den Weg der Entstehung so verständlich machen, dass man zum Schluss auch ohne Beweis überzeugt ist, da muss zwangsläufig genau das herauskommen, was Arthur als Formel hingeschrieben hat. Diese Art von Verständnis ist aus meiner Sicht mindestens so wichtig und nützlich, wie der Beweis selbst.

Um dieses Ziel zu erreichen, ist notwendig:

(1) Die Ausgangsformel

Zitat:

$\begin{eqnarray*} \left |G_m \right |= \left | H_m \right |- \left | \bigcup_{i=1}^m H_{m-1,i}\right | \end{eqnarray*}$

Dabei sind $\begin{eqnarray*} H_{m-1,i} \end{eqnarray*}$ die Teilmengen von $\begin{eqnarray*} H_m \end{eqnarray*}$ , die die Zahl i nicht enthalten.

zu verstehen. Was bedeuten die Mengen und weshalb ist die Formel richtig? Wenn du die Erläuterungen sorgfältig liest und dir Beispiele machst, solte dir das gelingen. Wenn es dir nicht gelingt, solltest du dich mit dem Gedanken vertraut machen, dass du für dieses Thema noch nicht bereit bist.

(2) Man muss den Reduktionsprozess für die Vereinigunsmengen verstehen. Zu Anfang hat man eine Vereinigungsmenge aus m Mengen. Nach dem ersten Reduktionsschritt hat man 2 Vereinigungsmengen aus m - 1 Mengen. Auch das muss man sich im Detail und an Beispielen klar machen. In meinen bisherigen Erläuterungein fehlt dabei noch der Schritt, den Schnitt einer Menge mit einer Vereinigungsmenge mit dem Distributivgesetz in eine Vereinigung von Schnittmengen umzuformen.

(3) Man muss das Verfahren für kleine m explizit und vollständig durchführen. m = 2 ist trivial. m =2, 3, 4 geht problemlos. m = 5 bewältigt man zur Not auch noch. Danach hat man die Arthur-Formel für diese m bewiesen und dabei gesehen, wie sie zu Stande kommt. Und danach sollte einem klar sein, dass die Formel für beliebiges m genau so aussehen muss, wie sie aussieht, obwohl das kein Beweis ist.

Der vollständige und formale Beweis für beliebiges m, welcher natürlich ein Induktionsbeweis ist, beginnt mit der Schwierigkeit, die dabei auftretenden Mengen zu indizieren. Wenn man sich z. B. den Artikel in der Wikipedia zur Siebformel anschaut, sieht man, dass man dabei als Index Mengen verwendet. Das ist im Vergleich zu dem, was man kennt, schon mächtig gewöhnungsbedürftig.

@Edit
Wenn du das liest, wirst du vermutlich verärgert sein. Aber bedenke, würde ich einen so langen Beitrag schreiben, nur um jemanden zu ärgern, den ich gar nicht kenne?

@Edit2
Bei der Ausführung des Vefahrens für kleine m würde ich eine Änderung der Indizierung empfehlen. Ich würde empfehlen, dann für die H-Mengen als Index die Zahlen zu verwenden, die sie höchsten enthalten sollen. Statt $\begin{eqnarray*} H_4 \end{eqnarray*}$ würde man also schreiben $\begin{eqnarray*} H_{1234} \end{eqnarray*}$ . Und $\begin{eqnarray*} H_{4,1} \end{eqnarray*}$ wäre dann $\begin{eqnarray*} H_{234} \end{eqnarray*}$ .

17.07.2010, 18:28

mathchild

Auf diesen Beitrag antworten »

@Huggy

Zitat:

Wenn du das liest, wirst du vermutlich verärgert sein.

Wie kommst du denn da drauf! Du bist doch sehr freundlich. Und natürlich ist diese Thematik recht abstrakt. Und ganz sicher vertue ich mich sehr häufig.

Also mir geht es nicht um den Beweis der Siebformel. Den Induktionsbeweis der Siebformel habe ich verstanden und auch wie die Sache funktioniert - was ja aus einem Beweis mit Induktion nicht immer hervorgeht. Jetzt würde ich gern die Siebformel anwenden, um die Aufgabe mit den Würfeln zu lösen.

Bisher haben wir doch erreicht

$\begin{eqnarray*} \left |G_m \right |= \left | H_m \right |- \left | \bigcup_{i=1}^m H_{m-1,i}\right | \end{eqnarray*}$

Es ist

$\begin{eqnarray*} |H_{m}| = m^N \end{eqnarray*}$

Jetzt geht es darum, die Siebformel auf den verbleibenden Ausdruck anzuwenden.

$\begin{eqnarray*} |\bigcup_{i=1}^m H_{m-1,i}| = \sum_{k = 1}^{m} (-1)^{k-1} \sum_{1 \leq i_1 \leq ... \leq i_i\leq m} |\bigcap_{j=1}^k H_{m-1,i_j}| \end{eqnarray*}$

Ich hoffe mal, dass bis hierher alles noch richtig ist. Aber dann komme ich mit der Auswertung der Schnittmenge nicht klar. Du versuchst wohl den Ausdruck schrittweise zu reduzieren. Aber dann müsste man ja jetzt irgendwie mit Induktion an die Sache herangehen. Oder übersehe ich da etwas.

17.07.2010, 19:08

mathchild

Auf diesen Beitrag antworten »

Habe erst jetzt deinen letzten Beitrag so ganz bis in alle Einzelheiten studiert. Also muss man die Durchschnitte mit Induktion bearbeiten, wobei im Index Mengen verwendet werden. Das klingt wirklich ganz schön verzwickt. Wobei die resultierende Formel dann erstaunlich einfach ausfällt.

17.07.2010, 19:15

Auf diesen Beitrag antworten »

Das sind ja gerade die Hauptanwendungsfälle der Siebformel: Wo die Durchschnitte (genauer gesagt deren Mächtigkeiten bzw. Wahrscheinlichkeiten) einfach berechenbar sind, ganz im Gegensatz zu den im Endeffekt interessierenden Vereinigungen - siehe z.B. auch Wichtelproblem.

17.07.2010, 21:07

mathchild

Auf diesen Beitrag antworten »

Ja und wie leitet man jetzt aus dem mit der Siebformel erhaltenen Ausdruck die Lösung der Aufgabe ab? Also das schrittweise Vorgehen von Huggy zum Behandeln der Durchschnitte verstehe ich ja, aber die Induktion kriege ich nicht hin.

17.07.2010, 21:17

Auf diesen Beitrag antworten »

Nach den Definitionen von $\begin{eqnarray*} H_m \end{eqnarray*}$ sowie der $\begin{eqnarray*} H_{m-1,i} \end{eqnarray*}$ enthält der Durchschnitt

$\begin{eqnarray*} \bigcap_{j=1}^k H_{m-1,i_j} \end{eqnarray*}$

genau jene Wurfergebnis-N-Tupel, deren Augenzahlen aus der Menge $\begin{eqnarray*} \{1,\ldots,m\}\setminus\{i_1,\ldots,i_k\} \end{eqnarray*}$ stammen, das sind also $\begin{eqnarray*} m-k \end{eqnarray*}$ mögliche Augenzahlen.

Wieviele solche Tupel gibt es gemäß einfachen kombinatorischen Überlegungen?

17.07.2010, 21:25

mathchild

Auf diesen Beitrag antworten »

Da würde ich jetzt vermuten

$\begin{eqnarray*} \begin{pmatrix} m \\ m-k \end{pmatrix} \end{eqnarray*}$

Oder liege ich schon wieder falsch?

17.07.2010, 21:30

Auf diesen Beitrag antworten »

Nein, mehr daneben geht gar nicht. unglücklich

Auswahl von $\begin{eqnarray*} N \end{eqnarray*}$ Elementen des Tupels aus $\begin{eqnarray*} (m-k) \end{eqnarray*}$ Elementen mit Zurücklegen (d.h. Mehrfachwahl ist ja möglich) und auch mit Beachtung der Reihenfolge.

17.07.2010, 21:36

mathchild

Auf diesen Beitrag antworten »

also dann vermute ich jetzt

$\begin{eqnarray*} (m-k)^N \end{eqnarray*}$

besser?

17.07.2010, 21:37

Auf diesen Beitrag antworten »

Genau. Eingesetzt in

Zitat:

Original von mathchild
Bisher haben wir doch erreicht

$\begin{eqnarray*} \left |G_m \right |= \left | H_m \right |- \left | \bigcup_{i=1}^m H_{m-1,i}\right | \end{eqnarray*}$

Es ist

$\begin{eqnarray*} |H_{m}| = m^N \end{eqnarray*}$

Jetzt geht es darum, die Siebformel auf den verbleibenden Ausdruck anzuwenden.

$\begin{eqnarray*} |\bigcup_{i=1}^m H_{m-1,i}| = \sum_{k = 1}^{m} (-1)^{k-1} \sum_{1 \leq i_1 \leq ... \leq i_i\leq m} |\bigcap_{j=1}^k H_{m-1,i_j}| \end{eqnarray*}$

ergibt sich also was? Fangen wir mit der letzten Formel unten an...

17.07.2010, 21:40

mathcild

Auf diesen Beitrag antworten »

Wenn ich damit weiterrechne dann erhalte ich für die Summe

$\begin{eqnarray*} \sum_{1 \leq i_1 \leq ... \leq i_k\leq m} |\bigcap_{j=1}^k H_{m-1,i_j}| \end{eqnarray*}$

$\begin{eqnarray*} = \sum_{1 \leq i_1 \leq ... \leq i_k\leq m} (m-k)^N \end{eqnarray*}$

$\begin{eqnarray*} = (m-k)^N \sum_{1 \leq i_1 \leq ... \leq i_k\leq m} 1 \end{eqnarray*}$

$\begin{eqnarray*} = (m-k)^N\begin{pmatrix} m \\ k \end{pmatrix} \end{eqnarray*}$

Ne, irgendwie liege ich schon wieder neben der Spur!

17.07.2010, 21:42

Auf diesen Beitrag antworten »

Jetzt hab ich wohl dein Selbstbewusstsein zu sehr runtergedrückt? Nein, diesmal liegst du richtig. Freude

Und nun weiter, nicht schlappmachen. smile

17.07.2010, 21:51

mathchild

Auf diesen Beitrag antworten »

$\begin{eqnarray*} |\bigcup_{i=1}^m H_{m-1,i}| = \sum_{k = 1}^{m} (-1)^{k-1} \sum_{1 \leq i_1 \leq ... \leq i_i\leq m} |\bigcap_{j=1}^k H_{m-1,i_j}| \end{eqnarray*}$

$\begin{eqnarray*} = \sum_{k = 1}^{m} (-1)^{k-1} (m-k)^N\begin{pmatrix} m \\ k \end{pmatrix} \end{eqnarray*}$

Und jetzt?

17.07.2010, 21:58

Auf diesen Beitrag antworten »

Naja, jetzt nur noch hier

Zitat:

Original von mathchild
$\begin{eqnarray*} \left |G_m \right |= \left | H_m \right |- \left | \bigcup_{i=1}^m H_{m-1,i}\right | \end{eqnarray*}$

einsetzen und ein bisschen umformen:

$\begin{eqnarray*} |G_m| = m^N - \sum_{k=1}^{m} (-1)^{k-1} \binom{m}{k} (m-k)^N = (-1)^0\binom{m}{0}m^N + \sum_{k=1}^{m} (-1)^k \binom{m}{k} (m-k)^N = \sum_{k=0}^{m} (-1)^k \binom{m}{k} (m-k)^N \end{eqnarray*}$ ,

d.h. $\begin{eqnarray*} |H_m| = m^N \end{eqnarray*}$ kann man strukturell einfach mit in der Summe "verdauen", als Summenglied für k=0. Augenzwinkern

Soweit erstmal alles klar?

17.07.2010, 22:02

mathchild

Auf diesen Beitrag antworten »

jo, das ist klar. Nur was machen wir mit dem störenden Ausdruck $\begin{eqnarray*} (m-k)^N \end{eqnarray*}$

Binomial entwickeln und die Doppelsumme bearbeiten. Das klingt mir nach verflixt viel Arbeit! Und ich sehe auch nicht wie ich die Summanden irgendwie geschickt anordnen könnte. unglücklich

17.07.2010, 22:05

mathchild

Auf diesen Beitrag antworten »

ah ich sehe schon, wir ersetzen m-k durch k und lassen die Summation anders herum laufen. smile

17.07.2010, 22:08

Auf diesen Beitrag antworten »

Summiert man in der Summe

$\begin{eqnarray*} \sum_{k=0}^{m} (-1)^k \binom{m}{k} (m-k)^N \end{eqnarray*}$ ,

"rückwärts", d.h. von $\begin{eqnarray*} k=m \end{eqnarray*}$ (entspricht j=0) beginnend rückwärts bis zu $\begin{eqnarray*} k=0 \end{eqnarray*}$ (entspricht j=m), dann entspricht das einer Indexsubstitution $\begin{eqnarray*} j=m-k \end{eqnarray*}$ , welche zur Identität

$\begin{eqnarray*} \sum_{k=0}^m (-1)^k \binom{m}{k} (m-k)^N = \sum_{j=0}^m (-1)^{m-j} \binom{m}{m-j} j^N \end{eqnarray*}$

führt. Mit der Binomialkoeffizientensymmetrie $\begin{eqnarray*} \binom{m}{m-j} = \binom{m}{j} \end{eqnarray*}$ sollten dann auch die letzten Unklarheiten beseitigt sein, oder?#

EDIT: Ok, hatte nicht gesehen, dass schon ein weiterer Beitrag von dir da war (wg. "neuer" Seite).

17.07.2010, 22:12

mathchild

Auf diesen Beitrag antworten »

Super! Damit ist die Formel lückenlos hergeleitet. Jetzt habe ich die Sache (endlich) intus.

Um es mal zu ordnen: Huggy hat mir gezeigt, wie man die Aufgabe "zu Fuß" lösen kann, d.h. er hat die Logik der Siebformel nachvollzogen. Und hätte die Aufgabe dann mit einem Induktionsbeweis gelöst.

Wenn man die Siebformel aber kennt und anwendet, dann braucht man das nicht mehr zu machen, sondern muss nur die auftretenden Durchschnitte behandeln. Was ja auch gelingt, wenn man nur sorgfältiger rechnen kann als ich. smile

Danke an euch beide, vor allem für eure engelsgleich Geduld! Da habe ich heute viel gelernt!

17.07.2010, 22:15

Auf diesen Beitrag antworten »

Schön.

Und wenn dich weitere Anwendungsfälle der Siebformel interessieren, dann kannst du dir ja das schon angesprochene bekannte Wichtelproblem und dessen Lösung anschauen (einfach mal suchen, hier im Board oder Google).

18.07.2010, 08:02

Huggy

Auf diesen Beitrag antworten »

Ach wie schön!
Da waren aber zwei gestern noch richtig fleißig.

18.07.2010, 09:31

Auf diesen Beitrag antworten »

Das war wohl nur zu dritt zu schaffen: Zwei Helfer, die sich bei auftretender Ermattung immer mal wieder gegenseitig abgelöst haben, und eine beharrliche Fragestellerin, die zum Schluss noch mal richtig aufgedreht hat.

18.07.2010, 10:27

Mystic

Auf diesen Beitrag antworten »

Wenn es dem Fragesteller nur um das Verständnis der Siebformel anhand dieses Beispiels ging, dann führt wohl kein Weg an diesen Betrachtungen vorbei, wenn es ihm aber um das Beispiel selber ging, dann wage ich den schüchternen Einwurf, dass die einfache Berechnung der Stirlingzahlen S2(6,k), k=0,1,2,..,6, doch eine sehr überlegenswerte Alternative darstellt, wie von mir oben schon angedeutet...

Nachfolgend möchte ich nun auch noch die Erklärungen nachliefern, warum das so funktioniert... Nummeriert man dazu die sechs Würfe mit 1 bis 6 durch (hat jetzt natürlich nichts mit den Augenzahlen 1 bis 6 zu tun!), so muss sich dazu nur überlegen, dass jeder Wurffolge, bei der genau k Zahlen verschieden sind, in bijektiver Weise eine Partition von {1,2,...,6} in genau k Klassen entspricht, wobei in jeder Klasse die Nummern der Würfe liegen, welche die gleiche Augenzahl ergeben haben...

Beispiel:

Wurf 1: 6,
Wurf 2: 3,
Wurf 3: 2,
Wurf 4: 3,
Wurf 5: 4,
Wurf 6: 2

Die führt auf die Partition {{1},{2,4},{3,6},{5}}, wobei im speziellen Fall noch die Zuordnung gilt

{1} -> 6, {2,4} -> 3, {3,6} -> 3, {6} -> 2

Man muss also im gegebenen Beispiel für jedes k in {0,1,..,6}

1. die Anzahl der Partitionen von {1,2,..,6} in k Klassen berechnen, was dann eben gerade auf die berühmten Stirlingzahlen S2(6,k) zweiter Art führt...

2. anschließend noch das Produkt S2(6,k) 6!/(6-k)! bilden, um auch noch alle möglichen Zuordnungen der Klassen zu den entsprechenden Augenzahlen zu erfassen..

In letzter Konsequenz geht es also um die Berechnung der S2(6,k), k=0,1,...,6, und dazu kann man sich der einfachen Rekursionsformel

S2(n,k) =S2(n-1,k-1)+k*S2(n-1,k) (*)

bedienen, wobei S2(n,k)=0 für k<1 oder k>n zu setzen ist (mit Ausnahme von S2(0,0)=1).

Die Herleitung dieser Formel ist so einfach, dass ich empfehle (zumindestens mache ich das so), sich nicht die Formel selber, sondern einfach ihre Herleitung zu merken... Man greift dazu ein festes Element, o.B.d.A. sei dies n, heraus, und überlegt sich dann, was passiert, wenn ich n in einer Partition streiche...Hier gibt es dann zwei Fälle

1. n war allein in seiner Klasse, dann falle ich in eine gewisse Partition von {1,2,..,n-1} in k-1 Klassen zurück...

2. n war nicht allein in seiner Klasse, dann falle ich in eine Partition von {1,2,..,n-1} in k Klassen zurück, aber anders als im Fall 1 kann diese Partition auf k Arten erreicht werden, je nachdem, in welcher der k Klassen das Element n war...

Die Fälle 1 und 2 ergeben also genau die beiden Summanden in der rechten Seite obiger Formel... Diese kann man nun dazu benützen, um die S2(6,k) auf einfachste Weise mit Hilfe einer Art "Pascalsches Dreieck" , aber eben unter Benützung von (*) zu berechnen... Ich führe das hier mal vor

code:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10:	n S2(n,k), k=0,1,..,n 0 1 1 0 1 2 0 1 1 3 0 1 3 1 4 0 1 7 6 1 5 0 1 15 25 10 1 6 0 1 31 90 65 15 1

Die endgültige Berechnung der Wahrscheinlichkeiten mit Hilfe der S2(6,k),k=0,1,..,6, geht dann weiter wie in meinem ersten Posting...

Edit: All diese Dinge sind natürlich für den Profi ein "alter Hut", wo er nur müde abwinkt, ich habe sie dennoch hier ausgeführt, um mit dieser "all inclusive"-Darstellung einen direkten Vergleich zu ermöglichen...

18.07.2010, 15:41

tigerbine

Auf diesen Beitrag antworten »

An die sieben Fachmänner:

Ihr habt euch hier so reingehängt. Freude

Könntet ihr in einer Co-Produktion das ganze zu einer Art "Artikel zur Siebformel" zusammenkopieren? Augenzwinkern

Ich fänd's toll und viele Leser bestimmt auch. smile

18.07.2010, 16:43

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von tigerbine
An die sieben Fachmänner:

Ihr habt euch hier so reingehängt. Freude

Könntet ihr in einer Co-Produktion das ganze zu einer Art "Artikel zur Siebformel" zusammenkopieren? Augenzwinkern

Ich fänd's toll und viele Leser bestimmt auch. smile

Was mich betrifft, so gebe ich gerne mein Einverständnis, meine 2 Beiträge hier in diesem Sinn zu verwenden, wenn dies gewünscht wird... Nur bin ich hier der Antagonist, der sagt, dass man in diesem Zusammenhang die Siebformel gerade nicht braucht, wenn man auf andere - imho einfachere - Berechnungsmethoden der Stirlingzahlen 2.Art zurückgreift, wie ich sie oben auch ausführlich beschrieben habe...

18.07.2010, 17:20

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic
wenn man auf andere - imho einfachere - Berechnungsmethoden der Stirlingzahlen 2.Art zurückgreift,

Ich weiß ja, dass du die Siebformel nicht magst - deswegen musst du aber nicht immer wieder deklamieren, dass der Weg über die Stirlingzahlen angeblich "einfacher" ist, nur weil er dir vertrauter ist. Ich sehe ihn als gleichwertig an - er mag, was den Summa-Summarum-Berechnungsaufwand betrifft, seine Vorteile haben - mehr nicht.

Zudem muss man schon trennen: Geht es um das konkrete Problem hier, oder um die Siebformel allgemein. Letztere in ihrer Allgemeinheit kann wohl kaum durch die Stirlingzahlen ersetzt werden.

Wie auch immer: Das Publikum entscheidet, welcher Weg beschritten wird. Augenzwinkern

18.07.2010, 17:57

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Ich weiß ja, dass du die Siebformel nicht magst - deswegen musst du aber nicht immer wieder deklamieren, dass der Weg über die Stirlingzahlen angeblich "einfacher" ist, nur weil er dir vertrauter ist. Ich sehe ihn als gleichwertig an - er mag, was den Summa-Summarum-Berechnungsaufwand betrifft, seine Vorteile haben - mehr nicht.

Dass ich die Siebformel "nicht mag", kann ich so nicht stehen lassen... Dieser Eindruck mag vielleicht daurch entstanden sein, dass ich immer wieder auch Alternativen aufzeige - nicht zuletzt auch in diesem Thread - aber mehr jetzt in dem Sinne, dass sich die Leser dann aussuchen können, was ihnen letztlich am besten gefällt... Es wäre im Gegenteil ausgesprochen töricht, die Wichtigkeit der Siebformel - für mich geläufiger unter der Bezeichnung Inklusions-Exklusionsprinzip - in vielen Bereichen der Mathematik, insbesondere der Diskreten Mathematik, leugnen zu wollen...

Zitat:

Original von Arthur Dent
Zudem muss man schon trennen: Geht es um das konkrete Problem hier, oder um die Siebformel allgemein. Letztere in ihrer Allgemeinheit kann wohl kaum durch die Stirlingzahlen ersetzt werden.

Diese Frage hat sich für mich jetzt gar nicht gestellt, da es für mich immer nur um das konkrete Problem hier gegangen ist, aber wenn du sie schon stellst, so habe ich die Antwort dazu ja oben schon gegeben...

Zitat:

Original von Arthur Dent
Wie auch immer: Das Publikum entscheidet, welcher Weg beschritten wird. Augenzwinkern

Ja, in der Tat... lieselotte und mathchild (wenn nicht ohnehin ident) hatten jedenfalls die größten Probleme damit, die Formel auch nur soweit zu verstehen, um damit etwas ausrechnen zu können, geschweige denn, sie zu beweisen... Aber ich weiß schon, statistisch gesehen ist dieses sample viel zu klein... Augenzwinkern

18.07.2010, 18:00

Auf diesen Beitrag antworten »

Zugegeben ist es diesmal eine Berechnungsalternative, die (ohne CAS) mal nicht in exorbitantem Aufwand endet, wie es manchmal bei deinen anderen Steckenpferd "erzeugende Funktion" der Fall ist. Augenzwinkern

Zitat:

Original von Mystic

Zitat:

Original von Arthur Dent
Wie auch immer: Das Publikum entscheidet, welcher Weg beschritten wird. Augenzwinkern

Richtig, one-sample bzw. two-sample ist dürftig. Über die Erfahrungen mit der Kompliziertheit der Alternativmethode kann wegen zero-sample leider gar nichts gesagt werden. Big Laugh

18.07.2010, 20:42

mathchild

Auf diesen Beitrag antworten »

Ich habe hier zwar nur nach Anleitung gearbeitet. Aber vielleicht darf ich trotzdem etwas anmerken.

Die explizite Darstellung der Stirling Zahlen

$\begin{eqnarray*} S_{n,k} = \frac{1}{k!} \sum\limits_{j=1}^k (-1)^{n-j}\begin{pmatrix} k \\ j \end{pmatrix} j^n \end{eqnarray*}$

hat doch frappierende Ähnlichkeit mit der hier bewiesenen Summenformel. Im Grunde vollzieht doch die Stirling Zahl genau das, was Arthur mir über die Kardinalität der Durchschnitte gezeigt hat. Offensichtlich basiert die Stirling Formel auf der Siebformel und leistet dann die Auswertung der Durchschnitte.

Wenn man die Siebformel anwendet spart man den von Huggy verwendeten Induktionsbeweis.

Wenn man die Stirling Formel verwendet spart man die von Arthur verwendete Auswertung der Durchschnitte.

Mir scheint die Verfahren liegen alle ganz dicht beieinander.

18.07.2010, 20:47

Auf diesen Beitrag antworten »

Was auf wem basiert, ist Ansichtssache - irgendeine Kausalität sieht man den Endformeln nicht an.

Und dass sich die Formeln ähneln - mit entsprechend angepassten Vorfaktor sogar gleich sind - ist auch nicht verwunderlich, sondern unvermeidlich: Schließlich sind beide Wege inhaltlich richtig und müssen so zwangsläufig zum selben Ergebnis führen. Augenzwinkern

18.07.2010, 21:47

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von mathchild
Die explizite Darstellung der Stirling Zahlen

$\begin{eqnarray*} S_{n,k} = \frac{1}{k!} \sum\limits_{j=1}^k (-1)^{n-j}\begin{pmatrix} k \\ j \end{pmatrix} j^n \end{eqnarray*}$

hat doch frappierende Ähnlichkeit mit der hier bewiesenen Summenformel. Im Grunde vollzieht doch die Stirling Zahl genau das, was Arthur mir über die Kardinalität der Durchschnitte gezeigt hat. Offensichtlich basiert die Stirling Formel auf der Siebformel und leistet dann die Auswertung der Durchschnitte.

Es fallen mir auf Anhieb drei Möglichkeiten ein, diese Formel zu beweisen, aber vermutlich gibt's noch viele weitere:

1. Man zeigt, dass die Zahlen

$\begin{eqnarray*} S_{n,k} = \frac{1}{k!} \sum\limits_{j=1}^k (-1)^{n-j}\begin{pmatrix} k \\ j \end{pmatrix} j^n \end{eqnarray*}$

der von mir angegebenen Rekursion genügen, was in höchstens 3 Zeilen machbar sein sollte...

2. Man verallgemeinert das von mir angegebene Differenzenschema, d.h., benützt die Tatsache, dass für die Stirlingzahlen 2.Art gilt

$\begin{eqnarray*} x^n = \sum_{k=0}^n S_{n,k} x^{\underline k} \end{eqnarray*}$

wobei

$\begin{eqnarray*} x^{\underline k} :=x(x-1)\dots (x-k+1) \end{eqnarray*}$

die sog. fallenden faktoriellen Potenzen sind, m.a.W. Stirlingzahlen 2.Art haben in diesen Potenzen eine überaus einfache erzeugende Funktion...

3. Last, but not least, Arthur's Siebformel...

Und mathchild, beschäftige dich nicht zu sehr mit Stirlingzahlen 2.Art, sonst kommst du noch auf den Geschmack... Aber versprich mir vor allem eines: Solltest du meine Beiträge dazu durchgelesen und sie, Gott behüte, eventuell sogar verstanden haben, dann tu dies bitte hier auf keinen Fall kund - dies würde Arthur das Herz brechen... Big Laugh

18.07.2010, 22:00

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic
dies würde Arthur das Herz brechen... Big Laugh

Eigentlich bricht mir das Herz, dass du deine Provokationen weitertreibst, obwohl ich dich gerade eben noch verteidigt habe. Forum Kloppe

Es ist schon eine Kunst, die nicht jeder beherrscht:

Sich aus einem Thread zurückziehen, obwohl man meint, dass der eigene Weg besser und kürzer ist - aber nicht eingestehen will, dass man dadurch den Fragesteller verwirrt (etwas durch für den Fragesteller immer neue Begriffsbildungen wie "Partition" u.ä.).

Ich gebe durchaus zu, dass mir das auch bisweilen passiert.

18.07.2010, 22:43

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Eigentlich bricht mir das Herz, dass du deine Provokationen weitertreibst, obwohl ich dich gerade eben noch verteidigt habe. Forum Kloppe

Sorry, war in meinen Augen jetzt keine Provokation, sonst hätt ich das sicher nicht so gesagt... unglücklich

Wo genau hast du mich übigens verteidigt? Der Thread hat jetzt doch schon eine gewisse Länge, sodass ich den Überblick verloren habe...

Zitat:

Original von Arthur Dent
Es ist schon eine Kunst, die nicht jeder beherrscht:

Sich aus einem Thread zurückziehen, obwohl man meint, dass der eigene Weg besser und kürzer ist - aber nicht eingestehen will, dass man dadurch den Fragesteller verwirrt (etwas durch für den Fragesteller immer neue Begriffsbildungen wie "Partition" u.ä.).

Ich würde sagen, bisher ist doch noch gar nichts passiert, ausser das mathchild offenbar die Stirlingzahlen gegooglet hat... Damit ich ihn mit neuen Begriffsbildungen "verwirren" kann, müßte er sich erst mal meine Beiträge überhaupt durchlesen... Bisher gab es noch keinen Hinweis darauf, dass dies überhaupt geschehen ist... verwirrt

Im übrigen, war das zentrale Thema dieses Threads jetzt nicht unbedingt die Siebformel, sondern die Berechnung von gewissen Wahrscheinlichkeiten bei Wurffolgen, wo eben die Siebformel nur einen möglichen Zugang darstellt... Es muss also erlaubt sein, auch Beiträge zu bringen, die zum Thema passen, obwohl sie mit der Siebformel jetzt nicht unmittelbar zusammenhängen...

18.07.2010, 22:50

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic
Wo genau hast du mich übigens verteidigt?

Das wundert mich überhaupt nicht, dass du sowas nicht mitkriegst.

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

Das wichtigste ist, dass mathchild das Problem und die Lösung verstanden hat. Wenn du dich jetzt weiter hier produzieren willst, um ihr deine Lösungsalternative im einzelnen zu erläutern, dann kannst du das natürlich gern tun. Wink

18.07.2010, 23:03

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Das wundert mich überhaupt nicht, dass du sowas nicht mitkriegst.

Ja, es gibt schon eine Stelle, nämlich

Zitat:

Original von Arthur Dent
Für olle Kamellen gibt es keine Professorentitel, denn wie Mystic ja richtig anmerkte, geht es hier im wesentlichen um das Partitionsproblem und die dazu gehörenden Stirlingzahlen - auch wenn mir das oben zunächst nicht bewusst war. Augenzwinkern

die man so deuten kann und die mich ja auch ehrlich gefreut, falls du das gemeint haben solltest... Allerdings liegt das jetzt schon etwas weiter zurück, daher meine Frage...

Zitat:

Original von Arthur Dent
Das wichtigste ist, dass mathchild das Problem und die Lösung verstanden hat. Wenn du dich jetzt weiter hier produzieren willst, um ihr deine Lösungsalternative im einzelnen zu erläutern, dann kannst du das natürlich gern tun. Wink

Hm, und das soll keine Provokation sein?... Ne, sorry, die Lust mich hier noch weiter zu "produzieren" wie du es nennst, ist mir gründlich vergangen... geschockt

19.07.2010, 11:40

mathchild

Auf diesen Beitrag antworten »

ey, wer wird sich denn da gleich streiten. Ich dachte immer Mathematiker wären ruhige und besonnene Leute. smile

Ich habe mal versucht den Beweis alternativ mit den Stirling Zahlen zweiter Art zu führen.

Zitat:

Original von Mystic

$\begin{eqnarray*} p=\frac {6!}{6^6} (u \odot v) =\frac 5{324} (u \odot v) =(0,\frac 1{7776},\frac {155}{7776},\frac {25}{108},\frac {325}{648}, \frac {25}{108},\frac 5{324}) \end{eqnarray*}$

In meiner Notation mit N und n beliebig (statt N=6 und n=6) erhalte ich da

$\begin{eqnarray*} p_m = \frac {n!}{n^N} \cdot \frac {1}{(n-m)!} \cdot S_{n,m} \end{eqnarray*}$

$\begin{eqnarray*} = \frac {1}{n^N} \cdot \begin{pmatrix} n \\ m \end{pmatrix} \cdot S_{n,m} \end{eqnarray*}$

Die explizite Form der Stirling Zahlen lautet mit angepasster Nomenklatur

$\begin{eqnarray*} S_{n,m} = \sum\limits_{k=1}^m (-1)^{n-k}\begin{pmatrix} m \\ k \end{pmatrix} k^n \end{eqnarray*}$

Und damit erhalte ich

$\begin{eqnarray*} p_m = \frac {1}{n^N} \cdot \begin{pmatrix} n \\ m \end{pmatrix} \cdot \frac{1}{m!} \sum\limits_{k=1}^m (-1)^{n-k}\begin{pmatrix} m \\ k \end{pmatrix} k^n \end{eqnarray*}$

Heraus kommen soll aber

$\begin{eqnarray*} p_m = \frac{1}{n^N}\cdot \binom{n}{m} \cdot \sum_{k=1}^m (-1)^{m-k} \cdot \binom{m}{k} \cdot k^N \end{eqnarray*}$

Das sieht zwar ähnlich aus, knapp vorbei ist aber halt auch daneben. Klar habe ich mich vertan. Hat jemand die Geduld meine Rechnung zu korrigieren?

« vorherige Seite 123 nächste Seite »

Neue Frage »

Antworten »

6mal Würfeln. - Seite 2

Verwandte Themen