Aufteilung eines Satzes

Eine Reihe von Briefmarken, die in Bündel aufgeteilt sind: Kein Stempel befindet sich in zwei Bündeln, kein Bündel ist leer und jeder Stempel befindet sich in einem Bündel.

Das 52 Partitionen eines Satzes mit 5 Elementen. Ein farbiger Bereich zeigt eine Teilmenge von X an, die ein Mitglied der umschließenden Partition bildet. Unbekundete Punkte weisen auf Einzelelement-Untergruppen hin. Die erste gezeigte Partition enthält fünf Einselement-Untergruppen; Die letzte Partition enthält eine Teilmenge mit fünf Elementen.

Die traditionellen japanischen Symbole für die 54 Kapitel der Geschichte von Genji basieren auf den 52 Methoden zur Verteilung von fünf Elementen (die beiden roten Symbole repräsentieren dieselbe Partition, und das grüne Symbol wird zum Erreichen von 54 hinzugefügt).^[1]

Im Mathematik, a Aufteilung eines Satzes ist eine Gruppierung seiner Elemente in nicht leer Untergruppenso, dass jedes Element in genau einer Teilmenge enthalten ist.

Jeder Äquivalenzbeziehung auf einen einstellen Definiert eine Partition dieses Satzes und jede Partition definiert eine Äquivalenzbeziehung. Ein Set, der mit einer Äquivalenzbeziehung oder einer Partition ausgestattet ist setoid, normalerweise in Typentheorie und Beweistheorie.

Definition und Notation

Eine Partition eines Satzes X ist eine Reihe von nicht leeren Untergruppen von X so dass jedes Element jedes Element x in X ist genau in einem dieser Untergruppen^[2] (d. h., X ist ein Union Union der Untergruppen).

Äquivalent, a Familie der Sets P ist eine Teilung von X Wenn und nur wenn alle folgenden Bedingungen gelten:^[3]

• Die Familie P enthält das nicht die leeres Set (das ist ${\ displayStyle \ leereSet \ notin p}$).
• Das Union der Sets in P ist gleich X (das ist ${\ displaystyle \ textstyle \ bigcup _ {a \ in p} a = x}$). Die Sets in P werden gesagt Auspuff oder Startseite X. Siehe auch gemeinsam erschöpfende Ereignisse und Cover (Topologie).
• Das Überschneidung von zwei beliebigen Sets in P ist leer (das heißt ${\ displayStyle (\ forall a, b \ in p) \; a \ neq b \ impliziert a \ cap b = \ leerSet}$). Die Elemente von P sollen sein paarweise disjunkt.

Die Sets in P werden als die genannt Blöcke, Teile, oder Zellen, der Partition.^[4] Wenn ${\ displayStyle a \ in x}$ Dann repräsentieren wir die Zelle, die enthält a durch ${\ displayStyle [a]}$. Das heißt, ${\ displayStyle [a]}$ ist Notation für die Zelle in P was beinhaltet a.

Jede Partition, Pkann mit einer Äquivalenzbeziehung auf identifiziert werden X, nämlich die Beziehung ${\ displayStyle \ Sim _ {p}}$ so dass für jeden ${\ displayStyle a, b \ in x}$ wir haben ${\ displayStyle a \ sim _ {p} b}$ dann und nur dann, wenn ${\ displayStyle a \ in [b]}$ (äquivalent, wenn und nur wenn ${\ displayStyle b \ in [a]}$). Die Notation ${\ displayStyle \ Sim _ {p}}$ Evoziert die Idee, dass die Äquivalenzbeziehung aus der Partition aufgebaut werden kann. Umgekehrt kann jede Äquivalenzbeziehung mit einer Partition identifiziert werden. Aus diesem Grund wird manchmal informell gesagt, dass "eine Äquivalenzbeziehung die gleiche ist wie eine Partition". Wenn P ist die Partition, die mit einer bestimmten Äquivalenzbeziehung identifiziert wurde ${\ displayStyle \ Sim}$dann schreiben einige Autoren ${\ displayStyle p = x/\ sim}$. Diese Notation deutet auf die Idee hin, dass die Partition der Satz ist X in Zellen unterteilt. Die Notation erinnert auch an die Idee, dass man aus der Äquivalenzbeziehung die Partition konstruieren kann.

Das Rang von P ist |X| - |P|, wenn X ist endlich.

Beispiele

• Das leere Set ${\ displayStyle \ leereSet}$ hat genau eine Partition, nämlich ${\ displayStyle \ leereSet}$. (Hinweis: Dies ist die Partition, nicht ein Mitglied der Partition.)
• Für jeden nicht leeren Satz X, P = {{ X } ist eine Partition von X, genannt triviale Partition.
  • Besonders alles Singleton -Set {x} hat genau eine Partition, nämlich {{{{x}}.
• Für alle nicht leeren echte Teilmenge A eines Satzes U, der Satz A zusammen mit seinem ergänzen bilden eine Partition von U, nämlich {{ A, U ∖ A }.
• Der Satz {1, 2, 3} hat diese fünf Partitionen (eine Partition pro Element):
  • {{1}, {2}, {3}}, manchmal geschrieben 1 | 2 | 3.
  • {{1, 2}, {3}} oder 1 2 | 3.
  • {{1, 3}, {2}} oder 1 3 | 2.
  • {{1}, {2, 3}} oder 1 | 2 3.
  • {{1, 2, 3}} oder 123 (in Kontexten, in denen es keine Verwirrung mit der Nummer gibt).
• Das Folgende sind keine Partitionen von {1, 2, 3}:
  • {{}, {1, 3}, {2}} ist keine Partition (eines Satzes), weil eines seiner Elemente das ist leeres Set.
  • {{1, 2}, {2, 3}} ist keine Partition (eines Satzes), da das Element 2 in mehr als einem Block enthalten ist.
  • {{1}, {2}} ist keine Partition von {1, 2, 3}, da keine seiner Blöcke 3 enthält; Es handelt sich jedoch um eine Partition von {1, 2}.

Partitionen und Äquivalenzbeziehungen

Für jeden Äquivalenzbeziehung auf einem Set X, der Satz seiner Äquivalenzklassen ist eine Teilung von X. Umgekehrt aus jeder Partition P von XWir können eine Äquivalenzbeziehung auf definieren X indem man es einstellt x ~ y Genau wann x und y sind im selben Teil in P. Somit sind die Begriffe der Äquivalenzbeziehung und der Teilung im Wesentlichen gleichwertig.^[5]

Das Axiom der Wahl Garantien für jede Partition eines Satzes X die Existenz einer Untergruppe von X enthält genau ein Element aus jedem Teil der Partition. Dies impliziert, dass bei einer Äquivalenzbeziehung auf einem Satz a auswählen kann a kanonisches repräsentatives Element aus jeder Äquivalenzklasse.

Verfeinerung von Partitionen

Partitionen eines 4-Sets, das von bestellt wurde Raffinesse

Eine Partition α eines Satzes X ist ein Raffinesse einer Partition ρ von X- Und das sagen wir α ist feiner als ρ und das ρ ist Größe als α- Wenn jedes Element von α ist eine Untergruppe eines Elements von ρ. Informell bedeutet dies, dass das α ist eine weitere Fragmentierung von ρ. In diesem Fall wird geschrieben, dass α ≤ ρ.

Dies feiner als Beziehung zum Satz der Partitionen von X ist ein Teilreihenfolge (Die Notation "≤" ist also angemessen). Jeder Satz von Elementen hat a am wenigsten Obergrenze und ein greatest lower bound, so dass es a bildet Gitterund genauer gesagt (für Partitionen eines endlichen Satzes) ist es a Geometrisches Gitter.^[6] Das Partitionsgitter eines 4-Element-Satzes hat 15 Elemente und wird in der dargestellt Hasse -Diagramm auf der Linken.

Basierend auf Kryptomorphismus zwischen geometrischen Gitter und MatroidenDieses Gitter von Partitionen eines endlichen Satzes entspricht einer Matroid, in der der Basissatz der Matroid aus dem besteht Atome des Gitters, nämlich die Partitionen mit ${\ displayStyle n-2}$ Singleton-Sets und ein Zwei-Elemente-Set. Diese atomaren Partitionen entsprechen eins zu eins mit den Kanten von a Komplette Graph. Das Matroid -Schließung Von einer Reihe von Atompartitionen ist die beste gemeinsame Vergröberung von allen; In graphentheoretischen Begriffen ist es die Aufteilung der Eckpunkte der vollständigen Grafik in die verbundene Komponenten des Untergraphen, der durch den angegebenen Satz von Kanten gebildet wird. Auf diese Weise entspricht das Gitter der Partitionen dem Gitter der Wohnungen der Grafik Matroid der vollständigen Grafik.

Ein weiteres Beispiel zeigt die Verfeinerung von Partitionen aus der Perspektive der Äquivalenzbeziehungen. Wenn D ist der Kartensatz in einem Standard-52-Karten-Deck, die gleichfarbig-as Beziehung zu D - was bezeichnet werden kann ~_C - hat zwei Äquivalenzklassen: die Sets {rote Karten} und {schwarze Karten}. Die 2-teilige Partition entspricht ~_C hat eine Verfeinerung, die die ergibt gleicherkenntnis Beziehung ~_S, was die vier Äquivalenzklassen {Spaten}, {Diamonds}, {Hearts} und {Clubs} hat.

Nichtkreuzungspartitionen

Eine Partition des Satzes N = {1, 2, ...,, n} mit entsprechender Äquivalenzbeziehung ~ ist Nichtkreuzung Wenn es die folgende Eigenschaft hat: wenn vier Elemente a, b, c und d von N haben a < b < c < d erfüllen a ~ c und b ~ d, dann a ~ b ~ c ~ d. Der Name stammt aus der folgenden äquivalenten Definition: Stellen Sie sich die Elemente 1, 2, ... vor n von N gezeichnet wie das n Scheitelpunkte eines regulären n-Gon (im gegen den Uhrzeigersinn). Eine Partition kann dann visualisiert werden, indem jeden Block als Polygon gezeichnet wird (dessen Eckpunkte die Elemente des Blocks sind). Die Partition ist dann nicht kreuzend, wenn sich diese Polygone nicht schneiden.

Das Gitter von Nichtkreuzungspartitionen eines endlichen Satzes hat kürzlich aufgrund seiner Rolle in Bedeutung in Anspruch genommen freie Wahrscheinlichkeit Theorie. Diese bilden eine Untergruppe des Gitters aller Partitionen, aber kein Sublattice, da die Join -Operationen der beiden Gitter nicht einverstanden sind.

Partitionen zählen

Die Gesamtzahl der Partitionen von a n-Element -Set ist das Glockennummer B_n. Die ersten mehrere Glockenzahlen sind B₀ = 1,B₁ = 1, B₂ = 2, B₃ = 5, B₄ = 15, B₅ = 52 und B₆ = 203 (Sequenz A000110 in dem Oeis). Glockenzahlen erfüllen die Rekursion

${\ displayStyle B_ {n+1} = \ sum _ {k = 0}^{n} {n \ wählen K} B_ {k}}$

und haben die Exponentialerzeugungsfunktion

$oder$

Konstruktion des Belldreieck

Die Glockennummern können auch mit dem berechnet werden Belldreieck in dem der erste Wert in jeder Zeile vom Ende der vorherigen Zeile kopiert wird und nachfolgende Werte durch Hinzufügen von zwei Zahlen, der Anzahl links und der Zahl links von der Position berechnet werden. Die Glockenzahlen werden entlang beiden Seiten dieses Dreiecks wiederholt. Die Zahlen innerhalb der Dreieckszahl -Partitionen, bei denen ein bestimmtes Element das größte ist Singleton.

Die Anzahl der Partitionen von a n-Element genau eingestellt in genau k (nicht leere) Teile sind die Stirling Anzahl der zweiten Art S(n, k).

Die Anzahl der Nichtkreuzungspartitionen von a n-Element -Set ist das Katalanische Nummer

${\ displayStyle c_ {n} = {1 \ über N+1} {2n \ wählen n}.}$

Siehe auch

• Genaue Abdeckung
• Blockdesign
• Clusteranalyse
• Schwache Ordnung (bestellte Set Partition)
• Teiläquivalenzbeziehung
• Verfeinerung der Partition
• Liste der Partitionsthemen
• Laminierung (Topologie)
• Reimschemata durch festgelegte Partition
• Partitionalgebra

Anmerkungen

Verweise

• Brualdi, Richard A. (2004). Einführungskombinatorik (4. Aufl.). Pearson Prentice Hall. ISBN 0-13-100119-1.
• Schechter, Eric (1997). Handbuch der Analyse und der Grundlage. Akademische Presse. ISBN 0-12-622760-8.