Diskussion:Binomialkoeffizient

Auf dieser Seite werden Abschnitte monatlich automatisch archiviert, deren jüngster Beitrag mehr als 900 Tage zurückliegt und die mindestens einen signierten Beitrag enthalten. Um die Diskussionsseite nicht komplett zu leeren, verbleiben mindestens 5 Abschnitte.

Auf dieser Seite werden Abschnitte monatlich automatisch archiviert, deren jüngster Beitrag mehr als 540 Tage zurückliegt und die mindestens 2 signierte Beiträge enthalten. Um die Diskussionsseite nicht komplett zu leeren, verbleiben mindestens 5 Abschnitte.

Auf dieser Seite werden Abschnitte montags automatisch archiviert, wenn sie mit {{Erledigt|1=--~~~~}} markiert sind und ihr jüngster signierter Beitrag mehr als 30 Tage zurückliegt. Um die Diskussionsseite nicht komplett zu leeren, verbleibt mindestens ein Abschnitt.

Archiv

Archiv

Wie wird ein Archiv angelegt?

Fehler

Da steht:

Für [...] $n\neq 0$ [...]

Für alle anderen ganzen Zahlen $n,k$ wird ${n \choose k}=0$ definiert.

Ebenso steht da aber auch: ${0 \choose 0}=1$. Passt ja wohl nicht zusammen.

Das $n\not =0$ ist Unsinn, habe es zusammen mit dem {{Überarbeiten}}-Baustein entfernt. Oder war da noch was?--Gunther 11:30, 17. Jan. 2006 (CET)

Nö, das war das einzige, was mir aufgefallen war ;-) – 130.75.236.4 11:55, 17. Jan. 2006 (CET)

Ergänzung: Da steht ja auch noch $\prod _{i=1}^{k}{\frac {n-(i-1)}{i}}$, was für n = 0 ja Unsinn ist, weil i ja nicht von 1 auf 0 gehen kann. Also geht diese Definition tatsächlich nur für n > 0. – 130.75.236.4 12:00, 17. Jan. 2006 (CET)

---

k=0 ist problematisch, ein leeres Produkt hat nach allgemeiner Konvention den Wert 1. n ist beliebig, negativ, rational, reell, komplex,... die Produktformel liefert immer einen Wert.--LutzL 17:32, 21. Jun. 2006 (CEST)

Abschnitt „Algorithmus zur effizienten Berechnung“

Ich sehe, über die effiziente Berechnung von Binomialkoeffizienten wurde hier heftig gestritten. Mich treibt in diesem Abschnitt aber eine andere Frage um: Woher kommt die Aussage, die Rechenkapazität von Taschenrechnern wäre bei Nichtnutzung der angegebenen Methode für $n=69$ erschöpft? Wo kommt diese Zahl her? Für mich sieht die Sache so aus:

• ${66 \choose 33}=7219428434016265740<9223372036854775808=2^{63}$ und
• ${67 \choose 33}=14226520737620288370>9223372036854775808=2^{63}$,

also ist so oder so bei $n=66$ Schluss: Für größere $n$ passt der Binomialkoeffizient nicht mehr unbedingt in einen vorzeichenbehafteten 64-bit-Integer. (Man beachte, dass $\max _{0\leq k\leq n}{n \choose k}={n \choose \left\lfloor {\frac {n}{2}}\right\rfloor }$, siehe auch Satz von Sperner.) Man kann das Ganze natürlich auch für die vorzeichenlose Variante durchrechnen, dann ist erst bei $n=67$ Schluss; und wenn man nicht die im Artikel angegebene Berechnungsvariante verwendet, in beiden Fällen vermutlich bei noch viel kleineren Werten für $n$.

Außerdem möchte ich nicht ausschließen, dass Taschenrechner (als eingebettete Systeme) nicht mit 64-bit-Zahlen, sondern mit kürzeren Repräsentationslängen rechnen. Andererseits ist es ebenfalls denkbar, dass moderne Taschenrechner aus Präzisionsgründen noch breitere oder sogar beliebig lange Zahlendarstellungen unterstützen. --77.188.80.200 16:12, 17. Jul. 2017 (CEST)

Die Grenze $n=69$ ist wohl eine Folge der Annahme, daß man zur Bestimmung eines Binomialkoeffizienten der Berechnung von Fakultäten bedürfe. Denn es gilt $69!<10^{99}<10^{100}<70!$, sodaß bei der üblichen Gleitkommadarstellung mit (durch zwei angezeigte dezimale Stellen) limitiertem Exponenten zwar $69!,$ aber nicht $70!$ angezeigt werden kann. Franz 18:32, 17. Jul. 2017 (CEST)

Problem mit dem "Algorithmus zur effizienten Berechnung"

Wenn man den Pseudocode "naiv" in eine Programmiersprache überträgt, die bei Ganzzahlwerten (als solche wird man n und k i.d.R. deklarieren) nach jeder Operation (relevant ist hier die Division) das (Zwischen-)Ergebnis erforderlichenfalls zu einer Ganzzahl rundet (was u.a. auf C/C++ und Java zutrifft), erhält man falsche Ergebnisse.

#include <iostream>

unsigned int binomialkoeffizient (unsigned int n, unsigned int k) {
    if (k == 0) return 1;
    if (2*k > n) return binomialkoeffizient(n, n-k);
    return (n+1-k) / k * binomialkoeffizient(n, k-1);
}

unsigned int binomialkoeffizient_korrekt (unsigned int n, unsigned int k) {
    if (k == 0) return 1;
    if (2*k > n) return binomialkoeffizient_korrekt(n, n-k);
    return binomialkoeffizient_korrekt(n, k-1) * (n+1-k) / k;
}

int main () {
    std::cout << "4 ueber 2: " << binomialkoeffizient(4, 2) << ' ' << binomialkoeffizient_korrekt(4, 2) << '\n'; // 4 6
}

Ich habe den Pseudocode angepaßt, damit das Problem nicht mehr auftritt und auch sonst etwas verändert. --(nicht signierter Beitrag von 212.29.34.233 (Diskussion) 17:45, 27. Jul. 2017 (CEST))

1. Es ist mir völlig unerklärlich, wie man in einem ausdrücklich als „Pseudocode“ deklarierten Text einen Slash / nicht als „normalen“ Divisionsoperator interpretieren kann (also z. B. wie Du glauben kann, 9 / 2 sollte nicht zu 4,5 ausgewertet werden, sondern zu 4.
2. Darüber hinaus ist Deine Lösung des „Problems“ durch Faktorenvertauschung untauglich: Bei Deinem Beispiel ${10 \choose 3}$ würde das neue Programm zunächst mit ($n=10$ und) $k=3$ aufgerufen, dann (bevor die folgende Multiplikation mit $(10-k+1)/k$ auch nur erkannt, geschweige denn ausgeführt wird) mit $k=2,$ dann mit $k=1$ und schließlich mit $k=0.$ Bis jetzt ist noch überhaupt nichts gerechnet worden, erst dieser letzte Aufruf des Programms führt (weil nun $k=0$ ist) zur Rückgabe 1. Ich würde meinen, daß das Programm mit dieser Rückgabe 1 sogar stoppt, aber auch eine andernfalls noch erfolgende (einmalige und abschließende) Multiplikation mit $(10-k+1)/k$ würde nichts daran ändern, daß das Programm nicht die beabsichtigte Rückgabe liefert (ja, wegen einer Division durch 0 sogar abstürzen würde, weil die interne Variable k nun ja schon mit dem Wert 0 belegt ist).

Ich werde Deine Änderung daher (der Einfachheit halber komplett) zurücksetzen. Dabei lasse ich aber ausdrücklich offen, ob (a) Deine Vertauschung der ersten zwei Codezeilen und/oder (b) Deine Zusatzbemerkung über Iteration nicht doch wieder aufgenommen werden sollten. Du kannst diese beiden Punkte jedenfalls gerne hier zur Diskussion stellen, und ich werde mich in die Entscheidung über diese beiden Detailfragen dann nicht mehr einmischen. Gruß, Franz 00:38, 28. Jul. 2017 (CEST)

Der 2. Punkt ist sicherlich kein Problem. Das kriegt der Compiler schon auf die Reihe ;-) Der deutliche Vorteil der Reihenfolge binomialkoeffizient(n, k-1) * (n+1-k) / k scheint mir aber zu sein, dass dabei ausschließlich Rechenoperationen mit ganzen Zahlen ausgeführt werden (wenn n ganz ist). Das war im Artikel wohl auch so gedacht, denn ein paar Zeilen weiter oben steht „Zusätzlich sind auch alle Zwischenergebnisse natürliche Zahlen.“ Grüße -- HilberTraum (d, m) 19:47, 28. Jul. 2017 (CEST)

Ich habe den Revert und Beitrag von FranzR erst jetzt gesehen. Hättest Du meinen Beitrag in der Diskussion genau gelesen, wäre Dir aufgefallen, daß ICH nicht glaube, der / im Pseudocode wäre ein Ganzzahl-Divisionsoperator (wie z.B. in C), aber die Gefahr sehe, daß andere Personen, die den Artikel zu Rate zu (z.B. Schüler, die den Binomialkoeffizienten in einer Programmiersprache implementieren wollen/sollen), ihn dahingehend mißverstehen. Außerdem möchte ich Dir empfehlen (ich erlaube mir einmal, deinen latent überheblichen Sprachduktus zu übernehmen), Dich etwas mit Rekursion in der Informatik zu beschäftigen. Dann würde Dir nämlich auffallen, daß es keine "interne Variable k" gibt, die "schon belegt" sein könnte, sondern daß der Parameter k bei jedem (rekursiven) Aufruf der Funktion unabhängig einen anderen Wert annehmen kann (in imperativen Sprachen typischerweise durch einen eigenen Stackframe implementiert). Und deshalb liefert der Aufruf binomialkoeffizient_korrekt(10, 3) auch den korrekten Wert von 120 (ausprobiert mit gcc). -- 212.29.34.233 17:34, 2. Aug. 2017 (CEST)

Ich habe den Code durch die Version vom 24. Oktober ersetzt. Sie ist in vielerlei Hinsicht sinnvoller und passt besser zum Text drumherum (klar: es wurde am 27. Oktober ja nur der Code geändert ;) ). --Daniel5Ko (Diskussion) 00:27, 3. Aug. 2017 (CEST)

Summe verschobener Binomialkoeffizienten

Ich glaube, in dem Abschnitt ist ein Fehler. Auf der rechten Seite dürfte im unteren Term des Binonialkoeffizienten nicht n+1 sondern der obere Index m stehen, oder? Richtig wäre meiner Meinung nach: $\sum _{k=0}^{m}{\binom {n+k}{k}}={\binom {m+n+1}{m}}$ Steht zumindest so in Graham, Concrete Mathematics Seite 161 und Wolfram Alpha rechnet es auch so aus. --Sascha Laing (Diskussion) 13:34, 27. Apr. 2022 (CEST)

Ne, ist identisch, denn

${\binom {m+n+1}{m}}={\binom {m+n+1}{(m+n+1)-m}}={\binom {m+n+1}{n+1}}$

ist ja gültig, siehe Abschnitt Symmetrie der Binomialkoeffizienten. --Bnottelm (Diskussion) 17:49, 28. Apr. 2022 (CEST)

Ach ja, danke dir! --Sascha Laing (Diskussion) 13:34, 9. Mai 2022 (CEST)

Summen von Binomialkoeffizienten mit geraden bzw. ungeraden Anzahlen ausgewählter Objekte

Ist denn nun die obere oder die untere Gaußklammer gemeint? (Und man sollte vielleicht \left und \right verwenden, aber das nur nebenbei.) --2A02:8108:50BF:C694:99B:FBDC:9F83:F23C 12:08, 15. Sep. 2022 (CEST)