Wie viele Elemente hat P(A)P(A)\mathcal{P}(A)?

Lassen A ein Satz der Größe fünfzehn sein. Lassen P ( A ) bezeichnen die Potenzmenge von A , das ist die Menge aller Teilmengen von A . Wie viele Elemente hat P ( A ) enthalten?

Das ist dasselbe wie Sein 0 oder 1 , binäre Größensätze 1 → 14 ?

Bedeutet dies, dass die Antwort lautet

( 15 0 ) + ( 15 1 ) + ( 15 2 ) + ⋯ + ( 15 13 ) + ( 15 14 ) + ( 15 15 ) ?

Oder fällt mir etwas nicht ein?

Von Größe 0 Zu 15 . Dein Ausdruck ist richtig. Es wird nicht wirklich benötigt, die Nummer ist 2 15 .
Ihre Antwort ist richtig, aber beachten Sie, dass sie in einer viel einfacheren Form ausgedrückt werden kann, nämlich ( 1 + 1 ) 15 = 2 15 . Das ergibt sich aus dem Binomialsatz: ( X + j ) N = ∑ k = 0 N ( N k ) X k j N − k mit X = j = 1 . Eine andere Möglichkeit, darüber nachzudenken, ist, dass jeder der 15 Elemente können eingeschlossen oder ausgeschlossen werden, also gibt es 2 15 Möglichkeiten.
@Bungo Ahhh, das war die Richtung, in die meine Logik mit dem binären Vergleich ging, aber ich denke, es hat nicht vollständig geklickt!
Oder Sie können sogar mit Induktion zeigen, dass jede Potenzmenge einer endlichen Menge Kardinalität hat 2 #  Satz
@JoseAntonio Das war 2  Größe des Sets  ?
Ja, oder Sie können eine bijektive Karte aus anzeigen { 0 , 1 } N → P ( N ) und das Ergebnis ist fast trivial, Hinweis: Verwenden Sie die Indikatorfunktion. N ist der Satz mit N Elemente Entschuldigung für die Notation ist spät

Antworten (1)

Ihre Summe ist richtig, und im Allgemeinen:

( N 0 ) + ( N 1 ) + ( N 2 ) + ⋯ + ( N N − 1 ) + ( N N ) = 2 N .

Eine andere Möglichkeit, Ihre Summe zu realisieren, ist also 2 15 .

Ein kombintorischer Beweis, dass die Größe der Potenzmenge von an N Elementsatz A Ist 2 N (die auch verwendet werden kann, um die obige Identität zu beweisen) lautet wie folgt.

Es gibt eine Bijektion zwischen Teilmengen X ⊂ A Und N -Bit-Binärsequenzen, in denen eine 1 steht ich te Position der Sequenz, wenn die ich tes Element von A befindet sich in der entsprechenden Teilmenge. Es ist leicht zu zeigen, dass dies eine Bijektion ist. Außerdem ist die Zahl der N -Bit-Binärfolgen ist eindeutig 2 N (Sie haben zwei Möglichkeiten für jede der N Bits). Dies beweist die Behauptung.

Danke, das macht Sinn! Eine weitere Frage: Wie viele Bitfolgen gibt es, die genau neun enthalten? 0 's und sechs 1 's, wenn auf jede 1 unmittelbar ein a folgen muss 0 ? Würde ich die koppeln 10 holt mich auf 3 0 's und 6 Paare, was bedeutet, dass ich mir nur die Anzahl der Kombinationen davon ansehen muss? 9 ! 6 ! 3 !
Ja, das ist richtig, wenn Sie es so umschreiben, dass jedes der "10" Paare eine 2 wäre, dann zählen Sie die Anzahl der Möglichkeiten, drei 0en und sechs 2en anzuordnen, was ergibt 9 ! 3 ! 6 ! .
Es stellt sich heraus, dass aus diesem Grund die Leistung eingestellt wird A wird manchmal geschrieben 2 A .
Wie viele Elemente hat P(A)P(A)\mathcal{P}(A)?
AntwortenHierDatenschutz-Bestimmungen1y, 0v