Subfakultät Rechner

🎭 Grundlegende Eigenschaften

Wichtige mathematische Eigenschaften der Subfakultät:

\[\text{Definition: } !n = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!}\] \[\text{Rekursion: } !n = (n-1)(!(n-1) + !(n-2)) \text{ für } n \geq 2\] \[\text{Alternative: } !n = n \cdot !(n-1) + (-1)^n\] \[\text{Basis: } !0 = 1, \quad !1 = 0\] \[\text{Asymptotik: } !n \approx \frac{n!}{e} \text{ für große } n\]

🔄 Inklusions-Exklusion-Prinzip

Herleitung über Inklusions-Exklusion:

\[\text{Anzahl Permutationen mit Fixpunkten: } \sum_{k=1}^{n} (-1)^{k+1} \binom{n}{k} (n-k)!\] \[\text{Fixpunktfreie Permutationen: } !n = n! - \sum_{k=1}^{n} (-1)^{k+1} \binom{n}{k} (n-k)!\] \[= n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}\] \[\text{Rundungsformel: } !n = \left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor\]

📊 Wichtige Werte

Häufig verwendete Subfakultäten:

\[!0 = 1\] \[!1 = 0\] \[!2 = 1\] \[!3 = 2\] \[!4 = 9\] \[!5 = 44\] \[!6 = 265\] \[!7 = 1{.}854\] \[!10 = 1{.}334{.}961\]

📝 Beispiel 1: Das klassische Hutproblem

Aufgabe: n Personen geben ihre Hüte ab
Gegeben: 4 Personen mit verschiedenen Hüten
Berechnung:

\[\text{Anzahl Möglichkeiten, dass niemand seinen Hut erhält} = !4\] \[!4 = 4! \sum_{i=0}^{4} \frac{(-1)^i}{i!}\] \[= 24 \left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}\right)\] \[= 24 \times \frac{3}{8} = 9\]

Interpretation: Von 24 möglichen Hutverteilungen sind 9 völlig falsch

📝 Beispiel 2: Briefumschlag-Problem

Aufgabe: Briefe in falsche Umschläge
Szenario: 5 Briefe und 5 adressierte Umschläge
Berechnung:

\[\text{Wahrscheinlichkeit völlig falscher Zuordnung} = \frac{!5}{5!}\] \[\frac{!5}{5!} = \frac{44}{120} = \frac{11}{30} \approx 0.367\] \[\text{Asymptotisch: } \lim_{n \to \infty} \frac{!n}{n!} = \frac{1}{e} \approx 0.368\]

Anwendung: Etwa 36.8% aller Permutationen sind fixpunktfrei

📝 Beispiel 3: Rencontres-Problem

Aufgabe: Kartenspiel ohne Treffer
Gegeben: 52 Karten werden einzeln aufgedeckt
Berechnung:

\[\text{Wahrscheinlichkeit für keine Übereinstimmung} \approx \frac{1}{e}\] \[\text{Erwartete Anzahl Übereinstimmungen} = 1\] \[\text{Varianz der Übereinstimmungen} = 1\] \[\text{Für große } n: P(\text{keine Treffer}) \to \frac{1}{e} \approx 0.368\]

Bedeutung: Überraschend konstante Wahrscheinlichkeit unabhängig von n

💻 Code-Implementierungen

Effiziente Implementierung der Subfakultät:

Python:
import math

def subfactorial(n):
  """Berechnet die Subfakultät !n (Derangements)"""
  if n < 0:
    raise ValueError("n muss >= 0 sein")
  if n == 0 or n == 1:
    return 1 if n == 0 else 0
  
  # Rekursive Methode
  return (n - 1) * (subfactorial(n - 1) + subfactorial(n - 2))

def subfactorial_iterative(n):
  """Iterative Implementierung"""
  if n == 0: return 1
  if n == 1: return 0
  
  prev_prev = 1 # !0
  prev = 0 # !1
  
  for i in range(2, n + 1):
    current = (i - 1) * (prev + prev_prev)
    prev_prev, prev = prev, current
  
  return prev

def subfactorial_formula(n):
  """Mit Inklusions-Exklusions-Formel"""
  if n == 0: return 1
  
  factorial_n = math.factorial(n)
  sum_term = sum((-1)**i / math.factorial(i) for i in range(n + 1))
  return int(factorial_n * sum_term)

def subfactorial_approximation(n):
  """Näherung für große n"""
  if n == 0: return 1
  return round(math.factorial(n) / math.e)

JavaScript:
function subfactorial(n) {
  if (n < 0) throw new Error("n muss >= 0 sein");
  if (n === 0) return 1;
  if (n === 1) return 0;
  
  let prev2 = 1, prev1 = 0;
  for (let i = 2; i <= n; i++) {
    let current = (i - 1) * (prev1 + prev2);
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

C++:
#include <iostream>
#include <vector>
long long subfactorial(int n) {
  if (n < 0) throw std::invalid_argument("n must be >= 0");
  if (n == 0) return 1;
  if (n == 1) return 0;
  
  long long prev2 = 1, prev1 = 0;
  for (int i = 2; i <= n; ++i) {
    long long current = (i - 1) * (prev1 + prev2);
    prev2 = prev1;
    prev1 = current;
  }
  return prev1;
}

🎯 Hutproblem-Simulator

Simulation des klassischen Hutproblems:

Python Hutproblem-Simulator:
import random
import math

class HatProblemSimulator:
  @staticmethod
  def subfactorial(n):
    """Exakte Subfakultät"""
    if n == 0: return 1
    if n == 1: return 0
    prev2, prev1 = 1, 0
    for i in range(2, n + 1):
      current = (i - 1) * (prev1 + prev2)
      prev2, prev1 = prev1, current
    return prev1
  
  @staticmethod
  def simulate_hat_problem(n, trials=100000):
    """Simuliert das Hutproblem"""
    derangements = 0
    
    for _ in range(trials):
      # Zufällige Permutation
      permutation = list(range(n))
      random.shuffle(permutation)
      
      # Prüfe auf Fixpunkte
      is_derangement = all(permutation[i] != i for i in range(n))
      if is_derangement:
        derangements += 1
    
    return derangements
  
  @staticmethod
  def analyze_convergence(max_n=10, trials=10000):
    """Analysiert Konvergenz zu 1/e"""
    print("n\tExakt\tSimulation\tVerhältnis\t1/e")
    print("-" * 50)
    
    for n in range(2, max_n + 1):
      exact = HatProblemSimulator.subfactorial(n)
      simulated = HatProblemSimulator.simulate_hat_problem(n, trials)
      exact_ratio = exact / math.factorial(n)
      simulated_ratio = simulated / trials
      
      print(f"{n}\t{exact}\t{simulated}\t{exact_ratio:.4f}\t{1/math.e:.4f}")

# Verwendung
simulator = HatProblemSimulator()
print(f"!5 = {simulator.subfactorial(5)}")
print(f"Simulation für n=5: {simulator.simulate_hat_problem(5)}")
simulator.analyze_convergence()

🎯 Statistische Analyse

Asymptotische Eigenschaften und Approximationen:

Python Statistische Analyse:
import math
import numpy as np
import matplotlib.pyplot as plt

class DerangementAnalysis:
  @staticmethod
  def subfactorial(n):
    if n == 0: return 1
    if n == 1: return 0
    prev2, prev1 = 1, 0
    for i in range(2, n + 1):
      current = (i - 1) * (prev1 + prev2)
      prev2, prev1 = prev1, current
    return prev1
  
  @staticmethod
  def rounding_formula(n):
    """Rundungsformel: round(n!/e)"""
    return round(math.factorial(n) / math.e)
  
  @staticmethod
  def probability_no_fixed_points(n):
    """Wahrscheinlichkeit für keine Fixpunkte"""
    return DerangementAnalysis.subfactorial(n) / math.factorial(n)
  
  @staticmethod
  def error_analysis(max_n=15):
    """Fehleranalyse der Rundungsformel"""
    print("n\tExakt\tRundung\tFehler\tP(keine Fixpunkte)")
    print("-" * 60)
    
    for n in range(1, max_n + 1):
      exact = DerangementAnalysis.subfactorial(n)
      rounded = DerangementAnalysis.rounding_formula(n)
      error = abs(exact - rounded)
      prob = DerangementAnalysis.probability_no_fixed_points(n)
      
      print(f"{n}\t{exact}\t{rounded}\t{error}\t{prob:.6f}")
    
    print(f"\n1/e ≈ {1/math.e:.6f}")

# Analyse durchführen
analysis = DerangementAnalysis()
analysis.error_analysis()

# Konvergenz visualisieren
n_values = range(1, 21)
probabilities = [analysis.probability_no_fixed_points(n) for n in n_values]
target = [1/math.e] * len(n_values)

plt.figure(figsize=(10, 6))
plt.plot(n_values, probabilities, 'bo-', label='P(!n/n!)')
plt.plot(n_values, target, 'r--', label='1/e ≈ 0.368')
plt.xlabel('n')
plt.ylabel('Wahrscheinlichkeit')
plt.title('Konvergenz der Derangement-Wahrscheinlichkeit zu 1/e')
plt.legend()
plt.grid(True)
plt.show()