Binominalkoeffizienten

sind die Koeffizienten, die sich bei der Berechnung von (a+b)n ergeben:

Die Koeffizienten

(sprich n über k) ergeben sich auch für Aufgabenstellungen der Wahrscheinlichkeitsrechung. n über k ist z.B. die Anzahl der Möglichkeiten aus n Elementen k Elemente auszuwählen, wenn die Reihenfolge der Auswahl keine Rolle spielt. Das ist z.B. beim Lotto der Fall. Beim Spiel 6 aus 45 ist die Wahrscheinlichkeit für einen 6 er:

Wenn man völlig unbekümmert die Berechnung ausprogrammiert, z.B. vorhandene Funktionen zur Berechnung der Fakultät verwendet, oder zunächst den Zähler ausmultipliziert und den Nenner ausmultipliziert, so ergeben sich rasch Probleme. Die Produkte erreichen schon für kleine Zahlen eine Größe, die mit dem Standardtyp int nicht mehr darstellbar sind und deshalb falsche Resultate die Folge sind. Zudem zeigt eine genauere Analyse, dass die iterative Berechnung auch viel effizienter gestaltet werden kann.

Der folgende Programmcode zeigt einige Funktionen zur Berechnung von n! und zur Berechnung von n über k.

Für beide Berechnungen werden sowohl iterative als auch rekursive Lösungen gezeigt.

Die rekursive Lösung für n über k beruht auf der Formel:

Oder auch:

Das ist als Rekursionsformel brauchbar, wenn man zudem weiß, dass

ist. n über k ist nur für n >= k definiert, somit kommt man bei der Rekursion nach k Schritten auf die Berechnung von m über 1 und kann die Rekursion damit abbrechen.

Quelltext:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define N 6          // Anzahl der Lottozahlen
#define LMAX 45      // Zahlenbereich der Lottozahlen z.B. 1 bis 45  (österreichisches Lotto)

void Tausche(int *a, int *b);
unsigned long long  nFakultaetIt(int n);
unsigned long long  nFakultaetRec(int n);
unsigned long long  NueberK1(int n, int k);
unsigned long long  NueberK2(int n, int k);
unsigned long long unsigned NueberKRec(int n, int k);
void lotto();
void TesteFakultaet();
void TesteNueberK();
void printLottoZahlen(unsigned aTipp[], char* endZeichen);
bool IstZahlInListe (unsigned liste[], unsigned n, unsigned zahl);
unsigned PruefeLottoTipp(unsigned aRichtige[], unsigned aTipp[], unsigned n);

int main()
{
  TesteFakultaet();
  
  TesteNueberK();
  
  /* Seed the random-number generator with current time so that
   * the numbers will be different every time we run.
   */

  srand( (unsigned)time( NULL ) );

  lotto();

  return 0;
}

void TesteFakultaet()
{
  int n;
  unsigned long long  nfak;

  do {
    printf("n! berechnen n = ");
    scanf("%u", &n);

    nfak = nFakultaetIt(n);    // iterative Loesung
    printf("%u! = %20I64u\n", n, nfak);      // I64 is Microsoft specific for int64  long long
    nfak = nFakultaetRec(n);  // rekursive Loesung
    printf("%u! = %20I64u\n", n, nfak);
  } while (n > 0);
}

void TesteNueberK()
{
  int n;
  int k;
  unsigned long long nk;  // 64 bit Zahl
  do {
    printf("n ueber k : n k = ");
    scanf("%u %u", &n, &k);
    if (k > n) 
    {
      printf("NueberK1: n muss groesser gleich k sein\n");
      continue;
    }  
    nk = NueberK1(n, k);
    printf("%i ueber %i = %I64u\n", n, k, nk);
    nk = NueberK2(n, k);
    printf("%i ueber %i = %I64u\n", n, k, nk);
    nk = NueberKRec(n, k);
    printf("%i ueber %i = %I64u\n", n, k, nk);
  } while (!(k == 0 && n == 0));

}

unsigned long long nFakultaetIt(int n)
{
  int i;
  unsigned long long  p = 1;
  if (n <= 1) return 1;
  for (i = 2; i <= n; i++)
    p *= i;
  return p;
}

unsigned long long nFakultaetRec(int n)
{
  if (n <= 0) 
    return 1;
  else
    return n * nFakultaetRec(n-1);
}

unsigned long long NueberK1(int n, int k)
{
// einfach die Formel verwenden, 
  // ineffizient und moeglicher Zahlenbereich kleiner
  // funktioniert nur fuer n <= 20, k <= 20;
  unsigned long long  zaehler, nenner;
  if (n > 20 || k > 20)
  {
    printf("NueberK1: Resultat von NueberK kann nicht berechnet werden\n");
    return 0;
  }
  zaehler = nFakultaetIt(n);
  nenner = nFakultaetIt(k)*nFakultaetIt(n-k);
  return zaehler / nenner;
}

unsigned long long NueberK2(int n, int k)
{
  
  // n >= k
  // Ausnuetzen, dass n! alle Faktoren von k! und (n-k)! enthaelt und gekuerzt werden kann
  // wir nützen die Symetrie des Produktes k!(n-k)! so, dass wir dafüœr sorgen,
  // dass k immer kleiner als n-k ist (durch Tausch, falls es nicht so ist)
  // es bleiben dann im Nenner das Produkt  n(n-1)(n-2)....(n-k+1)
  // und im Zähler das Produkt k(k-1)(k-2)....1
  // z.B. für 8 ueber 3  -->  8*7*6 / 3*2*1  oder  8*7*6 / 1*2*3
  // wir berechnen diesen Ausdruck in der Reihenfolge
  // 8 / 1 * 7 / 2 * 6 / 3
  // In dieser Reihenfolge sind die Divisionen interessanterweise 
  // und zum Glück immer ohne Rest möglich
  // die Zahl der Faktoren im Zähler und im Nenner ist auch immer gleich,
  // wir brauchen immer k Multiplikationen und k Divisionen
  // und das abwechselnde multiplizieren und dividieren sorgt daür, dass 
  // das Resultat p immer so klein wie möglich bleibt.
  
  unsigned long long p = 1;
  int nmk = n - k;

  if (k > nmk)
    Tausche( &k, &nmk);

  k = 1;
  while (n > nmk)
  {
    p *= n--;
    p /= k++;
  }
  return p;
}

unsigned long long NueberKRec(int n, int k)
{
  if (k == 0)
    return 1;  // Ende der Rekursion
  else         // Rekursiver Aufruf
    return n * NueberKRec(n-1, k-1) / k;
}
void Tausche(int *a, int *b) { int t = *a; *a = *b; *b = t; } void lottoTipp (unsigned aTipp[], unsigned max) { unsigned z; unsigned nBerechnet = 1; bool zahlBereitsGezogen; aTipp[0] = rand() % max + 1; // erste Lottozahl = Zufallszahl zwischen 1 und max while (nBerechnet <= n) { z = rand() % max + 1; zahlBereitsGezogen = IstZahlInListe( aTipp, nBerechnet, z); if (!zahlBereitsGezogen) { aTipp[nBerechnet-1] = z; nBerechnet++; } } } void printLottozahlen(unsigned aTipp[], char* endZeichen) { unsigned i; for (i = 0; i < N; i++) printf("%2i ", aTipp[i]); printf("%s", endZeichen); } bool IstZahlInListe (unsigned liste[], unsigned n, unsigned zahl) { unsigned i; for (i = 0; i < n; i++) { if (zahl == liste[i]) return true; } return false; } unsigned PruefeLottoTipp(unsigned aRichtige[], unsigned aTipp[], unsigned n) { // ermittelt, wieviele Zahlen aus aTipp in aRichtige enthalten sind // n ist die Anzahl der Zahlen // die arrays aRichtige und aTipp muessen mindestens n Elemente haben unsigned richtige = 0; unsigned i; for (i = 0; i < n; i++) { if (IstZahlInListe(aRichtige, n, aTipp[i])) richtige++; } return richtige; } void lotto() { unsigned lottoZahlen[N]; // die gezogenen Lottozahlen unsigned einTipp[N]; // ein Lotto Tipp lottoTipp(lottoZahlen, N, LMAX); printLottozahlen(lottoZahlen, "\n"); // 10000 Tipps erzeugen und prüfen, wieviele richtige dabei sind unsigned i, n = 10000; unsigned richtige; printf("Wahrscheinlichkeit fuer\n"); printf("6 er: 1 zu %I64u\n", NueberK2(LMAX, 6)); for (i = 0; i < n; i++) { lottoTipp(einTipp, N, LMAX); richtige = PruefeLottoTipp(lottoZahlen, einTipp, N); if (richtige > 2) { printLottozahlen(lottoZahlen, " --- "); printLottozahlen(einTipp, " ---> "); printf("%i richtige\n", richtige); } } // oder wieviele Tipps muessen wir erzeugen, bis ein 6-er kommt ? // aber Vorsicht, das kann dauern, deshalb zunächst auskommentiert /* long long unsigned tnr = 0; do { lottoTipp(einTipp, N, LMAX); tnr++; } while (PruefeLottoTipp(lottoZahlen, einTipp, N) < 6); printf("%I64u - ter Tipp ist ein 6-er\n", tnr); printLottozahlen(lottoZahlen, " --- "); printLottozahlen(einTipp, " ---> "); printf("%i richtige\n", 6); */ }