Kombinationen Rechner

🎯 Grundlegende Eigenschaften

Wichtige mathematische Eigenschaften von Kombinationen:

\[\text{Ohne Wiederholung: } C(n,k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}\] \[\text{Mit Wiederholung: } C(n+k-1,k) = \binom{n+k-1}{k} = \frac{(n+k-1)!}{(n-1)!k!}\] \[\text{Symmetrie: } C(n,k) = C(n,n-k)\] \[\text{Pascal'sche Identität: } C(n,k) = C(n-1,k-1) + C(n-1,k)\] \[\text{Beziehung zu Permutationen: } P(n,k) = k! \times C(n,k)\]

🎯 Unterschied: Kombination vs. Permutation

Abgrenzung zu Permutationen:

\[\text{Kombination (Reihenfolge unwichtig): } C(n,k) = \frac{n!}{k!(n-k)!}\] \[\text{Permutation (Reihenfolge wichtig): } P(n,k) = \frac{n!}{(n-k)!}\] \[\text{Beziehung: } P(n,k) = k! \times C(n,k)\] \[\text{Beispiel: } C(5,3) = 10, \quad P(5,3) = 60, \quad 60 = 3! \times 10\]

📊 Wichtige Werte

Häufig verwendete Kombinationen:

\[\text{Ohne Wiederholung:}\] \[C(5,2) = \binom{5}{2} = 10\] \[C(7,3) = \binom{7}{3} = 35\] \[C(10,4) = \binom{10}{4} = 210\] \[\text{Mit Wiederholung:}\] \[C(3+2-1,2) = C(4,2) = 6\] \[C(4+3-1,3) = C(6,3) = 20\] \[C(5+4-1,4) = C(8,4) = 70\]

📝 Beispiel 1: Lotto "6 aus 49"

Aufgabe: Gewinnwahrscheinlichkeit beim Lotto
Gegeben: 6 Zahlen aus 49 möglichen auswählen
Berechnung:

\[\text{Anzahl Kombinationen} = C(49,6)\] \[C(49,6) = \frac{49!}{6!(49-6)!} = \frac{49!}{6! \times 43!}\] \[= \frac{49 \times 48 \times 47 \times 46 \times 45 \times 44}{6!}\] \[= \frac{10{.}068{.}347{.}520}{720} = 13{.}983{.}816\]

Interpretation: Gewinnwahrscheinlichkeit = 1 : 13.983.816 ≈ 0,000007%

📝 Beispiel 2: Teamauswahl

Aufgabe: 5er-Team aus 12 Bewerbern auswählen
Szenario: Reihenfolge der Auswahl unwichtig
Berechnung:

\[\text{Anzahl Möglichkeiten} = C(12,5)\] \[C(12,5) = \frac{12!}{5!(12-5)!} = \frac{12!}{5! \times 7!}\] \[= \frac{12 \times 11 \times 10 \times 9 \times 8}{5!}\] \[= \frac{95{.}040}{120} = 792\]

Anwendung: 792 verschiedene Teams können gebildet werden

📝 Beispiel 3: Pizza-Beläge mit Wiederholung

Aufgabe: 3 Beläge aus 4 verfügbaren Sorten
Gegeben: Mehrfache Auswahl derselben Sorte erlaubt
Berechnung:

\[\text{Mit Wiederholung: } C(n+k-1,k) = C(4+3-1,3) = C(6,3)\] \[C(6,3) = \frac{6!}{3!(6-3)!} = \frac{6!}{3! \times 3!}\] \[= \frac{6 \times 5 \times 4}{3!} = \frac{120}{6} = 20\] \[\text{Ohne Wiederholung wären es: } C(4,3) = 4\]

Bedeutung: Mit Wiederholung ergeben sich 20 statt 4 Kombinationen

💻 Code-Implementierungen

Effiziente Implementierung von Kombinationen:

Python:
import math
from itertools import combinations, combinations_with_replacement

def combination_count(n, k, with_replacement=False):
  """Berechnet C(n,k) mit oder ohne Wiederholung"""
  if with_replacement:
    # C(n+k-1, k)
    return math.factorial(n + k - 1) // (math.factorial(n - 1) * math.factorial(k))
  else:
    # C(n, k)
    if k > n or k < 0:
      return 0
    return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))

def combination_efficient(n, k):
  """Effiziente Berechnung ohne vollständige Fakultäten"""
  if k > n or k < 0:
    return 0
  if k == 0 or k == n:
    return 1
  
  # Nutze Symmetrie: C(n,k) = C(n,n-k)
  k = min(k, n - k)
  
  result = 1
  for i in range(k):
    result = result * (n - i) // (i + 1)
  return result

def generate_combinations(items, k, with_replacement=False):
  """Generiert alle k-Kombinationen einer Liste"""
  if with_replacement:
    return list(combinations_with_replacement(items, k))
  else:
    return list(combinations(items, k))

# Mit itertools (Python standard library)
from itertools import combinations
result = list(combinations([1, 2, 3, 4], 2))
print(f"C(4,2) Kombinationen: {result}")

JavaScript:
function combinationCount(n, k, withReplacement = false) {
  if (withReplacement) {
    return factorial(n + k - 1) / (factorial(n - 1) * factorial(k));
  } else {
    if (k > n || k < 0) return 0;
    if (k === 0 || k === n) return 1;
    
    k = Math.min(k, n - k); // Symmetrie nutzen
    
    let result = 1;
    for (let i = 0; i < k; i++) {
      result = result * (n - i) / (i + 1);
    }
    return Math.round(result);
  }
}

function generateCombinations(arr, k) {
  if (k === 0) return [[]];
  if (k > arr.length) return [];
  
  const result = [];
  for (let i = 0; i <= arr.length - k; i++) {
    const rest = generateCombinations(arr.slice(i + 1), k - 1);
    for (const comb of rest) {
      result.push([arr[i], ...comb]);
    }
  }
  return result;
}

C++:
#include <iostream>
#include <vector>

long long combinationCount(int n, int k) {
  if (k > n || k < 0) return 0;
  if (k == 0 || k == n) return 1;
  
  k = std::min(k, n - k); // Symmetrie nutzen
  
  long long result = 1;
  for (int i = 0; i < k; ++i) {
    result = result * (n - i) / (i + 1);
  }
  return result;
}

🎯 Erweiterte Kombinatorik-Klasse

Umfassende Kombinations-Berechnungen:

Python Kombinatorik-Klasse:
import math
from itertools import combinations, combinations_with_replacement

class CombinationCalculator:
  @staticmethod
  def simple_combination(n, k):
    """C(n,k) = n!/(k!(n-k)!)"""
    if k > n or k < 0: return 0
    if k == 0 or k == n: return 1
    k = min(k, n - k) # Symmetrie nutzen
    result = 1
    for i in range(k):
      result = result * (n - i) // (i + 1)
    return result
  
  @staticmethod
  def combination_with_repetition(n, k):
    """C(n+k-1,k) = (n+k-1)!/((n-1)!k!)"""
    return CombinationCalculator.simple_combination(n + k - 1, k)
  
  @staticmethod
  def multinomial_coefficient(n, *groups):
    """Multinomialkoeffizient: n!/(n1! * n2! * ... * nk!)"""
    if sum(groups) != n:
      raise ValueError("Summe der Gruppen muss n entsprechen")
    result = math.factorial(n)
    for group_size in groups:
      result //= math.factorial(group_size)
    return result
  
  @staticmethod
  def pascal_triangle(n):
    """Erzeugt Pascal'sches Dreieck bis Zeile n"""
    triangle = []
    for i in range(n + 1):
      row = []
      for j in range(i + 1):
        row.append(CombinationCalculator.simple_combination(i, j))
      triangle.append(row)
    return triangle
  
  @staticmethod
  def catalan_number(n):
    """Catalan-Zahl: C_n = C(2n,n)/(n+1)"""
    return CombinationCalculator.simple_combination(2 * n, n) // (n + 1)
  
  @staticmethod
  def generate_all_combinations(items, k, with_replacement=False):
    """Generiert alle Kombinationen"""
    if with_replacement:
      return list(combinations_with_replacement(items, k))
    else:
      return list(combinations(items, k))

# Beispiele
calc = CombinationCalculator()
print(f"C(7,3) = {calc.simple_combination(7, 3)}") # 35
print(f"C(4+3-1,3) = {calc.combination_with_repetition(4, 3)}") # 20
print(f"Multinomial(6;2,2,2) = {calc.multinomial_coefficient(6, 2, 2, 2)}") # 90
print(f"Catalan(4) = {calc.catalan_number(4)}") # 14

# Pascal'sches Dreieck
triangle = calc.pascal_triangle(5)
for i, row in enumerate(triangle):
  print(f"Zeile {i}: {row}")

🎯 Wahrscheinlichkeits-Simulator

Simulation praktischer Kombinationsprobleme:

Python Wahrscheinlichkeits-Simulator:
import random
import math
from collections import Counter

class ProbabilitySimulator:
  @staticmethod
  def lottery_probability(total_numbers, drawn_numbers, your_numbers):
    """Berechnet Lotto-Gewinnwahrscheinlichkeiten"""
    total_combinations = math.factorial(total_numbers) // (
      math.factorial(drawn_numbers) * math.factorial(total_numbers - drawn_numbers))
    
    print(f"Lotto {drawn_numbers} aus {total_numbers}:")
    print(f"Gesamte Kombinationen: {total_combinations:,}")
    print(f"Gewinnwahrscheinlichkeit: 1 : {total_combinations:,}")
    print(f"Prozentual: {100/total_combinations:.10f}%")
    
    return 1 / total_combinations
  
  @staticmethod
  def quality_control_sampling(population_size, defective_items, sample_size, max_defective):
    """Hypergeometrische Verteilung für Qualitätskontrolle"""
    good_items = population_size - defective_items
    total_probability = 0
    
    print(f"Qualitätskontrolle: {sample_size} aus {population_size} (davon {defective_items} defekt)")
    print(f"Wahrscheinlichkeit für maximal {max_defective} defekte Teile:")
    
    for k in range(min(max_defective + 1, defective_items + 1, sample_size + 1)):
      if k <= defective_items and sample_size - k <= good_items:
        # P(X = k) = C(defective,k) * C(good,sample-k) / C(total,sample)
        numerator = (math.factorial(defective_items) // (math.factorial(k) * math.factorial(defective_items - k))) * \
                    (math.factorial(good_items) // (math.factorial(sample_size - k) * math.factorial(good_items - sample_size + k)))
        denominator = math.factorial(population_size) // (math.factorial(sample_size) * math.factorial(population_size - sample_size))
        probability = numerator / denominator
        total_probability += probability
        print(f" P(X = {k}) = {probability:.6f}")
    
    print(f"P(X ≤ {max_defective}) = {total_probability:.6f}")
    return total_probability
  
  @staticmethod
  def poker_hand_probability():
    """Berechnet Poker-Hand-Wahrscheinlichkeiten"""
    total_hands = math.factorial(52) // (math.factorial(5) * math.factorial(47)) # C(52,5)
    
    print(f"Poker-Hand-Wahrscheinlichkeiten (5 aus 52 Karten):")
    print(f"Gesamte mögliche Hände: {total_hands:,}")
    
    # Royal Flush: nur 4 mögliche Hände
    royal_flush = 4
    print(f"Royal Flush: {royal_flush}/{total_hands:,} = {royal_flush/total_hands:.10f}")
    
    # Straight Flush: 40 - 4 = 36
    straight_flush = 36
    print(f"Straight Flush: {straight_flush}/{total_hands:,} = {straight_flush/total_hands:.10f}")
    
    # Four of a Kind: 13 * C(48,1) = 13 * 48 = 624
    four_of_a_kind = 13 * 48
    print(f"Four of a Kind: {four_of_a_kind}/{total_hands:,} = {four_of_a_kind/total_hands:.6f}")

# Beispiel-Simulationen
simulator = ProbabilitySimulator()

# Lotto 6 aus 49
simulator.lottery_probability(49, 6, [1, 2, 3, 4, 5, 6])

# Qualitätskontrolle
simulator.quality_control_sampling(100, 5, 10, 1)

# Poker-Wahrscheinlichkeiten
simulator.poker_hand_probability()