XIII OM - III - Zadanie 4

Iloma sposobami można zbiór $ n $ przedmiotów podzielić na dwa zbiory?

Rozwiązanie

Odpowiedź na postawione pytanie będzie zależała od tego, czy - do rozważanych zbiorów zaliczymy też zbiór pusty, tj. zbiór nie posiadający żadnego elementu (przedmiotu), czy nie; w pierwszym przypadku poszukiwana liczba jest o $ 1 $ większa niż w drugim. Umówimy się rozważać tylko zbiory niepuste.

Niech $ p $ oznacza liczbę wszystkich możliwych podziałów zbioru $ Z $ posiadającego $ n $ elementów, na dwa zbiory, tj. na dwie części.

Wówczas $ 2p $ oznacza liczbę wszystkich możliwych części, czyli podzbiorów zbioru $ Z $, przy czym bierzemy pod uwagę tylko podzbiory właściwe, tj. różne od samego zbioru $ Z $.

Liczbę $ 2p $ wszystkich podzbiorów zbioru o $ n $ elementach znajdziemy, dodając liczby podzbiorów o $ 1, 2, \ldots, (n - 1) $ elementach.

Podzbiorów o $ k $ elementach jest tyle, ile jest kombinacji z $ n $ elementów po $ k $, tj. $ \binom{n}{k} $. Zatem

\[<br />
2p = \binom{n}{1} + \binom{n}{2} + \ldots + \binom{n}{n-1}.<br />
\]

Według wzoru dwumianowego Newtona

\[<br />
(2) \qquad  (1+1)^n = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \ldots + \binom{n}{n-1} + \binom{n}{n}.<br />
\]

Odejmując równości (1) i (2) i uwzględniając, że $ \binom{n}{0} = \binom{n}{n} = 1 $, otrzymujemy

\[<br />
2^n - 2p = 2<br />
\]

a stąd

\[<br />
p = 2^{n-1} - 1.<br />
\]

Komentarze

Dodaj nową odpowiedź