Dwa niepuste rozłączne podzbiory

[Rewop]

Zbiór n-elementowy dzielimy na dwa niepuste rozłączne podzbiory. Ile jest takich podziałów dla \(\displaystyle{ n \in \left\{4,5,6,7 \right\}}\) albo ogólnie dla \(\displaystyle{ n\in \mathbb{N_{+}}}\).
Wyszedł mi wzór \(\displaystyle{ \frac{2^n-2}{2}}\). Dochodzę do momentu \(\displaystyle{ 2^n-2={n \choose 1}\cdot{n-1 \choose n-1}+{n \choose 2}\cdot{n-2 \choose n-2}+\ldots+{n \choose n-2}\cdot{2 \choose 2}+{n \choose n-1}\cdot{1 \choose 1}}\) i nie wiem dlaczego to dzieli się przez 2.

[rafalpw]

Zbiór n-elementowy dzielimy na dwa niepuste rozłączne podzbiory. Ile jest takich podzbiorów

Podzbiorów, czy podziałów?

Wyszedł mi wzór \(\displaystyle{ \frac{2^n-2}{2}}\)

Pokaż najpierw dlaczego wyszedł taki wzór to się okaże skąd się wzięła dwójka w mianowniku.

[pehapx]

Dzielimy przez 2 dlatego, że podzbiory nie są rozróżnialne. Np. dla n=3: 1,2,3 to to samo, co 23,13,12

[bartek118]

Dzielimy przez 2 dlatego, że podzbiory nie są rozróżnialne. Np. dla n=3: 1,2,3 to to samo, co 23,13,12

Kompletnie nie rozumiem tego co napisałeś.

[Rewop]

Pokaż najpierw dlaczego wyszedł taki wzór to się okaże skąd się wzięła dwójka w mianowniku.

Ten wynik jest "strzałem" który pasuje do rozwiązania tego problemu. Doszedłem do niego przypadkiem.

Dzielimy przez 2 dlatego, że podzbiory nie są rozróżnialne. Np. dla n=3: 1,2,3 to to samo, co 23,13,12

Też tego nie rozumiem.

[bartek118]

Dobra. Dzieli się przez \(\displaystyle{ 2}\), ponieważ policzyłeś podwójnie wszystkie podziały. Np. W pierwszym składniku tej sumy liczysz ile jest rozbić na dwa zbiory: jednoelementowy i \(\displaystyle{ (n-1)}\)-elementowy, a ostatni składnik: na \(\displaystyle{ (n-1)}\)-elementowy i jednoelementowy. Więc liczysz każde rozbicie dwukrotnie - czyli trzeba podzielić przez \(\displaystyle{ 2}\).

[pehapx]

Dzielimy przez 2 dlatego, że podzbiory nie są rozróżnialne. Np. dla n=3: 1,2,3 to to samo, co 23,13,12

Kompletnie nie rozumiem tego co napisałeś.

Zadanie polega na podziale zbioru na dwa rozłączne podzbiory niepuste. Nasz algorytm będzie więc polegał na wybraniu pierwszego z nich spośród wszystkich podzbiorów o licznie elementów od 1 do n-1, a drugi utworzy się niejako automatycznie z pozostałych elementów zbioru wyjściowego. Jednakże w takiej sytuacji zliczając najpierw liczbę podzbiorów k-elementowych, a potem n-k elementowych wykonujemy tą samą czynność dwa razy (np. podzieliliśmy najpierw podzbiór 3-elementowy na podzbiory {1} oraz {2,3} a potem na podzbiory {2,3} oraz {1}) i stąd dzielenie przez 2. Nie potrafię jaśniej.

[Rewop]

Dzięki