MATEMANIJA

Primer 22.

Koliko podskupova ima skup [inlmath]\{a_1,a_2,\ldots,a_n\}[/inlmath]?

Rešenje:

Svaki od elemenata skupa može da pripada ili ne pripada podskupu datog skupa. Dakle, za svaki od njih postoje dve mogućnosti, pa ukupno ima [inlmath]2^n[/inlmath] podskupova.

---

Može usložnjenje ovog jednostavnog rešenja? Previše je jednostavno da bih ga ukapirao.

---

Matematika za prijemni na tehničkim i prirodno matematičkim fakultetima (Jovanov, Lazović, Đorić)

Može... Zamisli [inlmath]n[/inlmath] lampica (npr. LED-dioda) od kojih svaka može ili da svetli ili da ne svetli, logično. Neka sve te LED-diode čine skup [inlmath]A[/inlmath]. I onda uzmimo da, ako svetli, onda pripada trenutno posmatranom podskupu, a ako ne svetli, onda ne pripada trenutno posmatranom podskupu. Ako ne svetli nijedna – onda je posmatrani podskup prazan skup; ako svetle sve, onda je posmatrani podskup jednak skupu [inlmath]A[/inlmath] (i to je dozvoljeno, jer se svaki skup može posmatrati i kao podskup samog sebe); ako svete LED diode označene sa [inlmath]a_3,\:a_7,\:a_{12}[/inlmath], tada se posmatrani podskup sastoji od elemenata [inlmath]a_3,\:a_7,\:a_{12}[/inlmath]; itd...

Naravno, broj mogućih načina na koji neke LED-diode mogu da svetle ili ne svetle iznosi [inlmath]2^n[/inlmath], gde je [inlmath]n[/inlmath] njihov broj – varijacije od [inlmath]2[/inlmath] elementa (svetli / ne svetli) [inlmath]n[/inlmath]-te klase (jer imamo [inlmath]n[/inlmath] LED-dioda) s ponavljanjem. To je onda i broj svih podskupova skupa od [inlmath]n[/inlmath] elemenata.

Uzmi, na primer, skup od samo jednog elementa. On ima [inlmath]2^1[/inlmath] podskupova, tj. ima [inlmath]2[/inlmath] podskupa. Jedan podskup je prazan skup, a drugi podskup ima taj jedan element, tj. taj drugi podskup je jednak samom skupu.

Uzmimo sad skup od [inlmath]2[/inlmath] elementa, [inlmath]a_1[/inlmath] i [inlmath]a_2[/inlmath]. On ima [inlmath]2^2[/inlmath] podskupova, tj. ima [inlmath]4[/inlmath] podskupa. Jedan podskup je prazan skup, drugi podskup sadrži element [inlmath]a_1[/inlmath], treći podskup sadrži element [inlmath]a_2[/inlmath], a četvrti podskup sadrži oba elementa, i [inlmath]a_1[/inlmath] i [inlmath]a_2[/inlmath], tj. jednak je samom skupu.

Na isti način, možeš zamisliti i skupove od [inlmath]3[/inlmath] i više elemenata, pokušati da izbrojiš njihove podskupove i uočiti pravilnost.

Inače, valja napomenuti i to da se skup svih podskupova nekog skupa zove partitivni skup tog skupa. O tome možeš pogledati u Ubavic-evom tutorijalu o skupovima, pod tačkom 6. Tu je upravo i navedeno da je [inlmath]\mathrm{card}\bigl(P(A)\bigr)=2^{\text{card}(A)}[/inlmath], gde je [inlmath]\text{card}\bigl(P(A)\bigr)[/inlmath] kardinalnost, tj. broj elemenata partitivnog skupa [inlmath]P(A)[/inlmath], a [inlmath]\text{card}(A)[/inlmath] je kardinalnost, tj. broj elemenata skupa [inlmath]A[/inlmath].

Drugi način dokazivanja, koristeći kombinacije bez ponavljanja i svojstvo [inlmath]\sum\limits_{k=0}^n{n\choose k}=2^n[/inlmath], može se videti u ovoj temi.