Lah-Zahlen Rechner

🔢 Verschiedene Darstellungen

Äquivalente mathematische Formulierungen der Lah-Zahlen:

\[L(n,k) = \frac{n!}{k!} \binom{n-1}{k-1} \quad \text{(Standard-Form)}\] \[L(n,k) = \frac{n!}{k!} \cdot \frac{(n-1)!}{(k-1)!(n-k)!} \quad \text{(Ausgeschrieben)}\] \[L(n,k) = \binom{n}{k} \cdot \frac{n!}{k!} \quad \text{(Alternative Form)}\] \[L(n,k) = \sum_{j=0}^k (-1)^j \binom{k}{j} j^n \quad \text{(Explizite Summe)}\]

🔄 Rekursionsformeln

Wichtige rekursive Beziehungen:

\[L(n,k) = (n-1+k) \cdot L(n-1,k-1) + L(n-1,k) \quad \text{(Hauptrekursion)}\] \[L(n,k) = \frac{n}{k} \cdot L(n-1,k-1) \quad \text{(Einfache Rekursion)}\] \[\text{Startwerte: } L(0,0) = 1, L(n,0) = 0 \text{ für } n > 0\] \[L(n,n) = n! \quad \text{(Diagonale)}\]

📊 Beziehung zu Stirling-Zahlen

Verbindung zu anderen kombinatorischen Zahlen:

\[\text{Stirling 2. Art: } S(n,k) = \frac{1}{k!} \sum_{j=0}^k (-1)^{k-j} \binom{k}{j} j^n\] \[\text{Beziehung: } L(n,k) = \binom{n}{k} \cdot k! \cdot S(n,k) \quad \text{(falsch!)}\] \[\text{Korrekt: } L(n,k) \text{ und } S(n,k) \text{ sind verwandt über:}\] \[x^{\overline{n}} = \sum_{k=0}^n L(n,k) x^k \quad \text{(Steigende Fakultät)}\]

📝 Beispiel 1: Grundberechnung L(4,2)

Aufgabe: Auf wie viele Arten kann man 4 Personen in 2 geordnete Gruppen aufteilen?
Lösung: Berechne L(4,2)
Berechnung:

\[L(4,2) = \frac{4!}{2!} \binom{3}{1} = \frac{24}{2} \cdot 3 = 12 \cdot 3 = 36\] \[\text{Verifikation: } L(4,2) = \frac{4!}{2!} \cdot \frac{3!}{1! \cdot 2!} = 12 \cdot \frac{6}{2} = 12 \cdot 3 = 36\]

Antwort: Es gibt 36 verschiedene geordnete Aufteilungen

📝 Beispiel 2: Extremfälle

Aufgabe: Berechne L(5,1), L(5,5) und L(5,0)
Bedeutung: Spezielle Fälle der Lah-Zahlen
Berechnung:

\[L(5,1) = \frac{5!}{1!} \binom{4}{0} = 120 \cdot 1 = 120\] \[L(5,5) = \frac{5!}{5!} \binom{4}{4} = 1 \cdot 1 = 1\] \[L(5,0) = 0 \quad \text{(per Definition für } n > 0\text{)}\] \[\text{Interpretation:}\] \[\text{L(5,1): Alle Elemente in einer geordneten Liste}\] \[\text{L(5,5): Jedes Element in eigenem Block}\]

Muster: L(n,1) = n!, L(n,n) = 1, L(n,0) = 0 für n > 0

📝 Beispiel 3: Rekursive Berechnung

Aufgabe: Berechne L(5,3) mit der Rekursionsformel
Rekursion: L(n,k) = (n-1+k)·L(n-1,k-1) + L(n-1,k)
Berechnung:

\[L(5,3) = (5-1+3) \cdot L(4,2) + L(4,3)\] \[= 7 \cdot L(4,2) + L(4,3)\] \[\text{Bekannt: } L(4,2) = 36, L(4,3) = 24\] \[L(5,3) = 7 \cdot 36 + 24 = 252 + 24 = 276\] \[\text{Verifikation mit Formel:}\] \[L(5,3) = \frac{5!}{3!} \binom{4}{2} = 20 \cdot 6 = 120 \text{ (Fehler in Rekursion!)}\] \[\text{Korrekte Rekursion: } L(5,3) = \frac{5}{3} \cdot 36 = 60\]

Achtung: Rekursionsformeln müssen sorgfältig angewendet werden

📊 Lah-Zahlen L(n,k) für kleine n und k

Muster: L(n,1) = n!, L(n,n) = 1, Randwerte = 0

🔗 Beziehungen zu anderen Zahlenfolgen

Wichtige Verbindungen der Lah-Zahlen:

\[\text{Stirling 2. Art: Verwandtschaft über Partitionen}\] \[\text{Binomialkoeffizienten: } L(n,k) = \frac{n!}{k!} \binom{n-1}{k-1}\] \[\text{Fakultäten: } L(n,1) = n!, L(n,n) = 1\] \[\text{Fibonacci-artige Rekursionen möglich}\]

📐 Erzeugende Funktionen

Analytische Eigenschaften der Lah-Zahlen:

\[\text{Exponentiell: } \sum_{n \geq k} L(n,k) \frac{x^n}{n!} = \frac{1}{k!} \left(\frac{x}{1-x}\right)^k\] \[\text{Binomial: } \sum_{k=0}^n L(n,k) x^k = x(x+1)(x+2)\cdots(x+n-1)\] \[\text{Steigende Fakultät: } x^{\overline{n}} = \sum_{k=0}^n L(n,k) x^k\]

💻 Code-Implementierungen

Effiziente Berechnung der Lah-Zahlen:

Python - Direkte Formel:
import math

def lah_number(n, k):
  """Berechnet L(n,k) = (n!/k!) * C(n-1,k-1)"""
  if k == 0:
    return 1 if n == 0 else 0
  if k > n or n == 0:
    return 0
  return (math.factorial(n) // math.factorial(k)) * math.comb(n-1, k-1)

Python - Rekursive Methode:
def lah_recursive(n, k):
  if k == 0: return 1 if n == 0 else 0
  if k > n: return 0
  if k == n: return 1
  return (n + k - 1) * lah_recursive(n-1, k-1) + lah_recursive(n-1, k)

Python - Dynamische Programmierung:
def lah_table(max_n):
  L = [[0]*(max_n+1) for _ in range(max_n+1)]
  L[0][0] = 1
  for n in range(1, max_n+1):
    for k in range(1, n+1):
      L[n][k] = (n + k - 1) * L[n-1][k-1] + L[n-1][k]
  return L

📊 JavaScript-Implementierung

Web-freundliche Implementierung:

JavaScript:
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

function binomial(n, k) {
  if (k > n) return 0;
  if (k === 0 || k === n) return 1;
  return factorial(n) / (factorial(k) * factorial(n - k));
}

function lahNumber(n, k) {
  if (k === 0) return n === 0 ? 1 : 0;
  if (k > n) return 0;
  return (factorial(n) / factorial(k)) * binomial(n - 1, k - 1);
}

// Beispiel:
console.log(lahNumber(5, 3)); // Ausgabe: 150

⚡ Komplexitätsüberlegungen

Effizienzaspekte verschiedener Ansätze:

\[\text{Direkte Formel: } O(\log n) \text{ mit effizienter Fakultät}\] \[\text{Rekursion: } O(2^n) \text{ ohne Memoization}\] \[\text{Dynamische Programmierung: } O(n^2) \text{ Zeit, } O(n^2) \text{ Speicher}\] \[\text{Tabellen-Vorberechnung: Optimal für mehrfache Abfragen}\]