Stirling Zahlen berechnen

[Codewalker]

Die folgende Funktion berechnet rekursiv die Stirling-Zahlen erster Art. Diese werden zur Berechnung der Anzahl unterschiedlicher Permutationen mit n Elementen in r Zykeln verwendet (Mehr Info: http://de.wikipedia.org/wiki/Stirling-Zahl)

Delphi-Quellcode:

function Stirling1(n, r: integer): integer;
begin
  if ((n = 0) and (r = 0)) or (n = r) then
  begin
    Result := 1;
    Exit;
  end;
  if ((n > 0) and (r = 0)) or ((n = 0) and (r > 0)) then
  begin
    Result := 0;
    Exit;
  end;
  Result := Stirling1(n - 1, r - 1) + (n - 1) * Stirling1(n - 1, r);
end;

Die Stirling-Zahlen zweiter Art beschreiben die Anzahl Anzahl der unterschiedlichen Möglichkeiten aus einer Menge mit n Elementen r nichtleere, disjunkte Teilmengen zu bilden.

Delphi-Quellcode:

function Stirling2(n, r: integer): integer;
begin
  if ((n = 0) and (r = 0)) or (n = r) then
  begin
    Result := 1;
    Exit;
  end;
  if ((n > 0) and (r = 0)) or ((n = 0) and (r > 0)) then
  begin
    Result := 0;
    Exit;
  end;
  Result := Stirling2(n-1,r-1)+r*Stirling2(n-1,r);
end;

Leider habe ich nur eine Definition der Stirling-Zahlen gefunden, die eine nicht-lineare Variante zur rekursiven Berechnung ermöglicht, sodass der Rechenaufwand mit großen Zahlen exponentiell steigt.

Stichwörter: Diskrete Strukturen Mengen Permutation Kombinatorik Rekursion

[edit=fkerber]Kleinen Fehler ausgebessert. Mfg, fkerber[/edit]