podzbiory zbioru n elementowego

Gogeta · Post autor: **Gogeta** » 16 paź 2012, o 22:21

ile podzbiorow zbioru n elementowego zawiera nieparzysta liczbe elementow? Prosilbym o odpowiedz na to pytanie. Z gory dziekuje i pozdrawiam!

octahedron · Post autor: **octahedron** » 16 paź 2012, o 23:03

\(\displaystyle{ \left\lfloor\frac{n+1}{2}\right\rfloor}\)

Vardamir · Post autor: **Vardamir** » 16 paź 2012, o 23:13

octahedron pisze:\(\displaystyle{ \left\lfloor\frac{n+1}{2}\right\rfloor}\)

Skąd taki tok myślenia, skoro wszystkich takich podzbiorów jest \(\displaystyle{ 2 ^{n}}\) ?

octahedron · Post autor: **octahedron** » 16 paź 2012, o 23:34

No nie, tak nie będzie. Ale \(\displaystyle{ 2^n}\) też nie, np. dla \(\displaystyle{ n=1}\) to nie będą dwa podzbiory.

Vardamir · Post autor: **Vardamir** » 16 paź 2012, o 23:38

Podałem liczbę wszystkich podzbiorów i jest ich \(\displaystyle{ 2 ^{n}}\).

Dla \(\displaystyle{ n=1}\) czyli zbioru jednoelementowego istnieją dwa podzbiory, jeden złożony z tego właśnie elementu, a drugi złożony ze zbioru pustego.

-- 16 paź 2012, o 23:42 --

Zaryzykowałbym też stwierdzenie, że zbiorów o parzystej i nieparzystej liczbie elementów jest tyle samo. Więc rozwiązaniem jest \(\displaystyle{ 2 ^{n-1}}\) .

pyzol · Post autor: **pyzol** » 16 paź 2012, o 23:44

Też tak na początku pomyślałem, ale teraz nie jestem co do tego przekonany. Na pewno jest tyle dla parzystych:
\(\displaystyle{ \binom{2n}{0}+\binom{2n}{2}+\ldots+\binom{2n}{2n}}\)

Vardamir · Post autor: **Vardamir** » 16 paź 2012, o 23:48

Kod: Zaznacz cały

http://smurf.mimuw.edu.pl/node/814

Tutaj znalazłem kombinatoryczne uzasadnienie tego faktu.

pyzol · Post autor: **pyzol** » 16 paź 2012, o 23:56

O, to jednak "proste myślenie (tyle samo co nieparzystych)" było jak najbardziej prawidłowe.