Dwa niepuste rozłączne podzbiory
Dwa niepuste rozłączne podzbiory
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.
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.
Ostatnio zmieniony 4 mar 2013, o 18:29 przez Rewop, łącznie zmieniany 3 razy.
-
- Użytkownik
- Posty: 2203
- Rejestracja: 15 lis 2012, o 00:13
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 43 razy
- Pomógł: 526 razy
Dwa niepuste rozłączne podzbiory
Podzbiorów, czy podziałów?Rewop pisze:Zbiór n-elementowy dzielimy na dwa niepuste rozłączne podzbiory. Ile jest takich podzbiorów
Pokaż najpierw dlaczego wyszedł taki wzór to się okaże skąd się wzięła dwójka w mianowniku.Rewop pisze: Wyszedł mi wzór \(\displaystyle{ \frac{2^n-2}{2}}\)
-
- Użytkownik
- Posty: 8
- Rejestracja: 3 lut 2013, o 17:28
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 2 razy
Dwa niepuste rozłączne podzbiory
Dzielimy przez 2 dlatego, że podzbiory nie są rozróżnialne. Np. dla n=3: 1,2,3 to to samo, co 23,13,12
-
- Użytkownik
- Posty: 5974
- Rejestracja: 28 lut 2010, o 19:45
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 15 razy
- Pomógł: 1251 razy
Dwa niepuste rozłączne podzbiory
Kompletnie nie rozumiem tego co napisałeś.pehapx pisze:Dzielimy przez 2 dlatego, że podzbiory nie są rozróżnialne. Np. dla n=3: 1,2,3 to to samo, co 23,13,12
Dwa niepuste rozłączne podzbiory
Ten wynik jest "strzałem" który pasuje do rozwiązania tego problemu. Doszedłem do niego przypadkiem.rafalpw pisze:Pokaż najpierw dlaczego wyszedł taki wzór to się okaże skąd się wzięła dwójka w mianowniku.
Też tego nie rozumiem.pehapx pisze:Dzielimy przez 2 dlatego, że podzbiory nie są rozróżnialne. Np. dla n=3: 1,2,3 to to samo, co 23,13,12
-
- Użytkownik
- Posty: 5974
- Rejestracja: 28 lut 2010, o 19:45
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 15 razy
- Pomógł: 1251 razy
Dwa niepuste rozłączne podzbiory
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}\).
-
- Użytkownik
- Posty: 8
- Rejestracja: 3 lut 2013, o 17:28
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 2 razy
Dwa niepuste rozłączne podzbiory
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.bartek118 pisze:Kompletnie nie rozumiem tego co napisałeś.pehapx pisze:Dzielimy przez 2 dlatego, że podzbiory nie są rozróżnialne. Np. dla n=3: 1,2,3 to to samo, co 23,13,12