Liczba podziałów

[alicja_91]

Pokazać, że \(S(n,n-1) = \frac{n(n-1)}{2}\)

Nie wiem, jak za to się zabrać.

[Crazy Driver]

Co rozumiesz przez \(S(n,n-1)\)?

[alicja_91]

Co rozumiesz przez \(S(n,n-1)\)?

Jest to liczba podziałów zbioru n-elementowego na n-1 bloków. No i co w związku z tym?

[Crazy Driver]

To w związku z tym, że nie znając tego oznaczenia nie byłem w stanie Ci pomóc. A co to są boki zbioru \(n\)-elementowego?

[alicja_91]

To w związku z tym, że nie znając tego oznaczenia nie byłem w stanie Ci pomóc. A co to są boki zbioru \(n\)-elementowego?

Przepraszam. Nie umiem odpowiedzieć na to pytanie.

Myślę, że to zadanie ma coś wspólnego z liczbą Stirlinga. \(S(n,k)\) - liczba podziałów zbioru n elementowego na k bloków. Tylko jak to pokazać?

[Crazy Driver]

Aha, bloki, nie boki. Musiałem źle zrozumieć.
Nie dam głowy, że to jest dobrze (choć raczej jest), ale ja bym do tego podszedł tak: każdy podział zbioru \(n\)-elementowego na \((n-1)\) części dzieli go na \((n-2)\) singletonów i dokładnie jeden zbiór dwuelementowy. W takim razie każdy podział jest jednoznacznie wyznaczony przez dwuelementowy podzbiór naszego zbioru.
Takich podziałów jest więc tyle, ile dwuelementowych podzbiorów zbioru \(n\)-elementowego, czyli
\({n \choose 2}=\frac{n(n-1)}{2}\)

[alicja_91]

Myślę, że jest dobrze Już lepiej rozumiem, tylko nie bardzo rozumiem, skąd to wiadomo:

każdy podział zbioru \(n\)-elementowego na \((n-1)\) części dzieli go na \((n-2)\) singletonów i dokładnie jeden zbiór dwuelementowy.

Mógłbyś jakoś to rozwinąć?