Reorganisieren der alternierenden Summe von Produkten von Binomialkoeffizienten

Die Summe

∑ k = 0 ⌊ P S ⌋ ( − 1 ) k ( N k ) ( P − k S + N − 1 N − 1 ) ; N > 0 , S > 0  Und  0 ≤ P ≤ N S ,
mit ( N k ) den Binomialkoeffizienten bezeichnet, hat die Einschränkung, dass Ganzzahlen mit fester Größe implementiert sind, gibt es Fälle, in denen einzelne Terme die Ganzzahlgröße überschreiten, obwohl das Ergebnis dies nicht tut. (Selbst unter der Annahme einer idealen Berechnung von Binomialkoeffizienten.) Gibt es eine Möglichkeit, diese Summierung neu zu organisieren, um dies zu vermeiden? Es kann angenommen werden, dass die ganzzahlige Größengrenze ist S N , die Summe dieses Ergebnisses für alle P . Ein stärkeres Ergebnis wäre, dass alle summierten Terme ihre Summe im absoluten Wert nicht überschreiten. Ein noch stärkeres Ergebnis wäre, dass alle summierten Terme nichtnegativ sind. Aber auch der schwächste Fall ist in Ordnung.

Willkommen bei MSE. Für einige grundlegende Informationen über das Schreiben von Mathematik auf dieser Seite siehe zB grundlegende Hilfe zur mathjax-Notation , mathjax - Tutorial und Schnellreferenz , Haupt-Meta-Site-Mathe-Tutorial und Anleitungen zum Bearbeiten von Gleichungen .
Wechselnde Summen wie diese können oft als Einschluss-Ausschluss-Formel interpretiert und zu einem einfacheren Ausdruck von Binomialkoeffizienten vereinfacht werden. Sehen Sie sich diese aktuelle Antwort für eine wechselnde Summe an, die Ihrer sehr ähnlich sieht.

Antworten (3)

Ich kann Ihre Frage nicht genau beantworten, aber vorausgesetzt, Sie versuchen, diese Summe zu berechnen, während Sie einen Ganzzahlüberlauf vermeiden, hier ist ein Trick, der funktionieren könnte. Lassen A k sei der absolute Wert der k T H Summanden in deiner Summe. Das können Sie anhand der Zahlen beweisen A k bis zu einem gewissen Punkt erhöhen und danach wieder verringern. Dies impliziert, dass Ihre Wechselsumme nach oben durch die größte begrenzt ist A k . Vermietung M = max k A k , können Sie berechnen M im Voraus, und dann berechnest du stattdessen die Summe mit allen modulo durchgeführten Additionen M . Dadurch wird sichergestellt, dass Sie niemals Teilberechnungen haben, die größer sind als M , während Sie immer noch die richtige Antwort geben.

Das ist eine sehr nützliche Erkenntnis. Ich kann es in meinem speziellen Fall verbessern, indem ich weiß, dass die Summe aller solcher Summen (die alle positiv sind) ist S N , Und S N läuft in meiner Anwendung nicht über, könnte also jeden Term modulo berechnen S N . Was in dem Rahmen, den ich habe, nicht trivial ist, aber es wert ist, weiterverfolgt zu werden.

Wenn der Summenindex k ging auf N anstatt P / S ≤ N , wäre es die Einschluss-Ausschluss-Formel für die Anzahl von ( N − 1 ) -Teilmengen von { 1 , … , P + N − 1 } die mindestens ein Element von jedem der folgenden enthalten N disjunkte Intervalle:

{ 1 , … , S } { S + 1 , … , 2 S } ⋮ { ( N − 1 ) S + 1 , … , N S }
Die Anzahl solcher Teilmengen ist eindeutig 0 Weil N > N − 1 . Wie in der verknüpften Antwort können Sie verallgemeinern, indem Sie die ersetzen N − 1 mit jeder Zahl kleiner als N und immer noch dasselbe erhalten 0 Ergebnis.

Ihre Summe ist also

∑ k = 0 ⌊ P / S ⌋ ( − 1 ) k ( N k ) ( P − k S + N − 1 N − 1 ) = − ∑ k = ⌊ P / S ⌋ + 1 N ( − 1 ) k ( N k ) ( P − k S + N − 1 N − 1 )

Dieses Ergebnis ist nicht 0. Es ist eigentlich die Anzahl der Möglichkeiten, wie die Summe von n s-seitigen Würfeln, die jeweils von 0 bis s-1 nummeriert sind, p ist.
Okay, ich wollte zusammenfassen k = N , aber Ihre Summe wird bei abgeschnitten P / S ≤ N .

Wenn Sie wissen, dass die endgültige Antwort in die feste Ganzzahlgröße passt, müssen Sie sich keine Gedanken über einen Zwischenüberlauf machen. Berechnung mit, sagen wir, 64 -Bit-Ganzzahlen entspricht der Modulo-Berechnung 2 64 . Selbst wenn Zwischenantworten überlaufen und Ihnen etwas geben, das nur modulo richtig ist 2 64 es garantiert immer noch, dass die endgültige Antwort modulo korrekt ist 2 64 , was eigentlich richtig sein wird.

Also zum Beispiel in 8 -bit Integer-Arithmetik, die ich berechnen kann

100 + 200 − 50 − 150
und bekomme 100 , obwohl die Teilsummen nicht hineinpassen 8 Bits:

  • Mit unsigniert 8 -Bit-Ganzzahlen, 100 + 200 dazu kommen würde 44 , subtrahieren 50 ergäbe 250 , und subtrahieren 150 ergäbe 100 .
  • Mit signiert 8 -Bit-Ganzzahlen, würden die einzelnen Terme nicht einmal passen, und wir würden rechnen 100 + ( − 56 ) − 50 − ( − 106 ) . Die Teilsummen wären 100 + ( − 56 ) = 44 , 44 − 50 = − 6 , Und − 6 − ( − 106 ) = 100 .
Leider ist es aus Gründen, die außerhalb der reinen Mathematik liegen, nicht ganz so einfach, sich in der von mir verwendeten Umgebung auf die überlaufende Umhüllung zu verlassen. Aber Modulo ist der richtige Weg, wie ich basierend auf einer anderen Antwort implementiert habe. Aber es stellt sich dann heraus, dass Sie die Binomialkoeffizienten modulo berechnen müssen, was auch immer Sie verwenden (ich habe verwendet S N ) und das geht nicht einfach durch Überlaufen. Ich habe einen Hinweis von anderswo verwendet, um dafür eine zwischengespeicherte Version der additiven Wiederholungsrelation zu verwenden, wiederum modulo S N .
Es stimmt, es ist nicht einfach, einen Binomialkoeffizienten zu berechnen, der in eine 64-Bit-Ganzzahl passt, wenn die Zwischenschritte, um ihn zu finden, nicht passen. Wenn zumindest k ! ( N k ) immer noch klein genug wäre, wäre es einfach, aber darüber hinaus müssen Sie vielleicht etwas kniffliger machen.
Reorganisieren der alternierenden Summe von Produkten von Binomialkoeffizienten
AntwortenHierDatenschutz-Bestimmungen1y, 0v