Ilość podzbiorów zbioru wyłączając zbiory równe
: 3 gru 2006, o 09:36
Witam,
Dostałem takie dość ciekawe zadanko:
Dowieść, że funkcja przyporządkowująca liczbie n liczbę podzbiorów zbioru n-elementowego (z zastrzeżeniem, że zbiory równe liczymy tylko jeden raz) jest różnowartościowa.
np. Liczba podzbiorów zbioru {a,a,b} to:
- zbiór pusty - 1
- 1 elementowe - {a} {b} - 2
- 2 elementowe - {a,a} {a,b} -2
- 3 elementowe - {a,a,b} - 1
Razem 1+2+2+1=6
Na razie doszedłem do wniosku, że jeśli wszystkie elementy zbioru są parami różne to wartość funkcji jest równa 2^n, czyli jest różnowartościowa (Zaskakujące odkrycie ). A tak serio to próbowałem wyznaczać kombinatorycznie ilość podzbiorów zbioru, w którym niektóre elementy się powtarzają, ale jakoś nie idzie mi to. Pomóżcie
Z góry dzięki i pozdrawiam
Dostałem takie dość ciekawe zadanko:
Dowieść, że funkcja przyporządkowująca liczbie n liczbę podzbiorów zbioru n-elementowego (z zastrzeżeniem, że zbiory równe liczymy tylko jeden raz) jest różnowartościowa.
np. Liczba podzbiorów zbioru {a,a,b} to:
- zbiór pusty - 1
- 1 elementowe - {a} {b} - 2
- 2 elementowe - {a,a} {a,b} -2
- 3 elementowe - {a,a,b} - 1
Razem 1+2+2+1=6
Na razie doszedłem do wniosku, że jeśli wszystkie elementy zbioru są parami różne to wartość funkcji jest równa 2^n, czyli jest różnowartościowa (Zaskakujące odkrycie ). A tak serio to próbowałem wyznaczać kombinatorycznie ilość podzbiorów zbioru, w którym niektóre elementy się powtarzają, ale jakoś nie idzie mi to. Pomóżcie
Z góry dzięki i pozdrawiam