Tupel-Anzahl < Stochastik < Hochschule < Mathe < Vorhilfe
|
Hallo Zusammen,
| Aufgabe | | Sei $N [mm] \in \IN_{\ge 3}$. [/mm] Sei [mm] $\left(x_1,\ldots,x_N\right)$ [/mm] mit [m]0 \le x_i < M;\;M \in \IN[/m] und [mm] $x_1 \le \cdots \le x_N$. [/mm] Wieviele solche Tupel gibt es? |
Zur Lösung der Aufgabe habe ich mir folgende Formel überlegt(, wobei [mm] $\sigma$ [/mm] bei mir die Anzahl der Tupel sein soll):
[m]\begin{gathered}
\sigma = \sum\limits_{x_1 = 0}^{M-1} {\sum\limits_{x_2 = x_1 }^{M-1} {\sum\limits_{x_3 = x_2 }^{M-1} { \cdots \sum\limits_{x_N = x_{N - 1} }^{M-1} 1 } } } = \sum\limits_{x_1 = 0}^{M-1} {\sum\limits_{x_2 = x_1 }^{M-1} {\sum\limits_{x_3 = x_2 }^{M-1} { \cdots \sum\limits_{x_{N - 1} = x_{N - 2} }^{M-1} {\left( {M-1 - x_{N - 1} + 1} \right)} } } } \hfill \\
= \sum\limits_{x_1 = 0}^{M-1} {\sum\limits_{x_2 = x_1 }^{M-1} {\sum\limits_{x_3 = x_2 }^{M-1} { \cdots \left( {\left( {\sum\limits_{x_{N - 1} = 1}^{M - 1 - x_{N - 2} + 1} \left(M-1\right) } \right) - \left( {\sum\limits_{x_{N - 1} = 1}^{M - 1 - x_{N - 2} + 1} {x_{N - 1} } } \right) + M - 1 - x_{N - 2} + 1} \right)} } } \hfill \\
= \sum\limits_{x_1 = 0}^{M-1} {\sum\limits_{x_2 = x_1 }^{M-1} {\sum\limits_{x_3 = x_2 }^{M-1} { \cdots \left( {\left( {M - 1} \right)\left( {M - 1 - x_{N - 2} + 1} \right) - \frac{{\left( {M-1 - x_{N - 2} + 1} \right)\left( {M-1 - x_{N - 2} + 2} \right)}}
{2}}+M-1-x_{N-2}+1 \right)} } } \hfill \\
= \dotsm = \operatorname{?} \hfill
\end{gathered}[/m]
Man stelle sich ein solches Tupel wie einen Zähler (z.B. Wasserzähler) vor. Beim Hochzählen werden alle möglichen Tupel durchlaufen. Jetzt bauen wir eine "Verzahnung" in den Zähler ein, so daß der nächsthöhere Stellenwert dort zu zählen anfängt, wo sich der nächst-niedrigere Stellenwert gerade befindet (Wodurch wir auch automatisch die gewünschte monotone Anordnung erhalten). So kommt diese Summe zustande.
Nur wie löse ich das? Es ist leider kein Schema erkennbar und die Größe der Terme steigt mit jedem Auflösen einer inneren Summe stark an.
Vielen Dank!
Viele Grüße
Karl
P.S. Ich habe diese Frage auch ![[]](/images/popup.gif) im Usenet gestellt.
|
|
| |
|
Hallo zusammen!
Ich versuche dieses Abzählprinzip anhand folgender Aufgabe zu begreifen
| Aufgabe | | In einem Hotel sind noch 5 Zimmer frei. Jedes der Zimmer ist ein Dreibettzimmer. Am Abend kommen noch 3 Wanderburschen [mm]A,B[/mm] und [mm]C[/mm]. Wie viele Möglichkeiten hat der Hotelier, die Gäste unterzubringen, wenn jedem Gast per Zufall eines der 5 Dreibettzimmer zugewiesen wird und zugelassen wird, daß in einem Zimmer 1, 2 oder 3 Personen schlafen? Der Hotelier will nur wissen, welche Zimmer mit wievielen Personen belegt sind. |
Hier ist die Lösung der Aufgabe. (Meine eigentliche Frage steht weiter unten.) :
In einer Urne denken wir uns 5 unterscheidbare Kugeln, die mit den Ziffern 1, 2, 3, 4 und 5 durchnummeriert sind. Es wird drei Mal eine Kugel gezogen; Die jeweils gezogene Kugel wird jeweils vor der nächsten Ziehung in die Urne zurückgelegt. In einer Tabelle notieren wir jeweils eine 1 unter die jeweilige gezogene Zimmernummer:
[mm]\begin{array}{|c|c|c|c|c|}
\hline\multicolumn{5}{|c|}{\texttt{Zimmer Nr.}}\\ \hline\hline
1&2&3&4&5\\ \hline\hline
{}&1&1&{}&1\\ \hline
1&{}&{}&11&{}\\ \hline
1&11&{}&{}&{}\\ \hline
\end{array}[/mm]
In Zeile 1 ist jeweils 1 Gast in den Zimmern 2, 3, 5 untergebracht. Zeile 3 bedeutet: In Zimmer 1 ist ein Gast, in Zimmer 2 sind 2 Gäste. Wir könnten versuchen, systematisch alle Möglichkeiten aufzuschreiben. (Es gibt 35 Möglichkeiten.) Wir wollen einen Weg beschreiben, der unter Rückführung auf eine schon bekannte kombinatorische Figur zu einer Formel für die Anzahlbestimmung führt. Wir lösen uns von der Tabelle. Das geht aber nicht ohne weiteres, da dann in jeder Zeile dieselbe Sequenz aus drei Einsen steht: 111. Man kann so nicht erkennen, welche Zimmer belegt sind. Die in der Tabelle durch Striche voneinander getrennten Zimmer müssen erkennbar bleiben. Als Übergangsmarkierung wählen wir das Zeichen 0 (wir könnten auch Striche | setzen). Zur Trennung der 5 Zimmer (Kugeln, Zeichen) sind 5-1 = 4 Trennungen, also 4 Nullen erforderlich. Mit den drei Einsen zusammen entstehen also 4 + 3 = 7-gliederige Sequenzen. Die in der Tabelle angegebenen Belegungen sind also durch folgende Zeichenfolgen eindeutig beschrieben:
0 1 0 1 0 0 1
1 0 0 0 1 1 0
1 0 1 1 0 0 0
Umgekehrt liegt auch Eindeutigkeit vor. Sei etwa z.B. 0 1 1 1 0 0 0 gegeben. Das bedeutet: Alle 3 Personen sind in Zimmer 2 untergebracht.
An dieser Stelle habe ich die erste Frage. Intuitiv glaube ich ja auch, daß dieses Schema eindeutig ist, aber das reicht mir irgendwie nicht. Wie kann man hier wirklich sichergehen, daß jeder Belegung der Zimmer genau eine 7er-Sequenz entspricht und umgekehrt auch?
Durch diesen "Trick" ist die Lösung gefunden. Wir brauchen nur noch zu fragen, an welchen Stellen die 4 Zeichen 0 stehen können. Das geht gemäß der letzten kombinatorischen Figur (Kombination ohne Wiederholung) auf [mm]\textstyle\binom{7}{4} = \frac{7!}{4!\cdot{3!}} = \binom{7}{3} = 35[/mm] verschiedene Arten.
Wieso ist das so? Tut mir Leid, die Frage ist ungenau formuliert, aber die Formel [mm]\textstyle\binom{n}{k}[/mm] besagt letztlich, daß ich mir [mm]k\![/mm] Kugeln mit einem Griff (und damit ungeordnet) aus einer Kiste greife, ohne sie zurückzulegen. Füllen wir die Kiste jetzt mit 3 schwarzen Kugeln (-> 1) und 4 gelben (-> 0) Kugeln. Die obige Formel besagt dann: Ich ziehe mit einem Griff 4 Kugeln aus der Kiste mit den 7 Kugeln. Aber wer sagt mir dann, daß ich damit nicht z.B. 2 gelbe und 2 schwarze, oder z.B. 3 schwarze und eine gelbe Kugel rausgezogen habe? Was sagt mir diese Formel dann über die Positionen der Nullen aus? Deshalb verstehe ich den Zusammenhang hier nicht, obwohl alle vorhergehenden Überlegungen klar sind.
Danke für eure Hilfe!
Viele Grüße
Karl
|
|
|
| |
|
Hallo und guten Morgen Karl,
also die Anzahl der Moeglichkeiten sollte doch sowas wie [mm] 5^3 [/mm] sein, oder ?
Denn die Leute ziehen unabhaengig voneinander in eines der 5 Zimmer, jeder hat also 5 Moeglichkeiten.....
....ok, ok, ich verstehe, es soll die Anzahl der Moeglichkeiten fuer die Anzahlen der Personen pro Zimmer
berechnet werden, und dann ist Deine Loesung richtig.
Dass die Bijektion bei Dir stimmt, ist doch offensichtlich: Die Anzahl der Moeglichkeiten ist doch gleich der
Anzahl der Vektoren [mm] v\in \{0,1,2,3\}^5 [/mm] mit der Eigenschaft [mm] \sum_{i=1}^5v_i=3,
[/mm]
und Deine Schreibweise codiert doch die [mm] v_i [/mm] als leeren String im Falle [mm] v_i=0 [/mm] und ansonsten unär
(d.h. 2 wird als 11 codiert, 3 als 111 und so).
Insofern: Sehr schoene Darstellung, und alles inklusive Antwort steckt schon in der Frage.
Viele Gruesse,
Mathias
|
|
|
| |
|
Hallo Mathias,
> Dass die Bijektion bei Dir stimmt, ist doch offensichtlich:
> Die Anzahl der Moeglichkeiten ist doch gleich der
> Anzahl der Vektoren [mm]v\in \{0,1,2,3\}^5[/mm] mit der Eigenschaft
> [mm]\sum_{i=1}^5v_i=3,[/mm]
>
> und Deine Schreibweise codiert doch die [mm]v_i[/mm] als leeren
> String im Falle [mm]v_i=0[/mm] und ansonsten unär
> (d.h. 2 wird als 11 codiert, 3 als 111 und so).
Mittlerweile finde ich diese Darstellung auch eindeutig. Die Frage hat sich jetzt erledigt. Allerdings verstehe ich trotzdem nicht, wie man hiervon jetzt auf die Abzählformel [mm]\textstyle\binom{7}{4}[/mm] kommt?
Viele Grüße
Karl
|
|
|
| |
|
Hallo und guten Morgen Karl,
bin verunsichert:
(1,2,0,0,0) und (2,1,0,0,0) wuerden doch beide durch 111000 codiert, oder ?
Zu Fuss:
Alle drei auf ein Zimmer: 5 Moegl.
Zwei auf eines, einer in ein Einzelzimmer:
[mm] 5\cdot [/mm] 4 (waehle erst das Zweier-Zimmer aus 5 moeglichen, dann das Einzelzimmer aus 4 verbleibenden).
Alle drei in Einzelzimmer: [mm] {5\choose 3}= \frac{5\cdot 4}{2}=10 [/mm] Moegl.
Insgesamt: 5+20+10=35
Test:
[mm] {7\choose 4}=\frac{7\cdot 6\cdot 5}{3\cdot 2}=7\cdot [/mm] 5=35
Ups, da stimmt wohl am Anfang etwas noch nicht.
(Hab nochmal gelesen.) Also die Nullen sind Trennstriche.
Aber dann ist es doch klar: Wir haben 4 Trennstriche, und die Einsen muessen wir
dazwischen plazieren. Wir codieren Konfigurationen durch Strings der Laenge 7 mit genau 4 Nullen
und 3 Einsen. Das Mapping
[mm] \{Belegungen\: der\: Zimmer\}\to\{v\in\{0,1\}^5|\sum_{i=1}^7v_i=3\}
[/mm]
sollte doch klar sein, oder
Dann ist aber die Wahl eines
[mm] v\in\{0,1\}^5\:\: mit\:\: \sum_{i=1}^5v_i=3 [/mm]
doch nichts anderes als die Wahl von 4 aus 7 Positionen fuer die Nullen (oder 3 aus 7 Positionen fuer die Einsen),
und
[mm] {7\choose 3}= {7\choose 4}=35
[/mm]
(Lag da das Problem ?).
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:30 Mo 06.03.2006 | | Autor: | Karl_Pech |
Hallo Mathias,
> Ups, da stimmt wohl am Anfang etwas noch nicht.
>
> (Hab nochmal gelesen.) Also die Nullen sind Trennstriche.
>
> Aber dann ist es doch klar: Wir haben 4 Trennstriche, und
> die Einsen muessen wir
> dazwischen plazieren. Wir codieren Konfigurationen durch
> Strings der Laenge 7 mit genau 4 Nullen
> und 3 Einsen. Das Mapping
>
>
> [mm]\{Belegungen\: der\: Zimmer\}\to\{v\in\{0,1\}^5|\sum_{i=1}^7v_i=3\}[/mm]
>
> sollte doch klar sein, oder
>
> Dann ist aber die Wahl eines
>
> [mm]v\in\{0,1\}^5\:\: mit\:\: \sum_{i=1}^5v_i=3[/mm]
>
> doch nichts anderes als die Wahl von 4 aus 7 Positionen
> fuer die Nullen (oder 3 aus 7 Positionen fuer die Einsen),
>
> und
>
> [mm]{7\choose 3}= {7\choose 4}=35[/mm]
Ich denke, ich habe es jetzt verstanden. Ich habe da sogar noch einen anderen Ansatz gefunden, der wieder eine Argumentation über Tupel mit der Eigenschaft [mm]1 \le a_1 \le \dotsb \le a_k \le n[/mm] führt. Bei diesem Ansatz wird diese Ungleichungskette "auseinandergezogen", indem man [mm]b_j := a_j + j-1[/mm] setzt mit [mm]j = 1,\dotsc,k[/mm]. Dadurch erreicht man [mm]1 \le b_1 < \dotsb < b_k \le n+k-1[/mm] und gelangt so auch zu der gewünschten Formel.
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:27 Mo 06.03.2006 | | Autor: | mathiash |
Hallo Karl,
jou, sieht auch gut aus.
Wir hatten mal ne Vorlesung Diskrete Mathematik bei Jaroslav Nesetril (so der Name des Professors, der damals
fuer ein Jahr Gast bei Korte war), und der hat zu allen moeglichen Themen jeweils drei oder mehr verschiedene
Beweise und Sichtweisen angegeben, das war schon toll. Vielleicht wandelst Du ja unterbewusst auf Nesetrils Spuren -
liescht eijentlisch noch Schnee up d'r Schäl Sick ?
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:56 Sa 25.02.2006 | | Autor: | Phoney |
Hallo.
Das war zwar nicht gefragt, aber nachdem ich mich 2(?) Stunden damit beschäftigt habe, bin ich endlich über einen Alternativweg zum Ziel gekommen, evtl. interessiert den die Nachwelt, für Leute, die später mal suchen.
Zunächst einmal habe ich alle Ergebnismengen notiert (Naja fast)
Es gibt ja folgende Fälle zu betrachten.
Einmal dass alle drei Wanderer ein Zimmer nehmen (B=belegt, N=nicht belegt):
S = {(B,N,N,N,N),(N,B,N,N,N),...,(N,N,N,N,B)}
Das sind 5 Fälle...Leicht abzuzählen.
Was übersetzt genau eben die Tabelle ist:
$ [mm] \begin{array}{|c|c|c|c|c|} \hline\multicolumn{5}{|c|}{\texttt{Zimmer Nr.}}\\ \hline\hline 1&2&3&4&5\\ \hline\hline {}111&{}&{}&{}&{}\\ \hline {}&111&{}&{}&{}\\ \hline {}&{}&111&{}&{}\\ \hline \end{array} [/mm] $
Komplizierter wird es bei dem zweiten Fall, der sich ganz schön in der Tabelle darstellen lässt:
$ [mm] \begin{array}{|c|c|c|c|c|} \hline\multicolumn{5}{|c|}{\texttt{Zimmer Nr.}}\\ \hline\hline 1&2&3&4&5\\ \hline\hline 11&1&{}&{}&{}\\ \hline 11&{}&1&{}&{}\\ \hline 11&{}&{}&1&{}\\ \hline \end{array} [/mm] $
usw.
Eigentlich lässt sich jetzt schon ablesen, dass es 20Möglichkeiten sind...
Jedenfalls würde ich dazu tendieren (evtl. ist es auch nur Zufall), dass der Hotelier einfach "zwei Leute" als eine Person behandelt und diese dann in ein Zimmer weist. Wie schon in der Frage steht: "Der Hotelier will nur wissen, welche Zimmer mit wievielen Personen belegt sind." Das heißt, hier (für diesen zweiten Fall) liegt eine geordnete Stichprobenziehung ohne Zurücklegen vor, denn es macht einen Unterschied (für den Hotelier), ob im ersten Zimmer eine Person und im zweiten Zimmer zwei Personen sind oder ob im ersten Zimmer zwei Personen sind und im zweiten eben nur eine.
D.h. wir haben in einem Topf fünf Kugeln. Diese werden gezogen, wobei der Hotelier noch zu unterscheiden hat: Die erste Kugel mit der Zahl, die ich ziehe, ist die für die beiden Wanderer oder für die erste Person? (Was wiederum heißt: (WW,W) oder (W,WW) :"ob im ersten Zimmer eine Person und im zweiten Zimmer zwei Personen sind oder ob im ersten Zimmer zwei Personen sind und im zweiten eben nur eine."
[mm] \bruch{n!}{(n-k)!} [/mm] = [mm] \bruch{5!}{(5-2)!} [/mm] = 20
Insgesamt haben wir nun 20+5 Möglichkeiten.
Der letzte Fall ist nun eben:
$ [mm] \begin{array}{|c|c|c|c|c|} \hline\multicolumn{5}{|c|}{\texttt{Zimmer Nr.}}\\ \hline\hline 1&2&3&4&5\\ \hline\hline 1&1&1&{}&{}\\ \hline 1&1&{}&1&{}\\ \hline 1&1&{}&{}&1\\ \hline \end{array} [/mm] $
usw.
Nun interessiert es nicht mehr, "wer" in welchem Zimmer ist. Den Hotelier interessiert lediglich: Ist das Zimmer besetzt oder nicht (welche Einzelperson das ist, ist egal): Unser dritter und letzter Fall: ungeordnete Stichprobenziehung ohne zurücklegen (das Zimmer kann ja nicht doppelt besetzt werden - daher ohne zurücklegen)
[mm] \vektor{5 \\ 3} [/mm] = [mm] \bruch{5!}{3! * 2!} [/mm] = 10
5+20+10 = 35
Hoffentlich ist das auch richtig... 
Grüße Phoney
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:11 So 26.02.2006 | | Autor: | Karl_Pech |
Hallo Phoney,
Deine Lösung finde ich auch sehr schön. Was mir an meinem Ansatz von damals mit den verschachtelten Summen nicht gefällt, ist dieses "Rumraten", das da mit reingespielt hat. Schließlich habe ich dort ja nur einige endliche Summenausdrücke aufgelöst, und daraus auf die geschlossene Darstellung des allgemeinen Summenausdrucks geschlossen. Vermutlich könnte man die Gleichheit dort sogar mit Induktion beweisen.
Viele Grüße
Karl
|
|
|
| |
|
Hallo Karl,
warum ist [mm] {n\choose k} [/mm] die Anzahl der k-elementigen Teilmengen einer n-elementigen Menge ?
Nun, dafuer gibt es viele Moeglichkeitne, den Beweis zu formulieren, hier eine kurze:
[mm] {n\choose k} =\frac{n!}{k!\:\cdot\: (n-k)!}
[/mm]
Nimm alle Permutationen der Zahlen 1 bis n. Zu jeder solchen
[mm] \pi_1,\ldots \pi_n
[/mm]
ist [mm] \{\pi_1,\ldots \pi_k\} [/mm] eine k-elementige Teilmenge von [mm] {1,\dlots , n\}.
[/mm]
Dabei haben wir
jede solche [mm] k!\cdot [/mm] (n-k)! oft gezaehlt (Anzahl aller Permutationen der Zahlen [mm] \pi_1,\ldots \pi_k [/mm]
mal Anzahl aller Permutationen von [mm] \pi_{k+1},\ldots \pi_n).
[/mm]
Gruss,
Mathias
|
|
|
| |
|
Hallo Karl!
Den Strang, den du bei googlegroups geöffnet hast, habe ich gelesen. Anscheinend ist dabei aber keine erschöpfende Antwort abgefallen.
Eine wirklich perfekte Antwort habe ich auch nicht, aber wenigstens etwas:
Ich denke, dass die Formel gerade die aus der Kombinatorik bekannte Formel für "ohne Reihenfolge, mit Wiederholung" ist. Das liegt daran:
Du wählst $N$ Zahlen zwischen $1$ und $M$ aus, manche evtl. doppelt. Die Reihenfolge spielt dabei keine Rolle, denn du sortierst deine Zahlen, wenn du fertig bist. Es ist also egal, welche zuerst gezogen wird.
Gruß, banachella
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:12 Mo 13.06.2005 | | Autor: | Stefan |
Liebe Kristine!
Deine Antwort ist richtig, aber war das nicht genau das, was hier im Folgenden in der Newsgroup von Horst Kraemer (der sowieso immer richtige Antworten gibt, was ich so verfolge) geschrieben wurde (ich schreibe das, weil du erwähntest die Antworten dort hätten nichts hergegeben):
Horst Kraemer 12 Jun. 19:47 Optionen anzeigen
Newsgroups: de.sci.mathematik
Von: Horst Kraemer <h-krae...@lycos.de> Nachrichten von diesem Autor suchen
Datum: Sun, 12 Jun 2005 19:47:28 +0200
Lokal: So 12 Jun. 2005 19:47
Betreff: Re: Kombinatorik-Problem
Antworten | Antwort an Autor | Weiterleiten | Drucken | Einzelne Nachricht | Original anzeigen | Missbrauch melden
[...]
Gesucht ist die Anzahl monotonen Abbildungen von {1,2,3,...N} nach
{1,2,3,...,M} (In der Orinalfragestellung nach {0,1,2,...,M-1}, aber
das ist dasselbe).
Hier hilft ein kleiner Trick. Betrachte statt der gesuchen N-Tupel die
N-Tupel, die dadurch entstehen, dass Du statt des N-Tupels
[mm] (x_1,x_2,x_3,...,x_N)
[/mm]
das Ersatz-N-Tupel
[mm] (x_1+0,x_2+1,x_3+2,...,x_N+N-1) [/mm]
betrachtest. Wenn das Orignal-N-Tupel aus {1,...,M-1} monoton ist, ist
das Ersatz-N-Tupel ein *streng* monotones N-Tupel aus {1,..,M+N-1} und
wenn umgekehrt [mm] (y1,y2,...,y_N) [/mm] ein streng monotones N-Tupel aus
{1,..,M+N-1} ist, ist
[mm] (y_1-0,y_2-1,y_3-2,...,y_N-(N-1)) [/mm]
monotones N-Tupel aus {1,..,M}. Aufgrund dieser Bijektion musst Du nur
die Anzahl der streng monotonen N-Tupel aus {1.2,...,M+N-1} zaehlen.
Die Anzahl der Letzteren ist bekanntlich die Anzahl der
N-Kombinationen aus einer (M+N-1)-Menge...
(Du suchst uebrigens die Anzahl der N-Kombinationen mit Wiederholungen
aus einer M-Menge).
--
Horst
Dadurch bleibt es ja trotzdem richtig.  Gleiches hatten uns Brigitte und ich auch schon einmal überlegt als so eine Frage von einem Studenten kam. Ich hatten den Beitrag leider bisher übersehen, sonst hätte ich längst darauf geantwortet.
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:02 Di 14.06.2005 | | Autor: | banachella |
Hallo Stefan!
Das sieht in der Tat schwer danach aus. Dann habe ich wohl doch zu flüchtig drüber gelesen...
Gruß, banachella
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:24 Mo 13.06.2005 | | Autor: | Karl_Pech |
Hallo Kristine, Hallo Stefan,
Danke für eure Hilfe! Ich habe gestern noch die Lösung für dieses Problem gefunden, indem ich ein Bißchen mit meinem Computeralgebrasystem rumprobiert habe (ich habe das gestern in der NG bereits erwähnt).
Ich habe für $N = [mm] 1,\dotsc,8$ [/mm] Summen gebildet und durch mein C.A.S. lösen lassen. Wenn man nun die entstandenen Polynome faktorisiert (ebenfalls durch mein C.A.S.), bemerkt man eine Gesetzmäßigkeit:
[m]\begin{gathered}
\sum\limits_{x_0 = 0}^{M - 1} 1 = M \hfill \\
\sum\limits_{x_0 = 0}^{M - 1} {\sum\limits_{x_1 = x_0 }^{M - 1} 1 } = \frac{{M\left( {M + 1} \right)}}
{2} \hfill \\
\sum\limits_{x_0 = 0}^{M - 1} {\sum\limits_{x_1 = x_0 }^{M - 1} {\sum\limits_{x_2 = x_1 }^{M - 1} 1 } } = \frac{{M\left( {M + 1} \right)\left( {M + 2} \right)}}
{6} \hfill \\
\sum\limits_{x_0 = 0}^{M - 1} {\sum\limits_{x_1 = x_0 }^{M - 1} {\sum\limits_{x_2 = x_1 }^{M - 1} {\sum\limits_{x_3 = x_2 }^{M - 1} 1 } } } = \frac{{M\left( {M + 1} \right)\left( {M + 2} \right)\left( {M + 3} \right)}}
{{24}} \hfill \\
\sum\limits_{x_0 = 0}^{M - 1} {\sum\limits_{x_1 = x_0 }^{M - 1} {\sum\limits_{x_2 = x_1 }^{M - 1} {\sum\limits_{x_3 = x_2 }^{M - 1} {\sum\limits_{x_4 = x_3 }^{M - 1} 1 } } } } = \frac{{M\left( {M + 1} \right)\left( {M + 2} \right)\left( {M + 3} \right)\left( {M + 4} \right)}}
{{120}} \hfill \\
\sum\limits_{x_0 = 0}^{M - 1} {\sum\limits_{x_1 = x_0 }^{M - 1} {\sum\limits_{x_2 = x_1 }^{M - 1} {\sum\limits_{x_3 = x_2 }^{M - 1} {\sum\limits_{x_4 = x_3 }^{M - 1} {\sum\limits_{x_5 = x_4 }^{M - 1} 1 } } } } } = \frac{{M\left( {M + 1} \right)\left( {M + 2} \right)\left( {M + 3} \right)\left( {M + 4} \right)\left( {M + 5} \right)}}
{{720}} \hfill \\
\vdots \hfill \\
\end{gathered}[/m]
Es fällt auf, daß im Zähler Faktoren gebildet werden, die dann laufend um 1 ansteigen und zwar immer bis [mm] $N-1\!$. [/mm] Ich wußte zuerst nicht, wie der Ausdruck im Nenner zu interpretieren war, bis ich bei der 6er-Summe 720 im Nenner rausbekam. In diesem Moment erinnerte ich mich, daß das eine Fakultät-Zahl ist, nämlich 6!. Die anderen Zahlen im Nenner waren auch Fakultäten. Offenbar hängt hier die Fakultät-Zahl mit der Verschachtelungstiefe der Summe zusammen: Also [mm] $N!\!$. [/mm] Also gilt für die [mm] $N\texttt{er-Summe}$:
[/mm]
[m]\begin{gathered}
\sigma \left( N \right): = \sum\limits_{x_0 = x_1 }^{M - 1} {\sum\limits_{x_1 = x_2 }^{M - 1} { \cdots \sum\limits_{x_{N - 1} = x_N }^{M - 1} 1 } } = \frac{{M\left( {M + 1} \right)* \cdots *\left( {M + N - 1} \right)}}
{{N!}} \hfill \\
= \frac{{\left( {M + N - 1} \right)!}}
{{\left( {M - 1} \right)!N!}} = \frac{{\left( {N + M - 1} \right)!}}
{{N!\left( {M - 1} \right)!}} = \frac{{\left( {N + M - 1} \right)!}}
{{N!\left( {\left( {N + M - 1} \right) - N} \right)!}} = {{N+M-1} \choose N} \hfill \\
\end{gathered}[/m]
Viele Grüße
Karl
![[user]](/images/smileys/user.gif "[user]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:47 Mo 13.06.2005 | | Autor: | Marc |
Hallo Karl!
> [m]\begin{gathered}
\sigma \left( N \right): = \sum\limits_{x_0 = x_1 }^{M - 1} {\sum\limits_{x_1 = x_2 }^{M - 1} { \cdots \sum\limits_{x_{N - 1} = x_N }^{M - 1} 1 } } = \frac{{M\left( {M + 1} \right)* \cdots *\left( {M + N - 1} \right)}}
{{N!}} \hfill \\
= \frac{{\left( {M + N - 1} \right)!}}
{{\left( {M - 1} \right)!N!}} = \frac{{\left( {N + M - 1} \right)!}}
{{N!\left( {M - 1} \right)!}} = \frac{{\left( {N + M - 1} \right)!}}
{{N!\left( {\left( {N + M - 1} \right) - N} \right)!}} = {{N+M-1} \choose N} \hfill \\
\end{gathered}[/m]
Nicht schlecht
Übrigens hat Horst Kraemer dieselbe Formel auf anderem Wege angegeben...
Viele Grüße,
Marc
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:15 Mo 13.06.2005 | | Autor: | Karl_Pech |
Hallo Marc,
> Übrigens hat Horst Kraemer dieselbe Formel auf anderem Wege angegeben...
Ja stimmt:
"Aufgrund dieser Bijektion musst Du nur die Anzahl der streng monotonen [mm] $N\texttt{-Tupel}$ [/mm] aus [mm] $\{1,2,\dotsc,M+N-1\}$ [/mm] zaehlen. Die Anzahl der Letzteren ist bekanntlich die Anzahl der [mm] $N\texttt{-Kombinationen}$ [/mm] aus einer [mm] $(M+N-1)\texttt{-Menge}\dotsc$
[/mm]
(Du suchst uebrigens die Anzahl der [mm] $N\texttt{-Kombinationen}$ [/mm] mit Wiederholungen aus einer [mm] $M\texttt{-Menge}$)."
[/mm]
Nur leider hatte ich Probleme seinen Ansatz zu verstehen. Also habe ich es selber nochmal versuchst und in diesem Falle einfach Glück gehabt.
Viele Grüße
Karl
|
|
|
|
![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]"){kind=small}
![[keineahnung]](/images/smileys/keineahnung.gif "[keineahnung]"){kind=small}
