Eine verallgemeinerte Version des Inklusions-Ausschluss-Prinzips unter Verwendung einer binomialen Identität

Ich versuche, einen Weg zu finden, um ein verallgemeinertes Inklusions-Ausschluss-Prinzip für die Anzahl der Elemente abzuleiten, die sich im Schnittpunkt von mindestens befinden S setzt ab A 1 , A 2 , . . . , A N mit dieser Identität:

lassen k Und S positive ganze Zahlen sein und lassen k ≥ S ≥ 1

∑ ich = 0 k − S ( − 1 ) ich ( S − 1 + ich S − 1 ) ( k S + ich ) = 1

Ich komme von dieser Frage: Beweis, dass die Binomialsumme gleich 1 ist

Aus der Summe geht hervor, dass das, was bestimmt, ob wir das Produkt des Binomialkoeffizienten addieren oder subtrahieren, darin besteht, ob es eine gerade oder ungerade Anzahl von Elementen hat, und es kann auf jede Teilmenge von $s angewendet werden.

Aber ich verstehe das Konzept der verallgemeinerten Form des Inklusions-Ausschluss-Prinzips nicht ganz.

Antworten (1)

Ein verallgemeinertes Einschluss-Ausschluss-Theorem finden Sie in dieser Antwort . In dieser Antwort besagt das Theorem, dass die Anzahl der Elemente genau ist k der Sets ist

∑ J = 0 M ( − 1 ) J − k ( J k ) N ( J )
Korollar 2 besagt, dass die Anzahl der Elemente in mindestens k der Sets ist
∑ J = k M ( − 1 ) J − k ( J − 1 J − k ) N ( J )
Wo ( − 1 N ) = ( − 1 ) N ( N N ) = ( − 1 ) N [ N ≥ 0 ] .

Nachweis der Identität

Wenn k ≥ S , Dann

(1) ∑ ich = 0 k − S ( − 1 ) ich ( S − 1 + ich S − 1 ) ( k S + ich ) = ∑ ich = 0 k − S ( − 1 ) ich ( S − 1 + ich ich ) ( k k − S − ich ) (2) = ∑ ich = 0 k − S ( − S ich ) ( k k − S − ich ) (3) = ( k − S k − S ) (4) = 1
Erläuterung:
( 1 ) : ( N k ) = ( N N − k ) für N ≥ 0 Und N ∈ Z
( 2 ) : ( − N k ) = ( − 1 ) k ( N + k − 1 k )
( 3 ) : Vandermondes Identität
( 4 ) : ( N N ) = 1 für N ≥ 0 Und N ∈ Z

Eine verallgemeinerte Version des Inklusions-Ausschluss-Prinzips unter Verwendung einer binomialen Identität
AntwortenHierDatenschutz-Bestimmungen1y, 0v