Wyznacz liczbę podziałów zbioru \(\{1, 2, ..., n\}\) na dwa niepuste rozłączne podzbiory.
Wskazówka: Ten podzbiór, który nie zawiera \(n\) jest niepustym podzbiorem zbioru \(\{1,2...,n-1\}\).
Udało mi się dotrzeć do znajomego, który ma rozwiązanie tego zadania, jednakże ja i on nie rozumiemy, skąd ono się wzięło.
dla \(n = 3 \)
\(\{1, 2\} \{3\}\)
\(\{1, 3\} \{2\}\)
\(\{2, 3\} \{1\}\)
dla \(n=4\)
\(\{2, 4\} \{1, 3\}\)
\(\{1, 2\} \{3, 4\}\)
\(\{1, 2, 4\} \{3\}\)
Jeśli mamy podzbiór \(\{1,2,3\}\) z podziału \(\{1, 2, 3, 4\} 2*3+1 \leftarrow \{1, 2, 3\} \{4\}\)
Próbuję to rozgryźć, już od dłuższego czasu, ale trafiam na ślepe punkty...
Wyznacz liczbę podziałów
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
damian28102000
- Czasem tu bywam
- Posty: 128
- Rejestracja: 11 lis 2020, 19:11
- Podziękowania: 144 razy
- Płeć:
- Kontakt:
-
kerajs
- Fachowiec
- Posty: 2963
- Rejestracja: 14 lis 2016, 14:38
- Podziękowania: 33 razy
- Otrzymane podziękowania: 1303 razy
- Płeć:
Re: Wyznacz liczbę podziałów
Podzbiór jednoelementowy wybieram na \({ n\choose 1}\) sposobów, a reszta elementów stanowi drugi podzbiór ( n-1 elementowy) .
Podzbiór dwuelementowy wybieram na \({ n\choose 12}\) sposobów, a reszta elementów stanowi drugi podzbiór ( n-2 elementowy) .
Podzbiór trójelementowy wybieram na \({ n\choose 3}\) sposobów, a reszta elementów stanowi drugi podzbiór ( n-3 elementowy) .
...
Podzbiór (n-1) elementowy wybieram na \({ n\choose n-1}\) sposobów, a reszta elementów stanowi drugi podzbiór ( 1 elementowy) .
Jak widać wybory się dublują, więc szukana ilość to połowa z nich.
\( \frac{1}{2} \sum_{i=1}^{n-1} { n\choose i}= \frac{1}{2} ( - { n\choose 0} - { n\choose n} + \sum_{i=0}^{n} { n\choose i} )= \frac{1}{2} (-1-1+2^n)=2^{n-1}-1 \)
Podzbiór dwuelementowy wybieram na \({ n\choose 12}\) sposobów, a reszta elementów stanowi drugi podzbiór ( n-2 elementowy) .
Podzbiór trójelementowy wybieram na \({ n\choose 3}\) sposobów, a reszta elementów stanowi drugi podzbiór ( n-3 elementowy) .
...
Podzbiór (n-1) elementowy wybieram na \({ n\choose n-1}\) sposobów, a reszta elementów stanowi drugi podzbiór ( 1 elementowy) .
Jak widać wybory się dublują, więc szukana ilość to połowa z nich.
\( \frac{1}{2} \sum_{i=1}^{n-1} { n\choose i}= \frac{1}{2} ( - { n\choose 0} - { n\choose n} + \sum_{i=0}^{n} { n\choose i} )= \frac{1}{2} (-1-1+2^n)=2^{n-1}-1 \)