Kombinatorik - n (geordnete) Tupel und die Summe

26.03.2014, 16:01	matrixstorm	Auf diesen Beitrag antworten »
Kombinatorik - n (geordnete) Tupel und die Summe Meine Frage: 1.) Wie viele n-tupel gibt es (x1....xn), wobei n aus den natuerlichen zahlen kommt, so dass: x1 + .. + xn = r ist, wobei r aus den natuerlichen zahlen ist (mit der 0) 2.) Wie viele n-tupel gibt es, wenn von dem Tupel (x1....xn) zusaetzlich gefordert wird, dass die xi (der Groesse nach) geordnet sind. Meine Ideen: 1.) ist ein Binominalkoeffizient, wie auch in http://www.matheboard.de/archive/432418/thread.html bereits erklaert. Aber wie bildet sich 2.) Die Loesung von 2 muss kleiner als die Loesung von 1 sein - ein Teiler ist es aber nicht. Besten Dank
29.03.2014, 12:31	HAL 9000	Auf diesen Beitrag antworten »
Bei 2) geht es um die Partitionsfunktion, allerdings mit einer Maximalzahl $\begin{eqnarray} n \end{eqnarray}$ an Summanden. In der Terminologie des Wikipedia-Beitrags wäre das $\begin{eqnarray} P(r+n,n) \end{eqnarray}$ (weil dort alle Summanden echt positiv sind). Eine explizite Formel dafür gibt es meines Wissens nicht, aber zumindest eine rekursive Berechnungsvorschrift: $\begin{eqnarray} P(r,n) = P(r-n,n) + P(r-1,n-1) \end{eqnarray}$ für $\begin{eqnarray} r>n>1 \end{eqnarray}$ mit Start- bzw. Randwerten $\begin{eqnarray} P(r,1) = 1 \end{eqnarray}$ für $\begin{eqnarray} r\geq 0 \end{eqnarray}$ $\begin{eqnarray} P(n,n) = 1 \end{eqnarray}$ für $\begin{eqnarray} n\geq 1 \end{eqnarray}$ $\begin{eqnarray} P(r,n) = 0 \end{eqnarray}$ für $\begin{eqnarray} 0\leq r<n \end{eqnarray}$ .

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »