Dowód kombinatoryczny - ilość podzbiorów 2^n.

[_Mithrandir]

Mam udowodnić kombinatorycznie, że ilość podzbiorów zbioru n-elementowego wyraża się wzorem \(\displaystyle{ 2^n}\). O ile dowód indukcyjny i dowód na podstawie tw. o dwumianie Newtona są proste, o tyle z tym mam problem. Jak zacząć?

[JakimPL]

Sumujemy liczbę możliwości:

- ile możemy wybrać różnych zbiorów pustych: \(\displaystyle{ {n \choose 0}}\)
- ile możemy wybrać różnych, jednoelementowych podzbiorów: \(\displaystyle{ {n \choose 1}}\)
- ile możemy wybrać różnych, dwuelementowych podzbiorów: \(\displaystyle{ {n \choose 2}}\)

I tak dalej, aż po \(\displaystyle{ n}\). Uzyskaliśmy sumę:

\(\displaystyle{ {n \choose 0}+{n \choose 1}+ {n \choose 2}+\ldots+{n \choose n-1}+{n \choose n}= \sum_{k=0}^n {n \choose k}}\)

Mam nadzieję, że z tego miejsca już łatwo do \(\displaystyle{ 2^n}\).

[_Mithrandir]

Ten już miałem (bo chodzi o wykorzystanie twierdzenia o dwumianie Newtona, prawda?), ale dzięki, już mam, co chciałem

[nivwusquorum]

Koledze chyba chodziło o to, że każdy unikalny podzbiór tworzymy decydując dla każdego z n elementów czy będzie się w nim zawierał, czy też nie. Mamy więc 2 możliwe stany dla każdego z n elementów. Stąd liczba podzbiorów to \(\displaystyle{ 2^n}\).