Podział zestawu - Partition of a set

Zestaw znaczków podzielony na wiązki: Żaden znaczek nie znajduje się w dwóch wiązkach, żadna wiązka nie jest pusta, a każdy znaczek znajduje się w wiązce.

Do 52 rozbicie zbioru z 5 elementów. Kolorowy region wskazuje podzbiór X, tworzący członka otaczającej partycji. Niekolorowe kropki oznaczają podzbiory jednoelementowe. Pierwsza pokazana partycja zawiera pięć jednoelementowych podzbiorów; ostatnia partycja zawiera jeden podzbiór składający się z pięciu elementów.

Tradycyjne japońskie symbole dla 54 rozdziałów Tale of Genji opierają się na 52 sposobach podziału pięciu elementów (dwa czerwone symbole reprezentują ten sam podział, a zielony symbol jest dodawany w celu osiągnięcia 54).

W matematyce , o rozbicie zbioru jest grupowanie z jej elementów do niepustych podzbiorów , w taki sposób, że każdy element jest zawarty w dokładnie jednej podgrupie.

Każda relacja równoważności w zestawie definiuje podział tego zestawu, a każdy podział definiuje relację równoważności. Zbiór wyposażony w relację równoważności lub podział jest czasami nazywany setoidem , zazwyczaj w teorii typów i teorii dowodu .

Definicja i notacja

Podział zbioru X jest zbiorem niepustych podzbiorów X takich, że każdy element x w X jest dokładnie w jednym z tych podzbiorów (tzn. X jest rozłączną sumą podzbiorów).

Równoważnie, rodzina zbiorów P jest podziałem X wtedy i tylko wtedy, gdy spełnione są wszystkie poniższe warunki:

• Rodzina P nie zawiera pustego zestawu (czyli ).${\ Displaystyle \ pusty zestaw \ notin P}$
• Związek zbiorów w P jest równy X (to ). Mówi się, że zestawy w P wyczerpują lub zakrywają X . Zobacz także zbiorczo wyczerpujące wydarzenia i okładkę (topologia) .${\ Displaystyle \ textstyle \ bigcup _ {A \ w P} A = X}$
• Przecięcia dowolnych dwóch różnych grup w P jest pusta (to ). Mówi się, że elementy P są parami rozłączne .${\ Displaystyle (\ forall A, B \ in P) \; A \ neq B \ implikuje A \ cap B = \ pusty zestaw}$

Zbiory w P nazywane są blokami , częściami lub komórkami partycji . Jeśli potem reprezentują komórkę zawierającą się By . To znaczy, jest zapis do komórki w P , który zawiera . ${\displaystyle a\w X}$${\displaystyle [a]}$${\displaystyle [a]}$

Każdy podział, P , można utożsamić z relacją równoważności na X , a mianowicie relacją taką, że dla każdego mamy wtedy i tylko wtedy, gdy (równoważnie wtedy i tylko wtedy, gdy ). Notacja przywodzi na myśl, że relację równoważności można zbudować z partycji. I odwrotnie, każda relacja równoważności może być utożsamiana z podziałem. Dlatego czasami mówi się nieformalnie, że „stosunek równoważności jest tym samym, co podział”. Jeżeli P jest partycją utożsamianą z daną relacją równoważności , to niektórzy autorzy piszą . Ten zapis sugeruje ideę, że partycja to zbiór X podzielony na komórki. Notacja przywołuje również ideę, że z relacji równoważności można zbudować przegrodę. ${\ Displaystyle \ SIM _ {P}}$${\displaystyle a,b\w X}$${\displaystyle a\sim_{P}b}$${\displaystyle a\w [b]}$${\displaystyle b\w [a]}$${\ Displaystyle \ SIM _ {P}}$${\displaystyle \sim}$${\displaystyle P=X/\sim}$

Ranga od P jest | X | − | P | , jeśli X jest skończone .

Przykłady

• Pusty zestaw ma dokładnie jedną partycję, a mianowicie . (Uwaga: to jest partycja, a nie członek partycji.)${\displaystyle \pusty zestaw}$${\displaystyle \pusty zestaw}$
• Dla każdego niepustego zbioru X , P = { X } jest podziałem X , zwanym podziałem trywialnym .
  • W szczególności każdy pojedynczy zbiór { x } ma dokładnie jedną partycję, mianowicie { { x } }.
• Dla dowolnego niepustego podzbioru właściwego A zbioru U , zbiór A wraz z jego uzupełnieniem tworzą podział U , mianowicie { A , U ∖ A }.
• Zbiór {1, 2, 3} ma te pięć partycji (jedna partycja na element):
  • { {1}, {2}, {3} }, czasami pisane 1 | 2 | 3.
  • { {1, 2}, {3}} lub 1 2 | 3.
  • { {{1, 3}, {2}} lub 1 3 | 2.
  • { {1}, {2, 3} } lub 1 | 2 3.
  • { {1, 2, 3} } lub 123 (w kontekstach, w których nie będzie pomyłek z liczbą).
• Poniższe nie są partycjami {1, 2, 3}:
  • { {}, {1, 3}, {2} } nie jest partycją (dowolnego zestawu), ponieważ jednym z jej elementów jest zestaw pusty .
  • { {1, 2}, {2, 3} } nie jest partycją (dowolnego zestawu), ponieważ element 2 jest zawarty w więcej niż jednym bloku.
  • { {1}, {2} } nie jest partycją {1, 2, 3}, ponieważ żaden z jej bloków nie zawiera 3; jednak jest to partycja {1, 2}.

Podziały i relacje równoważności

Dla każdej relacji równoważności na zbiorze X , zbiór jego klas równoważności jest podziałem X . I odwrotnie, z dowolnego podziału P z X , możemy zdefiniować relację równoważności na X , ustawiając x ~ y dokładnie wtedy, gdy x i y znajdują się w tej samej części w P . Zatem pojęcia relacji równoważności i podziału są zasadniczo równoważne.

Aksjomatu wyboru gwarancji dla każdej rozbicie zbioru X istnienie od podzbioru X zawierającym dokładnie jeden element z każdej strony przegrody. Oznacza to, że mając relację równoważności na zbiorze, można wybrać kanoniczny element reprezentatywny z każdej klasy równoważności.

Udoskonalenie przegród

Partycje zestawu 4 uporządkowane według udoskonalenia

Podział α zbioru X jest udoskonaleniem podziału ρ zbioru X —i mówimy, że α jest drobniejsze niż ρ i że ρ jest grubsze niż α —jeśli każdy element α jest podzbiorem jakiegoś elementu ρ . Nieformalnie oznacza to, że α jest dalszą fragmentacją ρ . W takim przypadku jest napisane, że α ≤ ρ .

Ta drobniejsza relacja na zbiorze partycji X jest porządkiem częściowym (więc odpowiednia jest notacja "≤"). Każdy zbiór elementów ma najmniejsze ograniczenie górne i największe ograniczenie dolne , tak że tworzy sieć , a dokładniej (dla podziałów zbioru skończonego) jest siecią geometryczną . Kraty podziału zbioru 4, element posiada elementy 15 i przedstawiono na schemacie Hasse po lewej stronie.

Opierając się na kryptomorfizmie między sieciami geometrycznymi a matroidami , ta siatka podziałów zbioru skończonego odpowiada matroidowi , w którym zbiór podstawowy matroidu składa się z atomów sieci, a mianowicie przegród ze zbiorami singletonowymi i jednego dwuelementowego ustawić. Te podziały atomowe odpowiadają krawędziom pełnego grafu jeden do jednego . Matroid zamknięcie zestawu partycji atomowych jest najlepszym wspólny brutalizacji z nich wszystkich; w kategoriach teorii grafów jest to podział wierzchołków całego grafu na połączone składowe podgrafu utworzonego przez dany zbiór krawędzi. W ten sposób siatka przegród odpowiada siatce mieszkań matroidy graficznej pełnego grafu. ${\displaystyle n-2}$

Inny przykład ilustruje doprecyzowanie podziałów z perspektywy relacji równoważności. Jeśli D jest zestawem kart w standardowej 52-kartowej talii, relacja tego samego koloru na D – którą można oznaczyć ~ _C – ma dwie klasy równoważności: zestawy {czerwone karty} i {czarne karty}. Dwuczęściowy podział odpowiadający ~ _C ma udoskonalenie, które daje relację tego samego koloru jako ~ _S , która ma cztery klasy równoważności {pik}, {diamenty}, {kiery} i {trefle}.

Przegrody nieprzekraczające

Podział zbioru N = {1, 2, ..., n } z odpowiednią relacją równoważności ~ jest niekrzyżujący, jeśli ma następującą własność: Jeżeli cztery elementy a , b , c i d z N mające a < b < c < d spełniają a ~ c i b ~ d , a następnie a ~ b ~ c ~ d . Nazwa pochodzi z następującej równoważnej definicji: Wyobraź sobie elementy 1, 2, ..., n z N narysowane jako n wierzchołków regularnego n- kąta (w kolejności przeciwnej do ruchu wskazówek zegara). Partycję można następnie zwizualizować, rysując każdy blok jako wielokąt (którego wierzchołki są elementami bloku). Partycja nie przecina się wtedy i tylko wtedy, gdy te wielokąty się nie przecinają.

Krata nieprzecinających się partycji zbioru skończonego zyskała ostatnio na znaczeniu ze względu na jej rolę w teorii prawdopodobieństwa swobodnego . Tworzą one podzbiór sieci wszystkich partycji, ale nie podsieć, ponieważ operacje łączenia dwóch sieci nie są zgodne.

Liczenie partycji

Całkowita liczba partycji zestawu n- elementowego to liczba Bell B _n . Pierwsze kilka numerów Bell to B ₀ = 1, B ₁ = 1, B ₂ = 2, B ₃ = 5, B ₄ = 15, B ₅ = 52 i B ₆ = 203 (sekwencja A000110 w OEIS ). Numery dzwonków spełniają rekurencję

${\ Displaystyle B_ {n + 1} = \ suma _ {k = 0} ^ {n} {n \ wybierz k} B_ {k}}$

i mieć funkcję generowania wykładniczego

${\ Displaystyle \ suma _ {n = 0} ^ {\ infty} {\ Frac {B_ {n}} {n!}} z ^ {n} = e ^ {e ^ {z} -1}.}$

Budowa trójkąta Bell

Liczby Bell można również obliczyć za pomocą trójkąta Bell, w którym pierwsza wartość w każdym wierszu jest kopiowana z końca poprzedniego wiersza, a kolejne wartości są obliczane przez dodanie dwóch liczb, liczby po lewej stronie i liczby do powyższego na lewo od pozycji. Liczby Bell są powtórzone po obu stronach tego trójkąta. Liczby w trójkącie liczą partycje, w których dany element jest największym singletonem .

Liczba podziałów n -elementu ustawionego na dokładnie k niepustych części jest liczbą Stirlinga drugiego rodzaju S ( n , k ).

Liczba nieprzecinających się partycji zbioru n- elementowego jest liczbą katalońską C _n , podaną przez

${\ Displaystyle C_ {n} = {1 \ ponad n + 1} {2n \ wybierz n}.}$

Zobacz też

• Dokładna okładka
• Projekt bloku
• Analiza skupień
• Słabe zamówienie (zamówiony zestaw partycji)
• Częściowa relacja równoważności
• Udoskonalenie partycji
• Lista tematów partycji
• Laminowanie (topologia)
• Schematy rymów według ustawionej partycji

Uwagi

Bibliografia

• Brualdi, Richard A. (2004). Wprowadzające kombinatoryka (wyd. 4). Pearson Prentice Hall. Numer ISBN 0-13-100119-1.
• Schechter, Eric (1997). Podręcznik analizy i jego podstawy . Prasa akademicka. Numer ISBN 0-12-622760-8.