tWie viele Möglichkeiten gibt es, eine Menge S unter den folgenden Einschränkungen in zwei Teilmengen aufzuteilen?

Auf wie viele Arten können wir eine Menge S in zwei Teilmengen aufteilen, so dass:

Der Satz S haben kann N Elemente im Sortiment 1 Zu 1000 (inklusive). Seien die beiden Teilmengen A Und B . Für alle X im Bereich 1 Zu 1000 Wir zählen die Anzahl der Elemente in jeder Teilmenge, die gleich sind X . Lassen Sie den Satz A hat A Elemente gleich X , und und der Satz B hat B Elemente gleich X . Wir berechnen die Summe aller solcher A 's und B 'S. Nun, wie man bestimmt, wie viele Teilmengen die Summe aller sind A 's ist mehr als die Summe all dessen B 's (ohne tatsächlich alle Teilmengen zu durchlaufen)

Beispiel:

Lassen S = { 1 , 1 , 3 , 2 } in diesen Fällen lautet die Antwort 5 . Und die Teilmenge Wahl von A Sind: { 1 , 1 , 3 } , { 1 , 1 , 2 } , { 1 , 3 , 2 } , { 1 , 3 , 2 } , { 1 , 1 , 3 , 2 }

Bitte beachten Sie: Beide Partitionen können bei diesem Problem leer sein.

Geben Ihnen diese Summen nicht nur die Anzahl der Elemente von A und von B ? Also bekommst du nicht einfach alle Partitionen wo A hat mehr Elemente als B ?
Normalerweise kann eine Menge nicht zwei gleiche Elemente haben, also { 1 , 1 , 3 , 2 } wäre kein Satz. Eine Multimenge kann gleiche Elemente haben. Wenn S eine Menge sein muss, hat Gerry Myerson Recht, dass die Summen nur die Anzahl der Elemente sind A Und B . Versuchen Sie, die Anzahl der Paare zu berechnen A , B wo die Größe von A ist größer als die Größe von B ? Tun A Und B auspowern müssen S ?
@RossMillikan Das würde ich sagen { 1 , 1 , 3 , 2 } ist ein Satz, es ist einfach gleich { 1 , 3 , 2 } (sowie zu { 1 , 2 , 3 } usw.) Bei der üblichen Entwicklung der axiomatischen Mengenlehre ist es wichtig, dass die Paarungsoperation verwendet werden kann, um Singletons zu erhalten { X , X } .

Antworten (1)

Dabei geht es eigentlich nicht um Mengen, sondern um so etwas: Für jede Zahl k , geben Sie eine maximale Anzahl an S ( k ) ∈ N 0 von Vorkommnissen. Es gibt nur endlich viele k mit S ( k ) ≠ 0 . Wir wollen alle möglichen Wahlmöglichkeiten für Funktionen finden A so dass 0 ≤ A ( k ) ≤ S ( k ) für alle k Und ∑ k A ( k ) > 1 2 ∑ k S ( k ) .

Wenn wir die Bedingung fallen lassen ∑ k A ( k ) > 1 2 ∑ k S ( k ) Für einen Moment gibt es sie ∏ k ( S ( k ) + 1 ) mögliche Funktionen A . Lassen σ = ∑ k S ( k ) . Für jeden A mit ∑ k A ( k ) < 1 2 σ , sein Komplement hat Summe > 1 2 σ . Daher, wenn σ ungerade ist, dann ist die gesuchte Zahl einfach

(1) 1 2 ∏ k ( S ( k ) + 1 ) .
Wie auch immer, wenn σ gerade ist, müssen wir die Anzahl der Funktionen explizit zählen A so dass ∑ k A ( k ) = 1 2 σ und subtrahieren Sie dann die Hälfte dieser Zahl von ( 1 ) . Das Zählen in diesem Fall, denke ich, wird am besten mit den Techniken der dynamischen Programmierung durchgeführt ...

Ausgezeichnete Antwort. +1
tWie viele Möglichkeiten gibt es, eine Menge S unter den folgenden Einschränkungen in zwei Teilmengen aufzuteilen?
AntwortenHierDatenschutz-Bestimmungen1y, 0v