Anzahl Permutationen? ==> Algorithmus / Formel gesucht

[Rolf b]

Ack, 2024 habe ich auch herausbekommen.

1. Analytisch (das, was ich Eddie geschickt habe)
2. Empirisch (habe die Aufgabe an Rasmus Lerdorf delegiert)

Zu 1: Ich formuliere meinen Text für Eddie hier nochmal neu.

Man hat 54mm in einem 2mm Raster, also 27 Rasterfelder (nummeriert von 1-27). Ich gebe die Position eines Pfeiles mit der Feldnummer an, die seine linke Seite belegt. Wenn also ein Pfeil auf Pos. 1 steht, belegt er die Felder 1+2. Die höchste Position, die Pfeil 1 belegen kann, ist die 22, weil 24+25 und 26+27 für die Pfeile 2 und 3 frei bleiben müssen. Pfeil 1 hat also 22 mögliche Positionen.

Steht Pfeil 1 auf Pos. 1, hat Pfeil 2 die Positionen 3-24 zur Verfügung. Auch das sind 22 mögliche Positionen. Steht Pfeil 2 auf Pos. 3, habe ich für Pfeil 3 die 22 Positionen von 5-26 verfügbar. Das ist die maximimale Beweglichkeit für Pfeil 3.

Schiebe ich Pfeil 2 auf Pos. 4 weiter, habe ich für Pfeil 3 nur noch 21 Positionen, bis zur Position 24 für Pfeil 2, wo Pfeil 3 nur noch eine Möglichkeit hat. D.h. während Pfeil 2 seine 22 möglichen Positionen durchläuft, ergeben sich durch Variation von Pfeil 3 22+21+20+...+1 Möglichkeiten. Steht Pfeil 1 weiter rechts, so dass Pfeil 2 nur J Möglichkeiten hat, ergeben sich entsprechend nur noch J + (J-1)+...+1 Möglichkeiten. Aus Notationsgründen betrachten wir das so, dass Pfeil 1 auf Pos. 22 beginnt und bis zur 1 läuft, dann habe ich für Pfeil 2 erst 1, dann 2, dann 3, etc, und schließlich 22 Möglichkeiten:

$$ anzahl = \sum_{J=1}^{22}\sum_{K=1}^{J} K $$

$$ = \sum_{J=1}^{22}\frac{J(J+1)}{2} = \frac{1}{2}\sum_{J=1}^{22}(J^2+J) = \frac{1}{2}(\sum_{J=1}^{22}J^2+\sum_{J=1}^{22}J)$$

$$ = \frac{1}{2}(\frac{22\cdot 23\cdot 45}{6}+\frac{22\cdot 23}{2})$$

$$ = \frac{1}{2}(3795+253) = \frac{4048}{2} = 2024$$

Dabei habe ich die bekannten Summenformeln für $$ \sum_{i=1}^{n} i $$ und $$ \sum_{i=1}^{n} i^2 $$ genutzt.

Zu 2: Rasmus Lerdorf zählt das so:

<?php
$total = 0;
for ($i=0; $i<22; $i++) {
   for ($j=$i+2; $j<24; $j++) {
      for ($k=$j+2; $k<26; $k++) {
         $total++;
      }
   }
}
echo "Finde $total Möglichkeiten";

Gibt auch 2024.

Rolf