MATEMANIJA

Ako skup [inlmath]A[/inlmath] ima [inlmath]n[/inlmath] elemenata njegov partitivni skup ima [inlmath]2^{n}[/inlmath] elemenata. Kako biste to dokazali?
formula: [dispmath]\left(a+b\right)^n=\sum_{k=0}^n{n\choose k}a^{n-k}b^k[/dispmath]
[dispmath]a=b=1\quad\Rightarrow\quad\left(1+1\right)^n=2^n=\sum_{k=0}^n{n\choose k}1^{n-k}1^k\quad\Rightarrow\quad\sum_{k=0}^n{n\choose k}=2^n[/dispmath]

Jeste, radi se preko te formule. Definiciju partitivnog skupa možeš videti ovde (na samom kraju).

– Koliko ima podskupova skupa [inlmath]A[/inlmath] koji imaju [inlmath]0[/inlmath] elemenata? – To je broj kombinacija od [inlmath]n[/inlmath] elemenata [inlmath]0.[/inlmath] klase, bez ponavljanja.
– Koliko ima podskupova skupa [inlmath]A[/inlmath] koji imaju [inlmath]1[/inlmath] element? – To je broj kombinacija od [inlmath]n[/inlmath] elemenata [inlmath]1.[/inlmath] klase, bez ponavljanja.
– Koliko ima podskupova skupa [inlmath]A[/inlmath] koji imaju [inlmath]2[/inlmath] elementa? – To je broj kombinacija od [inlmath]n[/inlmath] elemenata [inlmath]2.[/inlmath] klase, bez ponavljanja.
[inlmath]\vdots[/inlmath]
– Koliko ima podskupova skupa [inlmath]A[/inlmath] koji imaju [inlmath]k[/inlmath] elemenata? – To je broj kombinacija od [inlmath]n[/inlmath] elemenata [inlmath]k.[/inlmath] klase, bez ponavljanja.
[inlmath]\vdots[/inlmath]
– Koliko ima podskupova skupa [inlmath]A[/inlmath] koji imaju [inlmath]n[/inlmath] elemenata? – To je broj kombinacija od [inlmath]n[/inlmath] elemenata [inlmath]n.[/inlmath] klase, bez ponavljanja.

Pošto partitivni skup skupa [inlmath]A[/inlmath] ima onoliko elemenata koliko skup [inlmath]A[/inlmath] ima podskupova, to znači da treba samo da sabereš brojeve svih ovih kombinacija, a to radiš upravo pomoću te formule koju si napisao.

Drugi način dokazivanja, preko varijacija s ponavljanjem, može se videti u ovoj temi.