Diskussion:Binomialkoeffizient/Archiv/1

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:Binomialkoeffizient/Archiv/1#Thema 1]]

oder als Weblink zur Verlinkung auVorlage:SSerhalb der Wikipedia

https://de.wikiup.org/wiki/Diskussion:Binomialkoeffizient/Archiv/1#Thema_1

fakultaet als spezialfall der gamma-funktion

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)

einfache definition

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. --(nicht signierter Beitrag von Hutschi (Diskussion | Beiträge) 11:57, 19. Mär. 2004 (CET))

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)

fehlende rechenregeln

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 ${10 \choose 5}=252<2^{8}$ mit den gelöschten Algorithmen berechnen kann, mit den anderen jedoch nicht.--Gunther 21:36, 21. Mär. 2005 (CET)

4 aus 8 und zwei richtige bei 4 aus 8

Bei 4 aus 8 gibt es 70 Tips

Die Tips von 2 aus 8:

1, 2	2, 3	3, 4	4, 5	5, 6	6, 7	7, 8
1, 3	2, 4	3, 5	4, 6	5, 7	6, 8
1, 4	2, 5	3, 6	4, 7	5, 8
1, 5	2, 6	3, 7	4, 8
1, 6	2, 7	3, 8
1, 7	2, 8
1, 8

Jetzt kommt der Zufall in das Spiel:

(3, 5) und (6, 8) => 3, 5, 6, 8

1, 2	2, 3	3, 4	4, 5	-	6, 7	7, 8
1, 3	2, 4	-	4, 6	5, 7	-
1, 4	2, 5	-	4, 7	-
1, 5	2, 6	3, 7	4, 8
1, 6	2, 7	-
1, 7	2, 8
1, 8

Wieder der Zufall:

(1, 4) und (5, 7) => 1, 4, 5, 7

1, 2	2, 3	3, 4	-	-	6, 7	7, 8
1, 3	2, 4	-	4, 6	-	-
-	2, 5	-	-	-
-	2, 6	3, 7	4, 8
1, 6	2, 7	-
-	2, 8
1, 8

(1,7) und (2,8) => 1, 2, 7, 8 (ab jetzt sind Redundanzen vorhanden) R(1,7)

-	2, 3	3, 4	-	-	6, 7	-
1, 3	2, 4	-	4, 6	-	-
-	2, 5	-	-	-
-	2, 6	3, 7	4, 8
1, 6	-	-
-	-
-

(2, 6) und (3, 4) => 2, 3, 4, 6 R(3,6)

-	-	-	-	-	6, 7	-
1, 3	-	-	-	-	-
-	2, 5	-	-	-
-	-	3, 7	4, 8
1, 6	-	-
-	-
-

(1,6) und (3,7) => 1, 3, 6, 7 R(3,6) und R(1,7)

-	-	-	-	-	-	-
-	-	-	-	-	-
-	2, 5	-	-	-
-	-	-	4, 8
-	-	-
-	-
-

Als letztes noch (2,5) und (4, 8) => 2, 4, 5, 8 R(2,4), R(2,8), R(4,5) und R(5,8)

3, 5, 6, 8 ; 1, 4, 5, 7 ; 1, 2, 7, 8 ; 2, 3, 4, 6 ; 1, 3, 6, 7 ; 2, 4, 5, 8

Fazit: mit 6 Tips habe ich alle möglichen Zweiertips von 4 aus 8, wobei 4 Redundanzen vorkommen.

Was sagt jetzt die Hypergeometrische Verteilung? --Arbol01 13:10, 25. Mär. 2005 (CET)

Betafunktion

Warum die Einschränkungen $k>-1$ und $\alpha -k>-1$? Die Betafunktion ist doch meromorph in der ganzen Ebene.-- Gunther 11:05, 14. Apr. 2005 (CEST)

Fünf Richtige

Fehler im Artikel:

"Die Anzahl der Möglichkeiten für 5 Richtige bei 6 aus 49, lassen sich aber nicht über den Binomialkoeffizient berechnen, dazu wird die Hypergeometrische Verteilung benötigt."

Lässt sich sogar sehr einfach berechnen:

49 über 5 * 44 über 1

oder täusche ich mich da ???

außerdem ist noch ein Grammatikfehler in dem Satz: "Binomialkoeffizient" da fehlt ein "-en"...

mfg und gute N8

f_gx

Ja, Du täuscht Dich da. Das läßt sich prima mit drei Richtigen zeigen. Wenn es denn stimmen würde, das sich 5 Richtige bie 49 über 6 über den Binomialkoeffizienten oder die Hypergeometrische Verteilung berechnen lassen könnte, so müßte man auch drei Richtige bei 6 aus 49 mittels eines dieser beiden Formeln berechnen können. Probieren wir das mal. Zuerst ermitteln wir mal alle 3 aus 49. Das sind 18424 Dreiergruppen. Nun nehmen wir zufällig immer zwei Dreiergruppen, und versichern uns, das die beiden Dreiergruppen keine gemeinsame Zahl besitzen. Ist das der Fall, dan haben wir einen Tip mit sechs Zahlen, und legen diesen beiseite. Nun entfernen wir alle Dreiergruppen, die in diesem Sechsertip vorkommen. Jetzt wieder zwei dreiergruppen ohne gemeinsame Zahl nehmen, Tip aufschreiben, und alle redundanten Dreiergruppen entfernen. ...

Wenn es stimmt, das sich 3 Richtige von 6 aus 49 per Binomialkoeffizient berechnen lassen, müßte dieses Schema problemlos aufgehen. Dem ist aber nicht so. Es bleiben irgendwann Dreiergruppen übrig von denen man von zwei beiliebigen Dreiergruppen nicht mehr sagen kann, sie hätten keine gemeinsame Zahl. --Arbol01 03:28, 25. Mär 2005 (CET)

Im Artikel wurden 2 Begriffe verdreht: die Anzahl der Stimmzettel im Lotto 6 aus 49 ist ${49 \choose 6}$. Aber für 6 Richtige gibt es genau eine Möglichkeit. Erst mit dieser Unterscheidung ergibt es Sinn, nach der Anzahl der Möglichkeiten für 5 Richtige zu fragen (die sich übrigens durchaus mit der Hypergeometrischen Verteilung berechnen lässt.) Ich habe die Begriffsverwirrung nun durch die Verwendung des Begriffs der Wahrscheinlichkeit aufgelöst.--MKI 14:17, 25. Mär 2005 (CET)

in österreich wird lotto mit 6 aus 45 gespielt. daher sollte hier kein regional eingeschränktes beispiel angeführt werden, ausser man will sich auf wikipedia nur auf deutschland beziehen. (nicht signierter Beitrag von 62.178.141.211 (Diskussion) 17:24, 26. Okt. 2008 (CET))

Bronstein Abschreibübung

Den Fehler korrigiert in Summeneigenschaften, statt 0 heißt es 0^n, ansonsten referenzieren wir nicht das neutrale Element der Multiplikation, und darauf kommt es im Pascal-Dreieck an. --Helmut Rasinger 03:29, 31. Okt. 2006 (CET)

@Gunther: Wenn du die Formel mit n>0 einschränken willst, dann mußt du auch die allgemeine Gültigkeit des Binomischen Lehrsatzes einschränken. Die Formel ist nur eine spezielle Substitution (x:=-1; y:=1; n:=0) angewendet auf den Binomischen Lehrsatz. Willst du das, dann schreibe gefälligst auch sinngemäß in die Definition: Binomischer Lehrsatz gilt nicht für den Fall (n=0) Sei konsequent!!!!! Nach Definition ist es aber zugelassen!!!! Ändere bitte die Definition!!!!! Alternativ revert auf meine Version. Entweder oder! Denk darüber nach, was du gesagt hast: "Meine Ansprüche an die Mathematik sind größer als deine" --Helmut Rasinger 15:58, 3. Nov. 2006 (CET)

Es gibt bei dieser Formel i.w. zwei Möglichkeiten: entweder 0 auf der rechten Seite und die Einschränkung auf $n>0$, oder so etwas wie $0^{n}$ oder ${\begin{cases}0&n>0\\1&n=0\end{cases}}$ auf der rechten Seite und keine Einschränkung an $n$. Bei der zweiten Möglichkeit verliert man Verständlichkeit und Übersichtlichkeit für einen relativ geringen Informationsgewinn. Und bitte zitiere mich nicht falsch, danke.--Gunther 16:03, 3. Nov. 2006 (CET)

@Gunther: Zitat kopiert mit CTRL-C. Quelle:

http://de.wikipedia.org/wiki/Diskussion:Vollkommene_Zahl#.C3.84quivalente_Aussagen_haben_keinen_Nutzen.3F

Zitatanfang:

Wer die Formel verstanden hat, braucht keine Mnemotechnik. Meine Ansprüche an "mathematische Zusammenhänge" sind höher als Deine.

Zitatende.

Meine Aussage lautet: "(n>0) ist eine Definitionseinschränkung für Binomialkoeffizienten"

Entweder ist die Definition allgemeingültig oder nicht.

Red nicht um den heißen Brei herum, entscheide dich bitte!!!!!! --Helmut Rasinger 19:33, 3. Nov. 2006 (CET)

Mit "Definitionen" oder mathematischen Zusammenhängen hat das alles nichts zu tun. Es geht darum, dass der Spezialfall $n=0$ so uninteressant ist, dass er es nicht rechtfertigt, dafür die Darstellung der Formel komplizierter bzw. unverständlicher zu machen. Der Laie weiß typischerweise nicht, dass 0⁰ = 1 ist.--Gunther 08:34, 4. Nov. 2006 (CET)

P.S. Es wäre der Effizienz der Diskussion übrigens sehr zuträglich, wenn Du weniger Zeit mit dem Tippen von Ausrufezeichen und mehr Zeit mit dem Lesen und Verstehen der Antworten verbringen würdest.--Gunther 08:54, 4. Nov. 2006 (CET)

---

Angewandte Taktik: Zerreden!!!!!!!!!

Mit der Einschränkung (n>0) machst gerade du einen Spezialfall daraus.

Findest du $0!=1\,$ verständlicher? Oder ${n \choose 0}=1$, oder $n^{0}=1\,$

Das neutrale ("zentrale") Element der Multiplikation ist EINS, so einfach lautet die Regel. Ich habe einige Beispiele gegeben, die für den Laien verständlich waren, leider sind sie zur Gänze, ich betone zur Gänze, gelöscht worden. Man hält das ja für zu trivial, zu banal, zu simpel. Diese ungeheure Arroganz dem Einfachen zu begegnen, führt auf einen langen, langen Weg.

Keine 5 Sekunden habe ich gebraucht um zu verstehen, daß die angeführte Formel fehlerhaft ist, kurz weil ich seinerzeit meinen Bronstein etwas "korrigiert" habe. Selbst nach Mitteilung, daß ein Fehler bei den Summeneigenschaften vorliegt, konntet ihr den Fehler nicht finden. Schließlich habe ich ihn selbst ausgebessert. Wer braucht hier Zeit zum Verstehen?!?!?!?

--Helmut Rasinger 11:46, 4. Nov. 2006 (CET)

Sorry, aber Du erwartest nicht im Ernst, dass hier jemand auf Diskussionsbeiträge der Art "ich hab einen Fehler gefunden, verrate aber nicht wo, jetzt geht mal suchen" eingeht? Ja, die Formel war fehlerhaft, und es gibt wie oben schon gesagt i.w. zwei Möglichkeiten, den Fehler zu beheben, von denen eine klar vorzuziehen ist, Gründe s.o. Beruhige Dich mal wieder, ich beabsichtige nicht, auf weitere Beiträge von Dir einzugehen, wenn es in ihnen weiter so von Ausrufezeichen wimmelt, ein bisschen Sachlichkeit wäre extrem hilfreich.--Gunther 12:04, 4. Nov. 2006 (CET)

---

Mach weniger Ausrufezeichen, schreibt er. Sonst noch was? Den persönlichen Ausdruck meiner Texte lass ich mir nicht nehmen. Allerdings setze ich sie nur ein, wenn ich es für nötig halte. Deine Ansichten zählen nicht mehr und nicht weniger als die der anderen. Es wäre schön wenn du auch die Meinung anderer zulassen würdest. Wer sich mit Binomialkoeffizienten auskennt, der weiß auch höchstwahrscheinlich was 0^n bedeutet. Also ist deine Argumentation nicht stichhaltig, welche besagt 0^n sei zu schwierig für den Leser. Daher revert in den ursprünglichen Zustand. Dein Trick auf Sachlichkeit hinzuweisen, nun ich nehme es gelassen, er ist für intelligente Leser zu offensichtlich. Wie ich bereits bemerke, von mal zu mal ändern sich deine Argumente, du windest dich, ich hol den Haken. Ich warte auf das nächste Argument, so fadenscheinig es auch sein mag. --Helmut Rasinger 18:05, 4. Nov. 2006 (CET)

0⁰ war noch im 19. Jahrhundert ernsthaft umstritten (teilweise bis heute), als Binomialkoeffizienten schon längst Standard waren. Für mich ist EOD, Dein Diskussionsstil verdirbt mir die Laune.--Gunther 19:01, 4. Nov. 2006 (CET)

Bravo, du hast den einzigen Schwachpunkt in meiner Argumentation gefunden. Es war wahrscheinlich kein Zufall, daß es im Bronstein nicht angeführt wurde. Es ist bis heute umstritten. Mit gutem Grund. Und genau das wollen die Leute die Wikipedia lesen, auch wissen. Der anschließende Satz über die anschauliche Symmetrie ist äußerst fragwürdig, ersetz ihn lieber durch deinen Satz:

0⁰ war noch im 19. Jahrhundert ernsthaft umstritten (teilweise bis heute), als Binomialkoeffizienten schon längst Standard waren.

Oder so ähnlich, danke für die Diskussion. --Helmut Rasinger 22:56, 4. Nov. 2006 (CET)

Habe den ziemlich unklaren Satz geändert, die Summeneigenschaft würde auch für eine asymmetrische Zeile gelten, die in der Pascal-Art aus einer "vorangehenden" Zeile entsteht (d.h. $\sum (-1)^{k}(a_{k}+a_{k+1})=0$). 0⁰ taucht in der aktuellen Artikelfassung nicht mehr auf.--Gunther 23:12, 4. Nov. 2006 (CET)

---

Dein Satz gefällt mir besser, er zeigt den Leuten eine kritische und seriöse Auseinandersetzung mit dem Thema und der Mathematik überhaupt, das ist Qualität.

Themenwechsel Oberflächlich betrachtet, hätte man die Symmetrie so ausdrücken können:

Für die (n+1)^te-Zeile des Pascal-Dreiecks gilt:

$n\in \mathbb {N} :\qquad \sum _{k=0}^{\infty }{{n+1} \choose {2k}}=\sum _{k=0}^{\infty }{{n+1} \choose {2k+1}}$

Man beachte:

1) Man hat "Schwierigkeiten" den oberen Index anzugeben, der einfachheithalber gegen unendlich, stimmt genauso, da n limitiert.

2) Auch hier wird die Zeile 0 ausgenommen, eben das Problem 0⁰, der übliche Murx.

Das 0^0 Problem ist keineswegs trivial. Ich glaube sogar, eine saubere Lösung würde die Mathematik revolutionieren, und eine Reihe von Paradoxien entlarven.

Was mir aufgefallen ist, ihr habt ja gar keine Historie zu den Binomialkoeffizienten. Pascal, Euler, Leibnitz, Gauss, Newton, alle die Rang und Namen hatten, haben dieses Gesetz genauestens studiert. Zitierte Quellen reichen bis 1100, 400 Jahre vor Pascal. Aufgrund seines einfachen Aufbaus, welcher letztlich im Dezimalsystem seinen Ursprung hat, birgt es enorme Möglichkeiten. --Helmut Rasinger 19:23, 5. Nov. 2006 (CET)

Andere Schreibweise erwähnen!

$C(n,k)$ und $C_{n}^{k}$ -- 19:59, 8. Nov. 2007 (CET)

Rechenregeln

stimmen diese Rechenregeln?:

${\binom {x}{0}}={\binom {x}{x}}=1$

${\binom {x}{1}}={x \choose x-1}=x$

${\binom {x}{2}}={x \choose x-2}={\frac {x\cdot (x+1)}{2}}$

${\binom {x}{3}}={x \choose x-3}={\frac {x\cdot (x+1)\cdot (x+2)}{2\cdot 3}}$

${\binom {x}{4}}={x \choose x-4}={\frac {x\cdot (x+1)\cdot (x+2)\cdot (x+3)}{2\cdot 3\cdot 4}}$

...usw

PS: ok die formeln sind ein bischen verunstaltet könnte die jemand richten wenn er versteht wie es seien sollte ( wo unten nur "(" sollte das nach dem binom auch noch hinein ; "*" sollte mal (x) sein ; "/" sollte durch (:) sein;;) und meine Frage beantworten -- danke

--so die formeln sind jetzt ok fehlt noch die antwort

Anstatt Plus musst du Minus verwenden. Die Wikipedia ist jedoch kein Matheforum. Bitte wende dich mit deiner Frage an ein Matheforum (beispielsweise www.matheplanet.com).--Stefan Birkner 19:32, 14. Jul. 2008 (CEST)

danke für die antwort, und natürlich weiß ich, dass wikipedia... aber es geht in diesem artikel nun mal um diese sachen, und meiner ansicht nach ist das in dem artikel nicht genau erklärt, und da werde ich doch mal eine frage stellen dürfen. (insgesamt finde ich sollte man diesen artikel verständlicher machen!!!)

Bitte schreibe weniger aufgeregt. Gerade diese Formeln werden im Artikel prominent und ausführlich dargestellt. Mehrfache Ausrufungszeichen haben auch einen speziellen Ruf.--LutzL 15:39, 15. Jul. 2008 (CEST)

Punkte hinter Formeln

Warum haben Formeln, die nicht Bestandteil eines Satzes sind, trotzdem einen Punkt am Ende? --Stefan Birkner 08:19, 23. Jul. 2008 (CEST)

"5 ist groesser als 4." ist ein satz. ;-)

ohne punkt dahinter, koennte man eine fortsetzung des satzes erwarten, z.b.:

x+1<4

gilt fuer alle x<5.

am besten ist wohl, wenn man grundsaetzlich formeln in aeussere (erklaerende) saetze einbettet. -- seth 08:40, 23. Jul. 2008 (CEST)

bindestrich

Er gibt an, auf wieviele verschiedene Arten man k-Objekte aus einer Menge von n-verschiedenen Objekten auswählen kann (ohne Zurücklegen, ohne Beachtung der Reihenfolge).
der bindestrich erleichtert das lesen und verstehen dieses satzes um einiges. auch wenns es nicht ganz korret ist. (den fettdruck meine ich nicht). ich musste mir den satz 5 mal durchlesen. Was meint ihr ? (nicht signierter Beitrag von 79.211.238.9 (Diskussion) 10:39, 10. Nov. 2008 (CET))

der bindestrich ist an diesen stellen falsch und ungebraeuchlich. deshalb wuerde er wohl mehr leute verwirren als die lesbarkeit zu verbesern. -- seth 16:40, 18. Nov. 2008 (CET)

komplexe zahlen und index i

bei der definition bitte bitte bitte einen anderen index nehmen, sonst verwirrung mit imaginärer einheit. (Der vorstehende, nicht signierte Beitrag – siehe dazu Hilfe:Signatur – stammt von 213.47.66.8 (Diskussion • Beiträge) 20:19, 22. Jan. 2009 (CET))

danke fuer den hinweis. hab's korrigiert. -- seth 21:45, 22. Jan. 2009 (CET)

Zum schnellen Berechnen von n über k

Der Google Calculator kanns mittlerweile auch: Einfach "n choose k" im Google Suchfeld eingeben (z.B. "18 choose 11" ergibt 31824). Leonhardt ^talk! (18:12, 13. Apr. 2010 (CEST), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

n tief k?

In der Einleitung steht "49 über 6" (bzw.„45 über 6“ in Österreich und der Schweiz). Sollte das nicht etwas "49 über 6" (bzw.„49 tief 6“ in Österreich und der Schweiz). Sonst macht das für mich keinen Sinn... Also wir verwendeten am Gymnasium und an der ETH Zürich jeweils "n tief k" für den Binomialkoeffizienten. --Renzo 12:07, 5. Aug. 2011 (CEST)

"in Österreich und der Schweiz" bezieht sich nicht auf die Sprechweise in Österreich bzw. der Schweiz, sondern darauf, dass beim österreichischen bzw. Schweizer Lotto 6 aus 45 gezogen werden, während es in Deutschland 6 aus 49 sind. -- Digamma 14:00, 5. Aug. 2011 (CEST)

Effizienter Algorithmus

Ich habe den Satz mal entfernt, dass man nur natürliche Zahlen als Ergebnis erhält. Man berechne mal den Binomialkoeffizienten 15 über 7, nach der angegeben Produktregel, dann erhält man

9, 5, 3.666..., 3, 2.6, 2.333..., 2.14286...

als Zwischenergebnisse. Vielleicht habe ich das aber auch falsch implementiert oder irgendetwas falsch verstanden. Kann das jemand bestätigen?

129.69.116.204 18:28, 5. Mär. 2012 (CET) Daniel

Die Zwischenergebnisse sind 9,45,165,495,1287,3003,6435. Im Text steht auch was von stetigem Wechsel zwischen Multiplikation und Division. Wenn du erst die Faktoren ausrechnest, und die danach zusammenmultiplizierts, wo ist dann der Wechsel? --Daniel5Ko (Diskussion) 19:55, 5. Mär. 2012 (CET)

Rechenregeln nicht eindeutig

Ich finde das diese Rechenregeln noch mal genauer erklärt werden sollten. aus ${\binom {n+1}{k+1}}={\binom {n}{k}}+{\binom {n}{k+1}}$ lässt sich keine Regelmäßigkeit ableiten. Was z.B ist ${\binom {n+2}{k+2}}$ bzw. was ist ${\binom {n}{k+1}}$ oder ${\binom {n+1}{k+2}}$?! --88.69.40.58 10:50, 7. Okt. 2013 (CEST)

Hi, das ist die Erzeugungsregel des Pascalschen Dreiecks, mehr regelmäßig geht nicht. Es ist natürlich hilfreich, wenn man auch die Produktform kennt.--LutzL (Diskussion) 15:46, 7. Okt. 2013 (CEST)

Rechenregeln: n über (n-1)

Zunächst: der Satz 'Sämtliche dieser Regeln gelten auch für die Verallgemeinerung mit reellen oder komplexen Werten für n' sollte vor und nicht hinter den Regeln stehen. Das ist üblich und verringert das Risiko, dass er überlesen wird.

Wohl jeder unbefangene Leser mit Vorkenntnissen erwartet hier die Erwähnung von ${\binom {n}{1}}={\binom {n}{n-1}}=n.$ Ich inzwischen auch wieder - denn aus der verallgemeinerten Definition im Artikel

Für $\alpha \in \mathbb {R} \setminus \{-1,-2,-3,\ldots \}$ erlaubt die Betafunktion $\mathrm {B} (x,y)$ eine Erweiterung der Definition auf reelle $x$:

${\binom {\alpha }{x}}={\frac {1}{(\alpha +1)\,\mathrm {B} (x+1,\alpha -x+1)}}={\frac {\Gamma (\alpha +1)}{\Gamma (x+1)\,\Gamma (\alpha -x+1)}},$

wobei $\Gamma (x)$ die Gammafunktion bezeichnet. Ist dabei $x$ oder $\alpha -x$ eine negative ganze Zahl, so ist der Wert der rechten Seite 0.

folgt doch unmittelbar die Symmetrie

${\binom {\alpha }{x}}={\binom {\alpha }{\alpha -x}}$

Ich mach' das einfach mal - o.k., Digamma?. -- 77.186.118.104 06:02, 4. Feb. 2014 (CET)

PS: Also - für reelle alpha und x isses laut Artikel wenigstens so, sofern der BK überhaupt definiert ist (alpha nicht negativ ganz). Frage: Gilt obige Erweiterung denn nicht sogar für $\alpha \in \mathbb {C} \setminus \{-1,-2,-3,\ldots \}$? Die nichtpositiv ganzen sind doch die einzigen Polstellen von Gamma und Beta. Wenn ja, dann sollte 'relle'=>'komplexe' gemacht werden. -- 77.186.118.104 06:58, 4. Feb. 2014 (CET)

In dem Abschnitt ist mit "Verallgemeinerung" nur das gemeint, was auch in der Definitin schon steht: "Sämtliche dieser Regeln gelten auch für die Verallgemeinerung mit reellen oder komplexen Werten für n". Aber k wird hier noch als ganzzahlig vorausgesetzt. Deshalb macht bei dieser Definition ${\binom {n}{n-1}}$ gar keinen Sinn, wenn n nicht ganzzahlig ist.

Meiner Meinung nach sollte man sich aber im ersten Teil des Artikels auf natürliche Zahlen n beschränken. Eine ganze Menge der ersten Abschnitte (zum Beispiel das Pascalsche Dreieck, die ganze Kombinatorik, die binomischen Formeln mit echten Summen - im Unterschied zu den Reihen-, der Algorithmus für schnelle Berechnung) ergibt nur Sinn, wenn n eine natürliche Zahl (0 eingeschlossen) ist. Erst im Abschnitt "Binomiealkoeffizienten in der Analysis" sollte man für n beliebige Zahlen zulassen. Und dann unter Umständen diejenigen Identitäten bzw. Rechenregeln, die weiterhin gelten, wiederholen. --Digamma (Diskussion) 19:31, 4. Feb. 2014 (CET)

Ja, das leuchtet ein. Damit mein Edit nicht immer wiederkehrt, sollte man ganzzahliges k betreffend genau diesen Deinen Satz vorab knapp unterbringen. k spielt ja wirklich als Faktorenanzahl in der Definition eher die Rolle einer natürlichen Zahl als n, dessen separate Verallgemeinerung erstmal näher liegt als die von k. Andererseits könnte man dann dort vorn auch die reellen/komplexen n erstmal weglassen? (Und n=0 ist ja wohl erschöpfend ausdiskutiert ..). Kann erst heute abend noch mal gucken .. -- 77.185.241.195 11:00, 5. Feb. 2014 (CET)

Uff - vollbracht. Hoffentlich gefällt's diesmal, Digamma? Und Bnottelm? -- 77.185.162.78 06:43, 6. Feb. 2014 (CET) Falls jemand wirklich die komplexen n vorn im Artikel ganz verbannen möchte - fände ich auch gut. Habe nur versucht, den alten Ansatz nochmal sauberer durchzuziehen. -- 77.185.162.78 06:49, 6. Feb. 2014 (CET)

Sorry, hab heute nicht die Muße, muss ich mir später nochmal genauer ansehen. (Ich lass anderen gerne den Vortritt! :-) ) --Bnottelm (Diskussion) 22:51, 6. Feb. 2014 (CET)

Ditto. --Digamma (Diskussion) 16:18, 7. Feb. 2014 (CET)

Ich hab nun erstmal gesichtet und ein wenig nachgearbeitet, die Parserfehler nervten doch gewaltig! Jetzt lautet aber die goldene Preisfrage: warum bitte dauert das so verf***t lange, bis der Artikel geladen wird? Das Ändern selbst einiger weniger Zeichen ist eine regelrechte Folter! --Bnottelm (Diskussion) 19:12, 9. Feb. 2014 (CET)

Effizienter Algorithmus 2

Wenn n und k die Anzahl von Elementen in Mengen sein soll (siehe Einleitung), dann ist es überflüssig die Beschränkung auf ganzzahlige n zu erwähnen. Außerdem funktioniert der angegebene Algorithmus für alle n einschließlich komplexe Zahlen und für alle k, bei denen i nicht den Wert Null erhalten kann und "i ist kleiner oder gleich k" eine sinnvolle Aussage darstellt. Was Ergebnis der Rechnung dann aussagt ist eine andere Geschichte. Die Beschränkung auf ganze, positive Zahlen ist nur nötig, wenn man die Binomialkoeffizenten berechenen will und hat nichts mit dem Algorithmus zu tun. Wenn man ein Schweinekotlett braten will/soll, muß man ein Schweinekotlett nehmen, aber diese Beschränkung liegt in der Zielvorgabe und nicht in der Verarbeitungstechnik braten.

Es mag Taschenrechner geben, die den angegebenen Algorithmus verwenden und es mag auch welche geben, bei denen die Fakultät nur bis n=69 funktioniert, aber das ist nicht generell so - erst Recht nicht im enzyklopädischen Sinne. In diesem Zusammenhang sind die Abhandlungen zu nCr und nPr und ebenso deren subtile Parametereingabe bestenfalls individuelle Schräubchenkunde für einige Geräte und sollten gelöscht oder in einen anderen Zusammenhang gestellt werden.--46.115.176.148 10:22, 11. Sep. 2014 (CEST)

Bild

Ich finde das Bild eher verwirrend und würde es herausnehmen. Andere Meinungen?--Kamsa Hapnida (Diskussion) 15:51, 23. Apr. 2015 (CEST)

Ich bin der gleichen Meinung und habe das Bild - bevor ich diesen Beitrag gesehen habe - raus genommen. --Digamma (Diskussion) 20:16, 23. Apr. 2015 (CEST)

Bild n über k

Ich bitte um Erklärung, werde das Bild aber nicht mehr einstellen wollen. Da es sich um ein Anwendungsbeispiel des Binomialkoeffizienten bei einer Aufgabenstellung aus der Kombinatorik handelt, verstehe ich die Argumentation nicht. Könnte die Auseinandersetzung mit dem Bild nicht auch ein besseres Verständnis des Themas zur Folge haben? Die Verbindung zwischen Mathematik und Kunst ist leider selten, aber ist sie nicht auch naheliegend? Und sind interdisziplinäre Beiträge nicht auch verständnisfördernd? Grüße von Mathematische Bilder (10:52, 24. Apr. 2015 (CEST), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

Das wird gerade diskutiert auf https://de.wikipedia.org/wiki/Portal_Diskussion:Mathematik#Bilder_.28Kunst.29_zur_Illustrierung Damit die Diskussion nicht zerfasert bitte dort diskutieren.--Kamsa Hapnida (Diskussion) 14:04, 24. Apr. 2015 (CEST)

Monotonie

Fehlt nicht was über die Monotonie des Binomialkoeffizienten? Also monoton steigend bis k=n/2, dann fallend. Bei geradem n streng monoton, bei ungeradem streng bis auf eine stelle. Außerdem monoton steigend in k bei festem n, streng monoton hier in den nichttrivialen fällen. --2A02:908:F440:CE80:316D:E2CB:71F0:3662 10:46, 26. Apr. 2015 (CEST)

Beweise auslagern

Ich bin dafür, die vor kurzem eingestellten Beweise in eine Extraseite auszulagern, die hier nur verlinkt wird. Ansonsten ist dieser Artikel eindeutig zu formel-lastig.--JFKCom 23:45, 29. Okt. 2005 (CEST)

Ich würde es vorziehen, sie einfach zu löschen. Die erste Eigenschaft wird weiter unten noch bewiesen, die zweite und dritte sind Spezialfälle des binomischen Satzes, und für die vierte sollte sich mit einem Moment Nachdenken auch ein eleganterer Zugang finden lassen.--Gunther 00:27, 30. Okt 2005 (CEST)

Im Interesse dieses Artikels hast Du sicher recht; der Verfasser dieser Beweise hat sich aber sicher Mühe gegeben, und diese Beweise gehören so ein bißchen zum Standardrepertoire beim "Quälen" von Studenten mit Nebenfach Mathe. Deshalb finde ich sie irgendwie doch sinnvoll und würde sie nicht gleich wegschmeißen. Über solches aus Beweisen bestehendes Wissen muß es auch schon jede Menge Wiki-Diskussionen gegeben haben, die offenbar bis jetzt nicht auf den Punkt gekommen sind: Es wäre eine Neben-Wiki "Wikiproofs" nötig, nur um den Spielereien der Mathematik-Begeisterten (und der Neugier wißbegieriger Schüler, Studenten und einiger Lehrer u. Professoren) Genüge zu tun.--JFKCom 00:41, 30. Okt. 2005 (CEST)

WP:SM/S – der Text passt nicht unbedingt, aber die Überschrift irgendwie schon. Nur weil irgendwelche hässlichen Rechnungen Standardaufgaben sind, müssen sie hier nicht erwähnt werden (wie wäre es mit Induktionsbeweisen, die sind bestimmt noch viel fürchterlicher...).--Gunther 00:47, 30. Okt. 2005 (CEST)

Gibt's nicht irgendein Wikibook, wohin man das auslagern könnte? Ein eigener Artikel sind die Beweise auf jeden Fall nicht. --yuszuv 16:46, 30. Okt. 2005 (CET)

Es gibt sicher Bücher in de.wikibooks.org, aber ob man die Beweise dahin integrieren kann? --Arbol01 17:21, 30. Okt. 2005 (CET)

Ich habe den Abschnitt herausgenommen, in diesem Artikel ist er definitiv falsch. Wenn ein besserer Platz gefunden ist, kann man ihn ja aus der History holen.--Gunther 19:16, 4. Nov. 2005 (CET)

Wieso nicht einfach nach Binominalkoeffizient/Beweisführung verschieben? Dadurch wird es zwar technisch gesehen zu einem eigenen Artikel, aber solange es kein passendes Wikibook dafür gibt, ist dies sicher der beste Platz dafür. MovGP0 17:03, 22. Nov 2005 (CET)

Oder als Navigationsleiste Implementieren (siehe: Raytracing#Schnittpunkttests) MovGP0 01:29, 8. Dez 2005 (CET)

Bitte, lasst doch diese Trivialitäten unbewiesen, damit Studenten im ersten Semester bzw. knobelfreudigen Schülern auch noch einige einfache Aufgaben zur vollständigen Induktion zum selbständig Lösen übrigbleiben.--LutzL 17:36, 22. Nov. 2005 (CET)

Unübersichtlich

Der Artikel ist eine Ansammlung von Formeln, die teilweise doppelt vorkommen. Zu den einzelnen Formeln müßten Erklärungen beigefügt werden. --Arbol01 16:28, 3. Sep. 2005 (CEST)

Seh ich genauso !! --(nicht signierter Beitrag von 84.56.247.51 (Diskussion) 15:16, 30. Okt. 2005 (CET))

Mittlerweile gibt es einige Beispiele und Veranschaulichungen, dennoch stehen weiterhin sehr viele Formeln sehr wenig Erklärungen gegenüber. Ich meine, dass der Punkt, trotz dieser Verbesserungen daher immernoch aktuell ist. Gruß! GS63 (Diskussion) 17:22, 4. Jan. 2020 (CET)