podzial zbioru n- elementowego

[Aramil]

Iloma sposobami zbiór n- elementowy mozna podzielic na dwa podzbiory. nie uwzgledniajac zbioru pustego.

kompletnie nie mam pomyslu na to zadanie

[max]

Zauważmy, że jeden z wybranych podzbiorów w pełni wyznacza podział (drugi podzbiór jest wyznaczony jako pozostałe elementy zbioru). Aby uniknąć powtórnego zliczania tego samego podziału wybierzmy sobie pewien ustalony element należący do zbioru i zliczajmy tylko te podzbiory naszego zbioru, do których należy ten element. Jest ich tyle ile jest wszystkich podzbiorów właściwych (drugi z podzbiorów nie może być pusty) zbioru (n - 1) -elementowego, czyli:
\(\displaystyle{ {n\brace 2} = 2^{n - 1} - 1}\)

(\(\displaystyle{ {n\brace k}}\) lub też \(\displaystyle{ S(n, k)}\) oznacza , czyli liczbę podziałów zbioru n-elementowego na k pozdbiorów.)

edit literówka

[przemk20]

jesli bedziemy brac n elementow ze zbioru n elementowego to wtedy mozemy go podzielic na 2 podzbiory na \(\displaystyle{ [\frac{n}{2}]}\) sposoby , gdy mamy wybrac n-1 elementow,
to mamy \(\displaystyle{ {n \choose 1}}\) mozliwosci wyboru, i na \(\displaystyle{ [\frac{n-1}{2}]}\) sposobow mozymy je podzielic na dwa podzbioru, czyli mamy \(\displaystyle{ {n \choose 1} [\frac{n-1}{2}]}\) mozliwosci itd ..
Sprubojmy uogolnic gdy wybieramy n-k elementow, k={0,1,..n-2},
to wtedy mozemy podany podzbior wybrac na \(\displaystyle{ {n \choose k}}\) sposobow, i podzielic go na dwa podzbiory na \(\displaystyle{ [\frac{n-k}{2}]}\)
sposobow, czyli mamy \(\displaystyle{ [\frac{n-k}{2}] }\) mozliwosci,
Zsumujac wszystkie mozliwe k, dostaniemy wszystki mozliwosci podzialy zbioru n elementowego na 2 podzbiory, czyli
\(\displaystyle{ K = \sum_{k=0}^{n-2} [\frac{n-k}{2}] }\)

[max]

\(\displaystyle{ n = 2 K = 0}\)

[Aramil]

...\(\displaystyle{ [\frac{n}{2}]}\)...

co rozumiesz przez to oznaczenie ?

[ Dodano: 18 Maj 2007, 21:43 ]

zliczajmy tylko te podzbiory naszego zbioru, do których należy ten element

nie wiem jak je zliczales ;/

[przemk20]

max, pomylilem sie przy granicach sumowania, powinno oczywiscie byc od k=0 do n-2, wtedy K=1,
\(\displaystyle{ [\frac{n}{k}]}\) cecha z liczby, albo inaczej czesc calkowita,

[max]

przemk20 dalej nie jest dobrze,
np \(\displaystyle{ {4\brace 2} = 7}\) (co można zauważyć wypisując te podziały)
a dla \(\displaystyle{ n = 4}\) jest \(\displaystyle{ K = 2 + 4 + 6 = 12}\)

zliczajmy tylko te podzbiory naszego zbioru, do których należy ten element

nie wiem jak je zliczales ;/

Jest ich tyle ile jest wszystkich podzbiorów właściwych (drugi z podzbiorów nie może być pusty) zbioru (n - 1) -elementowego

Właśnie tak.

[Aramil]

eh nie zrozumieliśmy sie chodzilo mi wlasnie o to jak wpadles na to ze jest ich wlasnie tyle, ze wlasnie tak trzeba je zliczac?

[max]

Ok, jeszcze raz.

Pojedynczy podział jest wyznaczony jednoznacznie przez jeden z dwóch podzbiorów, na które dzielimy. Oczywiste jest, że jeśli wybierzemy sobie pewien element zbioru to przy każdym podziale znajdzie on się w jednym z tych dwóch podzbiorów, na które dzielimy - zatem wystarczy policzyć liczbę możliwych podzbiorów zawierających ustalony element, różnych od całego zbioru, bo wtedy 'podzielilibyśmy' cały zbiór n elementowy na ten zbiór i zbiór pusty.

Podzbiory takie tworzymy w następujący sposób:
Jak już sobie wybierzemy jeden element to pozostałych będzie n - 1. Teraz musimy dobrać sobie jakiś podzbiór tego zbioru n - 1 elementowego różny od całego zbioru.

[Aramil]

aha rozumiem, a wzor jakim sposobem wyprowadziles? wariacje bez powtorzen? czy jakos inaczej ?

[max]

Dla każdego \(\displaystyle{ m\in \mathbb{N}}\) liczba wszystkich podzbiorów zbioru m elementowego wynosi:
\(\displaystyle{ {m\choose 0} + {m\choose 1} + \ldots + {m\choose m - 1} + {m\choose m} = (1 + 1)^{m} = 2^{m}}\)
czyli dla zbioru n - 1 elementowego będzie \(\displaystyle{ 2^{n - 1}}\) podzbiorów, odejmujemy jeden i mamy co trzeba.