Question

Czym jest niepusty podzbiór?

I na przykład na ile sposobów zbiór {1,2,3,4,5,6,7,8,9} można podzielić na 3 niepuste podzbiory?

Na ile sposobów ogólnie zbiór można podzielić na k niepustych podzbiorów?

Proszę o proste wytłumaczenie i dodanie własnego przykładu.

Answer 1

Niepusty podzbior - jest to zbior zawierajacy co najmniej jeden element.
Kazdy element zbioru mozna umiescic na 3 sposoby.
Wszystkich takich ustawien jest 3^9, od tego nalezy odjac pzypadki, gdy puste beda dwa podzbiory 2^9-2 i jeden podzbior - 3 mozliwosci.
Kolejnosc podzbiorow nie jest wazna, dlatego dzielimy to wszystko przez 3!

Ostatecznie:
(3^9-(2^9-2)-3)/3!=3025
Ogolnie:
(k^n-[(k-1)^n-(k-1)]- [k-2[^n-(k-2)-...-k)/k!
Na studiach poznajemy liczby Stirlinga, skad odczytujemy natychmiast ilosc takich podzialow.
Inny przyklad:
5 elementow dzielimy na 2 niepuste podzbiory:
(2^5-2)/2!=(1/2(32-2)=15