Particioni i bashkësisë

Nga Wikipedia, enciklopedia e lirë
Shko te: navigacion, kërko

Particion apo zbërthim i bashkësisë X është bashkësia P e të gjitha nënbashkësive jo të zbrazta të X të tilla që

  1. Unioni i elementeve nga P është i barabartë me X.
  2. Prerja ç'do dy elementeve të ndryshme nga P është bashkësi e zbrazët.

Me simbole matematikore këto dy kushte mund të shënohen me

  1. \bigcup P = X
  2. A \cap B =\emptyset \text{ nese } A \in P, B\in P, A \neq B

Elementet e P i quajmë blloqe ose pjesë të particionit.[1]

Shembuj[redakto | redakto tekstin burimor]

  • Bashkësia {x} ka vetëm një particion { {x} }.
  • Nëse X është një bashkësi jo e zbrazët atëherë, P = {X} është një particion i X.
  • Bashkësia { 1, 2, 3 } ka këto 5 particione të ndryshme.
    • { {1}, {2}, {3} }, shkurt shënojmë 1/2/3.
    • { {1, 2}, {3} }, shkurt shënojmë 12/3.
    • { {1, 3}, {2} }, shkurt shënojmë 13/2.
    • { {1}, {2, 3} }, shkurt shënojmë 1/23.
    • { {1, 2, 3} }, shkurt shënojmë 123.

Partitionet dhe relacioni i ekuivalencës[redakto | redakto tekstin burimor]

Imtësimi i particioneve[redakto | redakto tekstin burimor]

Çdo particion α i bashkësisë X është imtësim i particionit ρX—dhe themi se α është më imtë se ρ dhe ρ është më i trashë se α—nëse ç'do element i α është nënbashkësi e ndonjë elementi të ρ. Joformalisht kjo do të thotë se α është fragmentim ose coptim i ρ. Në këtë rast përdorim shënimin αρ.

Relacioni është më i imët se në bashkësinë e particioneve të X është një renditje e pjesshme ose rrjetë e plotë. Si shembull janë dhënë particionet e bashkësisë X = {1, 2, 3, 4}, kjo rrjetë e particioneve ka 15 elemente dhe ajo formon të ashtuquajturin diagram Hasse në figurën më poshtë

PartitionLattice.svg

Numri i particioneve[redakto | redakto tekstin burimor]

Numri i particioneve të një bashkësie me n-elemente është numër i Bellit Bn. Disa nga numrat eparë të Bellit janë B0 = 1, B1 = 1, B2 = 2, B3 = 5, B4 = 15, B5 = 52, B6 = 203 etj. Numrat e Bellit e plotësojnë rekurencën B_{n+1}=\sum_{k=0}^n {n\choose k}B_k

Funksioni gjenerues i numrave të Belleit është

\sum_{n=0}^\infty\frac{B_n}{n!}z^n=e^{e^z-1}.

Numri i particioneve të një bashkësie me n-elemente në k pjesë është numër i Stirlingut i llojit të dytë S(n, k).

Shënime[redakto | redakto tekstin burimor]

  1. ^ Brualdi, pp. 44-45

Referencat[redakto | redakto tekstin burimor]

  • Richard A. Brualdi: Introductory Combinatorics, 4th edition, Pearson Prentice Hall 2004, ISBN 0131001191
  • Eric Schechter: Handbook of Analysis and Its Foundations. Academic Press 1997, ISBN 0126227608