Na ile sposobów można podzielić zbiór \(\displaystyle{ \left\{ 1, 2, 3, ..., n\right\} }\) na
niepuste podzbiory tak, aby każdy podzbiór składał się
z kolejnych liczb. Przykładowo jeden z podziałów zbioru
\(\displaystyle{ \left\{ 1, 2, 3, 4, 5, 6\right\} }\) to \(\displaystyle{ \left\{ 1, 2\right\} }\), \(\displaystyle{ \left\{ 3, 4, 5\right\} }\), \(\displaystyle{ \left\{ 6\right\} }\).
Jak to zrobić? Może mi ktoś pomóc?
Na ile sposobów można podzielić zbiór
-
- Użytkownik
- Posty: 3568
- Rejestracja: 26 maja 2016, o 01:25
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 1050 razy
- Pomógł: 6 razy
Re: Na ile sposobów można podzielić zbiór
Mam pewien pomysł. Możemy ustawić te liczby po kolei w szeregu i dzielić je na \(\displaystyle{ k}\) grup. Liczba takich podziałów, to \(\displaystyle{ {n-1 \choose k-1} }\). Zatem suma wszystkich takich podziałów to
\(\displaystyle{ \sum_{k=0}^{n-1} {n-1 \choose k}=2^{n-1} }\).
Dobrze?
\(\displaystyle{ \sum_{k=0}^{n-1} {n-1 \choose k}=2^{n-1} }\).
Dobrze?
- kerajs
- Użytkownik
- Posty: 8652
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 314 razy
- Pomógł: 3380 razy
Re: Na ile sposobów można podzielić zbiór
Raczej
\(\displaystyle{ \sum_{k=1}^{n} {n-1 \choose k-1}=2^{n-1} }\)
Osobną kwestią jest to, czy należy tu uwzględnić \(\displaystyle{ k=1 }\) .
\(\displaystyle{ \sum_{k=1}^{n} {n-1 \choose k-1}=2^{n-1} }\)
Osobną kwestią jest to, czy należy tu uwzględnić \(\displaystyle{ k=1 }\) .
- kitsu-ne
- Użytkownik
- Posty: 17
- Rejestracja: 25 sty 2025, o 23:25
- Płeć: Mężczyzna
- wiek: 35
- Podziękował: 2 razy
- Pomógł: 10 razy
Re: Na ile sposobów można podzielić zbiór
Prostsze rozumowanie nie wymagające sumowania współczynników dwumianowych: za każdą liczbą \(\displaystyle{ 1, 2, \ldots, n-1}\) stawiasz pionową kreskę albo nie (kreski oddzielają od siebie osobne podzbiory). Łatwo widać, że wszystkich możliwych podziałów jest więc \(\displaystyle{ 2^{n-1}}\).
- kerajs
- Użytkownik
- Posty: 8652
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 314 razy
- Pomógł: 3380 razy
Re: Na ile sposobów można podzielić zbiór
To to samo co u maxa.kitsu-ne pisze: 28 sty 2025, o 18:05 Prostsze rozumowanie nie wymagające sumowania współczynników dwumianowych: za każdą liczbą \(\displaystyle{ 1, 2, \ldots, n-1}\) stawiasz pionową kreskę albo nie (kreski oddzielają od siebie osobne podzbiory).
A z czego innego to widać, jeśli nie z:kitsu-ne pisze: 28 sty 2025, o 18:05 Łatwo widać, że wszystkich możliwych podziałów jest więc \(\displaystyle{ 2^{n-1}}\).
\(\displaystyle{ \sum_{i=0}^{m} {m \choose i} =(1+1)^m=2^m}\) ?
-
- Użytkownik
- Posty: 22375
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 40 razy
- Pomógł: 3803 razy
Re: Na ile sposobów można podzielić zbiór
Z tego, że na każdym miejscu może być przerwa lub nie że zatem możliwości jest tyle ile podzbiorów zbioru przerw.
Ostatnio zmieniony 29 sty 2025, o 16:11 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.