Na ile sposobów można podzielić zbiór

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
max123321
Użytkownik
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

Na ile sposobów można podzielić zbiór

Post autor: max123321 »

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?
max123321
Użytkownik
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

Post autor: max123321 »

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?
Awatar użytkownika
kerajs
Użytkownik
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

Post autor: kerajs »

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 }\) .
Awatar użytkownika
kitsu-ne
Użytkownik
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

Post autor: kitsu-ne »

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}}\).
Awatar użytkownika
kerajs
Użytkownik
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

Post autor: kerajs »

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).
To to samo co u maxa.
kitsu-ne pisze: 28 sty 2025, o 18:05 Łatwo widać, że wszystkich możliwych podziałów jest więc \(\displaystyle{ 2^{n-1}}\).
A z czego innego to widać, jeśli nie z:

\(\displaystyle{ \sum_{i=0}^{m} {m \choose i} =(1+1)^m=2^m}\) ?
a4karo
Użytkownik
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

Post autor: a4karo »

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.
Awatar użytkownika
kerajs
Użytkownik
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

Post autor: kerajs »

Fakt, nie doczytałem.
ODPOWIEDZ