Anzahl Permutationen? ==> Algorithmus / Formel gesucht

[Matthias Apsel]

Hallo Rolf b,

Ich verspüre beim Verdauen dieses Konstrukts aber eine Korinthe, die mir Blähungen bereitet und die ich darum gerne auskacken würde: Ich vermute, dass Du doppelt moppelst, wenn Du sowohl unter dem Summenzeichen als auch über dem Summenzeichen (b-1) herausrechnest. Grund für meine Vermutung: Die Summen sollten immer mit i=1 starten, sonst addierst Du in der Extremposition, wo alle Pfeile am rechten Rand stehen, zu hohe Werte.

Ich denke nicht. Bei der unteren Summationsgrenze wird (b-1) addiert, das heißt, es werden Summanden weggelassen, bei der oberen Grenze wird (b-1) subtrahiert, das heißt es werden ebenfalls Summanden weggelassen.

Schaun mer mal:

Ja, es ist falsch, man muss bis n-b summieren und auch nur +b rechnen. In meiner ersten Variante bin ich schon von einer reduzierten Anzahl (mögliche Slots, hier 26) ausgegangen. Daher der Fehler

n ist die Anzahl der vorhandenen Slots, hier 28
k die Anzahl der zu platzierenden Items und hier 3
b die Anzahl der durch ein Item blockierten Slots, hier 2

$$\sum_{i_1 = 1}^{26} \left(\sum_{i_2 = i_1+2}^{26} \left(\sum_{i_3 = i_2+2}^{26} i_3\right)\right) = 2024$$

Korrigiert muss es also heißen

$$\sum_{i_1 = 1}^{n-b} \left(\sum_{i_2 = i_1+b}^{n-b} \dotsc \left(\sum_{i_k = i_{k-1}+b}^{n-b} i_k\right)\right)$$

Sieht doch gleich viel einfacher aus. ;-)

Bis demnächst
Matthias