Matematyka.pl

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?

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?

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 }\) .

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}}\).

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}\) ?

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.

Fakt, nie doczytałem.