Kombinatorik mit Nebenbedingungen

19.04.2010, 07:54

produkt

Kombinatorik mit Nebenbedingungen

guten morgen!

meine frage bezieht sich einerseits darauf, in welches gebiet das problem einzuorden ist und natürlich auch, ob es da lösungsansätze gibt.

es soll kapital auf verschiedene positionen verteilt werden. von diesen positionen kann es sehr viele geben, beispielsweise n. dabei wird in bestimmten konstanten schritten umgeschichtet, beispielsweise in 5%, also 0.05 und die summe aller positionen muss genau 1 ergeben. folgend noch ein schema, da meine beschreibung nicht über jeden zweifel erhaben ist:-)

1 0 0 ... 0
0.95 0.05 0 ... 0
0.95 0 0.05 ... 0
...
0 0 0 ... 1

nun ist die frage, wie ich die anzahl der möglichkeiten berechnen kann? und wo solche probleme behandelt werden? bei einem etwas primitiven zeichenversuch :-) bekam ich eine teleskopsumme, nur war da n zu klein gewählt, also im beispiel von oben kleiner als 20 (1/0.05). wenn es grösser ist, stimmt es nicht mehr. bei allen kombinatorischen versuchen kam ich nicht mit der nebenbedingung klar...

könnt ihr mir da einen tipp geben? danke schon mal für die hilfe...

19.04.2010, 09:32

Huggy

Auf diesen Beitrag antworten »

RE: Kombinatorik mit Nebenbedingungen? wohin damit?
Dein Kapital wird in k gleich große Portionen aufgeteilt. Bei deinem Beispiel ist k = 20. Diese k Portionen sind jetzt auf n Positionen zu verteilen. In deiner ersten Zeile hast du alle 20 Portionen auf die Position 1 gegeben. In deiner zweiten Zeile hat Position 1 19 Portionen und Position 2 eine Portion bekommen usw.

Es geht also um das Problem, wieviele Möglichkeiten es gibt k Objekte auf n Positionen zu verteilen, wenn jede Position auch mehrere Objekte bekommen kann. Die Lösung lautet:

$\begin{eqnarray*} \binom {n+k-1} k \end{eqnarray*}$

Das gehört zur elementaren Kombinatorik. Die Formel findest du meist unter dem Stichwort Kombination mit Zurücklegen oder Kombination mit Wiederholung.

19.04.2010, 09:44

produkt

Auf diesen Beitrag antworten »

RE: Kombinatorik mit Nebenbedingungen? wohin damit?
hi huggy

danke für deine antwort. scheint bis jetzt zu stimmen:-), sonst komme ich wieder hierher zurück. wird der "nebenbedingung" in dem fall mit der elementmenge rechnung getragen, seh ich das richtig? also mit den 1/0.05 = 20 elementen... und danke für die einordnung!

danke nochmals, schönen tag noch!

19.04.2010, 09:51

Huggy

Auf diesen Beitrag antworten »

RE: Kombinatorik mit Nebenbedingungen? wohin damit?

Zitat:

Original von produkt
wird der "nebenbedingung" in dem fall mit der elementmenge rechnung getragen, seh ich das richtig? also mit den 1/0.05 = 20 elementen...

So ist es.

11.04.2017, 20:46

wolfgangv

Auf diesen Beitrag antworten »

RE: Kombinatorik mit Nebenbedingungen? wohin damit?
Die Antwort war da und die Aufgabe ist sehr interessant. Wir haben eine Fortsetzung des Problems.
Die Aufteilung auf die Positionen ist wie beschrieben und die Ressource konstant. Aber zusaätzlich soll jede folgende Position mehr als die vorige bekommen. Wie viel muss man mit dieser Einschränkung abziehen?
Kann jemand helfen?

11.04.2017, 21:31

HAL 9000

Auf diesen Beitrag antworten »

Eine brauchbare explizite Formel für diesen Fall kannst du vergessen - was rekursives ist indes sehr gut machbar. Das läuft so ähnlich wie hier bei dem $\begin{align*} P(n,k) \end{align*}$ der Partitionsfunktion.

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

Bezeichnen wir mit $\begin{align*} Q(k,n) \end{align*}$ die Anzahl der $\begin{align*} n \end{align*}$ -Tupel $\begin{align*} (m_1,m_2,\ldots,m_n) \end{align*}$ ganzer Zahlen mit $\begin{align*} m_1+\ldots+m_n=k \end{align*}$ sowie $\begin{align*} 0\leq m_1<m_2<\ldots<m_n \end{align*}$ . Dann ist für beliebige ganze Zahlen $\begin{align*} k,n \end{align*}$ mit $\begin{align*} n\geq 1 \end{align*}$

$\begin{align*} Q(k,n) = \begin{cases} 1 &\;\mbox{für}\; n=1,\,k\geq 0,\\ 0 &\;\mbox{für}\; k<\frac{n(n-1)}{2},\\ Q(k-n,n) + Q(k-n+1,n-1) &\;\mbox{sonst} .\end{cases} \end{align*}$

Die letzte Zeile ist die eigentliche Rekursion, die ersten beiden Zeilen stellen Abbruchbedingungen dar.

Für kleine feste $\begin{align*} n \end{align*}$ kann man noch versuchen, explizite Formeln zu entwickeln, die aber zunehmend komplizierte Gestalt haben. Für $\begin{align*} n=1 \end{align*}$ ist es noch trivial (siehe erste Zeile). Für $\begin{align*} n=2 \end{align*}$ bekommen wir

$\begin{align*} Q(k,2) = Q(k-2,2) + 1 = Q(k-4,2) + 2 = \ldots = Q\left(k-2\left\lfloor \frac{k}{2}\right\rfloor, 2 \right) + \left\lfloor \frac{k}{2}\right\rfloor = \left\lfloor \frac{k+1}{2}\right\rfloor \end{align*}$ .

Für $\begin{align*} n=3 \end{align*}$ ergibt eine schon längere Rechnung $\begin{align*} Q(k,3) = \left\lfloor \frac{k^2+3}{12} \right\rfloor \end{align*}$ , bei $\begin{align*} n=4 \end{align*}$ dann $\begin{align*} Q(k,4) = \left\lfloor \frac{2k^3-6k^2-9(1-(-1)^k)k+72}{288} \right\rfloor \end{align*}$ , und für $\begin{align*} n=5 \end{align*}$ wirds langsam ungemütlich...

Zur obigen Partitionsfunktion mit fester Summandenzahl besteht der Zusammenhang $\begin{align*} Q(k,n) = P\left(k-\frac{n(n-3)}{2},n\right) \end{align*}$ .

26.08.2017, 08:43

HAL 9000

Auf diesen Beitrag antworten »

Kürzlich bin ich auf eine Problemstellung aufmerksam geworden, die nach kurzer Überlegung auch auf eben diese Partitionsfunktion $\begin{align*} P(n,k) \end{align*}$ zurückzuführen ist:

Zitat:

Es bezeichne $\begin{align*} R(k,n) \end{align*}$ die Anzahl aller $\begin{align*} k \end{align*}$ -Tupel nichtnegativer ganzer Zahlen $\begin{align*} (a_1,\ldots,a_k) \end{align*}$ mit $\begin{align*} \sum_{i=1}^k ia_i = n \end{align*}$ . Dann ist $\begin{align*} R(k,n) = P(n+k,k) \end{align*}$ .

Begründung:

$\begin{align*} n = \sum_{i=1}^k \sum_{j=1}^i a_i = \sum_{j=1}^k \sum_{i=j}^k a_i \end{align*}$

$\begin{align*} n+k = \sum_{j=1}^k \left(1+\sum_{i=j}^k a_i\right) \end{align*}$

$\begin{align*} b_j:= 1+\sum_{i=j}^k a_i \end{align*}$

$\begin{align*} j=1,\ldots,k \end{align*}$

$\begin{align*} n+k \end{align*}$

$\begin{align*} b_1\geq b_2\geq \ldots\geq b_k \end{align*}$

$\begin{align*} (b_1,\ldots,b_k) \end{align*}$

$\begin{align*} a_j:=b_j-b_{j+1} \end{align*}$

$\begin{align*} j=1,\ldots,k-1 \end{align*}$

$\begin{align*} a_k:=b_k-1 \end{align*}$

$\begin{align*} k \end{align*}$

$\begin{align*} (a_1,\ldots,a_k) \end{align*}$

$\begin{align*} R(k,n)=P(n+k,k) \end{align*}$

Tatsächlich ist mir dieser Zusammenhang aufgefallen, als ich bei Aufstellung einer Rekursionsfunktion für $\begin{align*} R(k,n) \end{align*}$ auf eine frappierende Ähnlichkeit zu der von $\begin{align*} P(n,k) \end{align*}$ gestoßen bin. Über den obigen Zusammenhang lässt sich ja dann auch sofort eine Rekursionsformel für $\begin{align*} R \end{align*}$ aus der von $\begin{align*} P \end{align*}$ ableiten.

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

Eine damit verbundene Fragestellung:

Zitat:

Es seien $\begin{align*} n,k \end{align*}$ vorgegebene positive ganze Zahlen. Wieviel Tupel $\begin{align*} (c_1,\ldots,c_m) \end{align*}$ (die Größe $\begin{align*} m \end{align*}$ ist dabei variabel, d.h., nicht von vornherein festgelegt) von Zahlen aus $\begin{align*} \{1,\ldots,k\} \end{align*}$ mit der Eigenschaft $\begin{align*} \sum_{j=1}^m c_j = n \end{align*}$ gibt es?

Wieso "verbunden"? Nun, bei vorgegebenen $\begin{align*} i\in\{1,\ldots,k\} \end{align*}$ kann man die Anzahl aller $\begin{align*} c_j \end{align*}$ in einem solchen Tupel mit $\begin{align*} c_j=i \end{align*}$ mit dem Wert $\begin{align*} a_i \end{align*}$ in der vorigen Aufgabe identifizieren. Der Unterschied hier ist, dass die Reihenfolge eine Rolle spielt, d.h., wo die Indizes $\begin{align*} j \end{align*}$ mit $\begin{align*} c_j=i \end{align*}$ überall liegen. Augenzwinkern

Ist $\begin{align*} f_k(n) \end{align*}$ die gesuchte Anzahl, so ergibt sich via $\begin{align*} \sum_{j=2}^m c_j = n-c_1 \end{align*}$ der einfache Rekursionszusammenhang $\begin{align*} f_k(n) = \sum_{c=1}^k f_k(n-c) \end{align*}$ für alle $\begin{align*} n\geq 1 \end{align*}$ mit Start $\begin{align*} f_k(0)=1 \end{align*}$ sowie $\begin{align*} f_k(n)=0 \end{align*}$ für $\begin{align*} n<0 \end{align*}$ . (Das bedeutet dann auch $\begin{align*} f_k(n) = 2f_k(n-1)-f_k(n-k-1) \end{align*}$ für alle $\begin{align*} n\geq 2 \end{align*}$ .)

Übrigens ist dieses Prinzip gar nicht an die konkrete Struktur der Menge der auswählbaren Elemente gebunden: Ersetzt man $\begin{align*} \{1,\ldots,k\} \end{align*}$ durch eine beliebige Menge $\begin{align*} C \end{align*}$ positiver ganzer Zahlen und fordert entsprechend stattdessen $\begin{align*} c_j\in C \end{align*}$ , so ist die Anzahl analog berechenbar via $\begin{align*} f_C(n) = \sum_{c\in C} f_C(n-c) \end{align*}$ für alle $\begin{align*} n\geq \min C \end{align*}$ und vergleichbaren Startbedingungen wie oben, genauer: $\begin{align*} f_C(n)=0 \end{align*}$ für $\begin{align*} n<\min C \end{align*}$ mit Ausnahme von $\begin{align*} f_C(0)=1 \end{align*}$ .

$\begin{align*} \begin{array}{|r|r|r|r|r|r|}\hline n & R(1,n) & R(2,n) & R(3,n) & R(4,n) & f_4(n) \hline 0 & 1 & 1 & 1 & 1 & 1 1 & 1 & 1 & 1 & 1 & 1 2 & 1 & 2 & 2 & 2 & 2 3 & 1 & 2 & 3 & 3 & 4 4 & 1 & 3 & 4 & 5 & 8 5 & 1 & 3 & 5 & 6 & 15 6 & 1 & 4 & 7 & 9 & 29 7 & 1 & 4 & 8 & 11 & 56 8 & 1 & 5 & 10 & 15 & 108 9 & 1 & 5 & 12 & 18 & 208 10 & 1 & 6 & 14 & 23 & 401 11 & 1 & 6 & 16 & 27 & 773 12 & 1 & 7 & 19 & 34 & 1490 13 & 1 & 7 & 21 & 39 & 2872 14 & 1 & 8 & 24 & 47 & 5536 15 & 1 & 8 & 27 & 54 & 10671 16 & 1 & 9 & 30 & 64 & 20569 17 & 1 & 9 & 33 & 72 & 39648 18 & 1 & 10 & 37 & 84 & 76424 \hline\end{array} \end{align*}$

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

Für die genannten Anzahlen kann man auch erzeugende Funktionen angeben, manche (wie der leider lange nicht mehr gesichtete Mystic) bevorzugen ja das:

$\begin{align*} \sum_{n=0}^{\infty} R(k,n) x^n = \frac{1}{\displaystyle\prod\limits_{i=1}^k (1-x^i)} \end{align*}$ und $\begin{align*} \sum_{n=0}^{\infty} f_C(n) x^n = \frac{1}{1-\displaystyle\sum\limits_{c\in C} x^c} \end{align*}$ .

27.08.2017, 20:04

HAL 9000

Auf diesen Beitrag antworten »

Ergänzend noch ein paar explizite Darstellungen für einige der genannten Anzahlen:

$\begin{align*} R(2,n) = \frac{1}{4}\left( 2n+3+(-1)^n \right) \end{align*}$

$\begin{align*} R(3,n) = \frac{1}{72}\left( 6n^2+36n+47+9(-1)^n+16\cos\left( \frac{2\pi}{3}n\right) \right) \end{align*}$

$\begin{align*} R(4,n) = \frac{1}{288}\left( 2n^3+30n^2+135n+175 + 9(n+5)(-1)^n + 32\cos\left( \frac{2\pi}{3}n\right) + \frac{32}{\sqrt{3}}\sin\left( \frac{2\pi}{3}n\right) + 36\cos\left( \frac{\pi}{2}n\right) \right) \end{align*}$

$\begin{align*} R(5,n) = \frac{1}{86400} \left( 30n^4+900n^3+9300n^2+38250n+50651+675(2n+15)(-1)^n+6400\cos\left( \frac{2\pi}{3}n\right)+5400\cos\left( \frac{\pi}{2}n\right)+5400\sin\left( \frac{\pi}{2}n\right)+6912\cos\left( \frac{2\pi}{5}n\right)+6912\cos\left( \frac{4\pi}{5}n\right) \right) \end{align*}$

Wirklich handlich sind die also nicht, und es wird bei $\begin{align*} R(k,n) \end{align*}$ mit wachsendem $\begin{align*} k \end{align*}$ immer schlimmer... smile

Neue Frage »

Antworten »

Kombinatorik mit Nebenbedingungen

Verwandte Themen