Particije skupova
D Za skupove A i B ka~zemo da su disjunktni ako vrijedi AnB=0. Dakle, ne postoji objekt koji je u oba (!(E_x)(x@A&x@B)), odnosno, bilo koji element jednog nije u onom drugom ((A_x@A)!(x@B)).
12Z S je univerzalan skup, A i B njegovi podskupovi. Doka~zite: A i B su disjunktni akko je A C= Bc.
Rj (=>) Neka su A i B disjunktni. Trebamo dokazati skupovnu inkluziju. U tu svrhu, neka je x proizvoljni element od A. Pretpostavka x@B odmah vodi na x@AnB, ~sto je kontradikcija s disjunktno~s~tu. Dakle, vrijedi !(x@B), odnosno x@Bc. Svaki element od A je time element od Bc, pa je inkluzija dokazana.
(<=) Neka je A podskup od Bc. Trebamo dokazati disjunktnost. U tu svrhu, pretpostavimo postojanje nekog x@AnB i poku~sajmo je dovesti do kontradikcije. Imamo x@A i x@B. Iz x@A po inkluziji slijedi x@Bc, ~sto je u kontradikciji s x@B. To zna~ci da takav x ne mo~ze postojati, pa je tvrdnja dokazana.
D Particija nekog skupa S je neki skup podskupova od S (dakle, podskup od P(S)), {Si;i@I} (smatramo Si i Sj razli~citima za i != j), koji ima sljede~ta svojstva:
  1. Nijedan od tih skupova nije prazan: !(E_i@I)(Si != 0)
  2. Unija svih tih skupova je cijeli S: Ui@ISi=S, odnosno (A_x@S)(E_i@I)(x@Si)
  3. Svi ti skupovi su me~dusobno disjunktni: (A_i@I)(A_j@I; != i)(SinSj=0)
13Z Odredite sve particije skupa {1,2,3}.
Rj {{1,2,3}}, {{1,2},{3}}, {{1,3},{2}}, {{2,3},{1}} i {{1},{2},{3}}.
14Z Koliko ima dvo~clanih particij~a skupa {1..5}?
Rj "Dvo~clana particija" zna~ci da je {1..5} podijeljen na 2 skupa. Pogledajmo koliko koji od njih ima elemenata. Po svojstvu (1), ne smiju biti prazni, a po svojstvima (2) i (3) zbroj tih brojeva (njihovih cardova) mora biti jednak card{1..5}=5. Budu~ti da je particija skup, redoslijed tih dvaju skupova nam nije bitan. Zaklju~cujemo da postoje samo mogu~tnosti 1+4 i 2+3.
  1. slu~caj: {{?},{?,?,?,?}}. Lako se vidi da je dovoljno odabrati prvi (jedno~clani) skup ~ drugi ~te tada biti skupovna razlika od {1..5}. To o~cito mo~zemo u~ciniti na 5 na~cina. Dakle, 1+4-particij~a od {1..5} ima 5 .
  2. slu~caj: {{?,?},{?,?,?}}. Analogno, dovoljno nam je odabrati prvi (dvo~clani) skup ~ elementi drugoga time su jednozna~cno odre~deni. Dva elementa od pet mo~zemo odabrati na (binomni koeficijent) (5 // 2)=10 na~cina. Dakle, 2+3-particij~a od {1..5} ima 10 .
Sveukupno ih dakle ima 5+10=15 .
Dz Koliko ima tro~clanih particij~a skupa {1..4}? (Hint: sve su tipa 1+1+2 . Od 6 )