Diskussion:Binomialkoeffizient

Ich würde den Spezialfall mit natürliche Zahlen mit Fakultäten extra ausweisen (Kombinatorik). Den allgemeinen Fall mit Gamma-Funktion fände ich hübscher. ---Lenny222 10:05, 9. Jul 2003 (CEST)

Ich habe jetzt in den Bronstein geschaut: Dort werden beide Formen als Definitionen verwendet. Der Fall q=0 ist hier allerdings bei der allgemeineren Definition auch extra angegeben, und das ist bei näherer Betrachtung auch sinnvoll, da ein Produkt mit 0 Faktoren nicht ganz offensichtlich 1 ist.

Ich finde es allerdings sauberer, wenn man als Definition nur die allgemeinere Version verwendet, da die Definition mit den Fakultäten als Spezialfall daraus hervorgeht.

Mit Gammafunktionen kann man z.B. (-1 über n) nicht darstellen, da die Gammafunktion für ganzzahlige n<=0 nicht definiert ist. Andererseits kann man mit Gammafunktionen auch q reell machen. Siehe auch Betafunktion (noch nicht geschrieben :-)) --Ce 10:23, 9. Jul 2003 (CEST)

Mein Bronstein ist offenbar zu alt. Da gibt es weit und breit nur ganze Zahlen. Kannst Du mal ein Beispiel geben, wo reelle Zahlen auftreten?---Lenny222 09:02, 10. Jul 2003 (CEST)

Kein Problem:

{\sqrt {1+x}}=\sum _{k=0}^{\infty }{1/2 \choose k}x^{k}

bzw. allgemeiner

(1+x)^{\alpha }=\sum _{k=0}^{\infty }{\alpha  \choose k}x^{k}

für beliebiges reelles α. --Ce 10:39, 10. Jul 2003 (CEST)

Ok, danke.---Lenny222 10:49, 10. Jul 2003 (CEST)

Eine einfache Definition sollte am Anfang eingefügt werden. Gibt es eine Definition, die allgemeiner verständlich ist? Ich selbst verstehe es ja, denke aber, eine rein formelmäßige Schreibweise ist, wenn sie ausschließlich verwendet wird, für eine Enzyklopädie nicht geeignet. Wer hier nachsieht, sollte doch wenigstens einen Eindruck haben, was man darunter versteht.

Ich bin ebenfalls dafuer, die einfachste Definition an den Anfang zu stellen, und dann schrittweise zu verallgemeinern. Ich hab jetzt den Artikel komplett umsortiert, so dass nun die einfachste Definition am Anfang steht. Haeltst du diese noch fuer zu unverstaendlich?

Vielleicht sollte man direkt nach der ersten Definition auf den Abschnitt "Anwendung in der Kombinatorik" verweisen, und dort naeher erlaeutern, wie die Formel fuer "die Anzahl der Moeglichkeiten, aus n Elementen k Elemente ohne Zuruecklegen auszuwaehlen, ohne die Reihenfolge zu beachten" zustandekommt. An der Stelle kann man auch auf die englische Bezeichnung "n choose k" eingehen... Oder man verweist auf Kombinatorik#Kombination_ohne_Zurücklegen. --SirJective 16:20, 19. Mär 2004 (CET)

Es fehlen noch Rechenregeln, z.B. (n/n-p)=(n/p)--Hhdw 16:39, 19. Mär 2004 (CET)

Es fehlen noch mehr Rechenregeln. Aber muß man jede Rechenregel, die man Ableiten könnte trotzdem erwähnen? --Arbol01 16:49, 19. Mär 2004 (CET)

Grundlegende Rechenregeln, die man im Umgang mit Binomialkoeffizienten oft braucht, sollten erwähnt werden in einem eigenen Abschnitt, z.B. die von Hhdw angegebene. Sowas wie

\sum _{i=0}^{n}{n \choose i}=2^{n}

lässt man Studenten beweisen, ich halte dies aber nicht für eine Aussage, die hier als Rechenregel erwähnt werden sollte, höchstens als eine Eigenschaft. --SirJective 00:38, 20. Mär 2004 (CET)

Optimierung der Auswertung

Ist das nicht ein ziemlich trivial-alltägliches Problem? Ausserdem kann man die Binomialkoeffizienten auch rekursiv berechnen, ganz ohne Gefahr eines Überlaufs; das ist auch gar nicht sooo ineffizient, da die Binomialkoeffizienten ja (im Schnitt) exponentiell wachsen.--Gunther 13:25, 14. Mär 2005 (CET)

Im Gegenteil. Es besteht auch beim rekursiven Berechnen, ja gerade beim rekusiven Berechnen, die Gefahr eines Überlaufs. Nämlich den eines Stack-Überlaufs. Und es ist zusätzlich eine Frage der Zeit.

Ich habe mal 49 über 6 rekursiv berechnen lassen, auf einer Sinix-Workstation. Es hat mehrere Minuten lang gedauert, bis ein Ergebnis zurück kam.

Nein, es ist wirklich kein triviales Problem. Aber du kannst ja mal 49 über 6 (oder größer) zu Fuß rekursiv berechnen, wenn dir danach ist. --Arbol01 11:14, 15. Mär 2005 (CET)

Hm, wenn ich bei mir (Athlon 1600+) auf 490 und 60 raufgehe, dann wird die Zeit so langsam messbar (0.014s). (Ok, das Resultat 716395843461995557415116222540092933411717612789263493493351013459481104668848 bringt dann natürlich meinen unsigned zum Überlauf, aber das war ja nicht die Frage. Der Rest mod 2³² stimmt jedenfalls.) Du hast Dir schon die bereits berechneten Werte gemerkt, oder? Und eine Stack-Tiefe von 49 (bzw. 490) ist doch nicht wirklich gefährlich.--Gunther 12:14, 15. Mär 2005 (CET)

Ich habe das schon lange nicht mehr gemacht! Die ersten Erfahrungen dieser Art stammen noch aus dem erste Semester 1989/90 (so jetzt habe ich mich geoutet), als wir noch mit Turbo-Pascal an 286-PC's gearbeitet haben. Diese Waren langsam, und ein Stacküberlauf war sehr wohl ein Problem.

Allerdings irrst Du mit deiner Stacktiefe, da ja nicht nur 490 Werte zwischengespeichert werden müssen, sondern einige mehr (Ich habe alledings nie berechnet, wieviele Werte maximal im Stack liegen). --Arbol01 12:28, 15. Mär 2005 (CET)

Um Missverständnisse zu vermeiden: Es geht (mir) um folgenden Code:

#define SIZE 1000

unsigned cache[SIZE * SIZE];

unsigned binom(unsigned n, unsigned k)
{
        if (k > n)
                return 0;
        if (k == n || k == 0)
                return 1;
        if (!cache[n * SIZE + k])
                cache[n * SIZE + k] = binom(n - 1, k - 1) + binom(n - 1, k);
        return cache[n * SIZE + k];
}

Die benötigte Stacktiefe ist n, die Rechenzeit ist nicht exponentiell. Der Cache benötigt minimal etwa n * k Plätze.--Gunther 12:58, 15. Mär 2005 (CET)

Um auch mißverständnisse zu Vermeiden:

1. Rechne das ganze mal zu Fuß (nicht 490 über 60)

2. Schreibe das ganze mal in C oder Rexx oder Tcl oder irgend einer Programmiersprache, die nicht auf Mathematische Probleme spezialisiert ist.

3. Schreibe das Progrm mal in Shellscript, das sich rekursiv wieder aufruft. Naja, vielleicht geht das auch in Rexx.

Ich mißtraue diesen Mathematik-Paketen (auch Mupad). Nicht, das sie falsche ergebnise liefern würden. Aber sie können ihre eigenen Tricks verwenden. --Arbol01 13:47, 15. Mär 2005 (CET)

Ich ziehe parallel mal mit (Intel Pentium, 1,2 GHz). Mal sehen.

1. Muss nicht sein.

2. Das ist C. MuPAD habe ich nur benutzt, um das Ergebnis zu überprüfen.

3. Done. Shellskripte sind schon verdammt langsam: 2.4s für 49 und 6 und 3m46.578s für 490 und 60. Code:

#!/bin/bash
[ -d binomial-cache ] || mkdir binomial-cache
if [ $2 -eq 0 -o $2 -eq $1 ]; then
        echo 1 > binomial-cache/$1-$2
else
        nminus1=$(($1 - 1))
        kminus1=$(($2 - 1))
        [ -e binomial-cache/$nminus1-$2 ] || $0 $nminus1 $2 blub
        [ -e binomial-cache/$nminus1-$kminus1 ] || $0 $nminus1 $kminus1 blub
        echo $((`<binomial-cache/$nminus1-$2` \
                + `<binomial-cache/$nminus1-$kminus1`)) > binomial-cache/$1-$2
fi
if [ $# -eq 2 ]; then
        cat binomial-cache/$1-$2
        rm -rf binomial-cache/
fi

--Gunther 14:19, 15. Mär 2005 (CET)

Optimierung durch Primfaktorzerlegung ist keine Optimierung

Das Dir, Gunther der Weg meiner Optimierung nicht gefällt, damit kann ich leben. Aber dafür die Primfaktorzerlegung reinzusetzen, zeigt nicht viel Kenntnis. Gerade die Primfaktorzerlegung ist sehr aufwendig. --Arbol01 17:27, 21. Mär 2005 (CET)

Die Laufzeit des angegebenen Algorithmus sollte eigentlich ganz ok sein: Wenn ich eine Liste von Primzahlen vorliegen habe, muss ich für jede der

n/{\log n}

Primzahlen kleiner als

n

etwa

\log n

oft teilen und am Schluss noch

n/\log n

Multiplikationen durchführen. Solange meine Rechenoperationen

O(1)

sind, sollte der Algorithmus also nicht schlechter als

O(n)

sein.

Darf ich umgekehrt fragen, wie Deine Optimierung funktioniert, wenn nicht durch Primfaktorzerlegung? Woher weiß ich, dass ich 2352/30 oder 9534420/30 kürzen kann?--Gunther 19:26, 21. Mär 2005 (CET)

"Mein" Optimierungsverfahren beruht auf dem ggT. Das heißt, zuerst wird ein ggT zwischen Zähler und Nenner ermittelt. Das Programm:

#include <stdio.h>

unsigned int ggt(unsigned int m, unsigned int n)
{
  unsigned int c=0;
  do
  {
    if (m < n)
    {
      if ((n % m) > 0)
      {
        n %= m;
      }
      else
      {
        c = m;
      }
    }
    if (m > n)
    {
      if ((m % n) > 0)
      {
        m %= n;
      }
      else
      {
        c = n;
      }
    }
  }
  while (c == 0);
  return(c);
}

unsigned int bin_koeff(unsigned int n, unsigned int k)
{
  unsigned int na = n;
  unsigned int ka = k;
  unsigned int t;
  if (na == ka) ka = 0;
  if (na == 0)  return(0);
  if (ka == 0)  return(1);
  if (ka == 1)  return(na);
  if ((ka > 1) && (na > 0))
  {
    do
    {
      na *= (n-1);
      ka *= (k-1);
      t   = ggt(na,ka);
      na /= t;
      ka /= t;
      n--;
      k--;
    }
    while (k > 1);
  }
  return(na / ka);
}

int main()
{
  unsigned int a, b, ergebnis;
  scanf("%d",&a);
  scanf("%d",&b);
  ergebnis = bin_koeff(a,b);
  printf(" %d ueber %d = %d \n",a,b,ergebnis);
  return 0;
}

muß keine Primzahlen kennen. --Arbol01 19:39, 21. Mär 2005 (CET)

So nach dem ersten Eindruck ist das

O(k^{2})

. Aber Du bringst mich auf eine Idee: was hältst Du von

unsigned binom(unsigned n, unsigned k)
{
    unsigned result;
    if (k == 0)
        return 1;
    if (2 * k > n)
        return binom(n, n - k);
    result = n;
    for (unsigned i = 1; i < k; i++)
        result = (result * (n - i))/(i + 1);
    return result;
}

Das ist definitiv einfacher, nicht überlaufgefährdet und

O(k)

.--Gunther 20:05, 21. Mär 2005 (CET)

Darüber muß ich erst mal schlafen. Aber zwei Anmerkungen:

Jedes Verfahren zur Berechnung ist überlaufgefährdet, wenn man nur die Zahlen groß genug wählt.
Wir sind uns doch drüber einig, das die Rechenzeit bei den heutigen Rechnern in diesem Falle keine Rolle mehr spielen. --Arbol01 20:20, 21. Mär 2005 (CET)

Die beiden Verfahren, die Du wieder gelöscht hast, laufen nur dann über, wenn das Ergebnis selbst nicht gespeichert werden kann. Die andere müssen das k-fache des Ergebnisses speichern können.--Gunther 20:55, 21. Mär 2005 (CET)

Ein System, das nur Integervariablen (0-255) kennt, wird sehr schnell überlaufen. wenn ein System Integerzahlen bis 2^n beherrscht, bekommt be Zahlen mit 2^(n+1) Überlaufprobleme. Wenn ich also Binomialkoeffizienten berechnen lasse, dessen Ergebnis größer als das zulässige Format ist, nützt mir der ausgefeilteste Algorithmus nichts mehr. --Arbol01 21:10, 21. Mär 2005 (CET)

Das ist mir bekannt. Ich meinte, dass man beispielsweise bei 8-Bit-Zahlen

{\binom {10}{5}}=252<2^{8}

mit den gelöschten Algorithmen berechnen kann, mit den anderen jedoch nicht.--Gunther 21:36, 21. Mär 2005 (CET)