Liczby Stirlinga drugiego rodzaju dowód

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
lola456
Użytkownik
Użytkownik
Posty: 71
Rejestracja: 16 lis 2019, o 21:50
Płeć: Kobieta
wiek: 19
Podziękował: 36 razy
Pomógł: 1 raz

Liczby Stirlinga drugiego rodzaju dowód

Post autor: lola456 »

Wykaż, że:
\(\displaystyle{ S(n,k) = \sum_{j=k-1}^{n-1} {n-1 \choose j} \cdot S(j,k-1)}\) dla \(\displaystyle{ n \ge k \ge 2 }\)

Rozumiem że \(\displaystyle{ S(j,k-1) }\) to podział zbioru \(\displaystyle{ j }\) na bloki które mają po \(\displaystyle{ k-1 }\) elementów. Natomiast nie wiem jak to ma się do \(\displaystyle{ n }\). Czy trzeba skorzystać tutaj ze zwartej postaci \(\displaystyle{ S(j,k-1)}\) ?
Proszę o jakąś wskazówkę do tego zadania.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Liczby Stirlinga drugiego rodzaju dowód

Post autor: Premislav »

Chcemy podzielić zbiór \(\displaystyle{ n}\)-elementowy na \(\displaystyle{ k}\) niepustych, parami rozłącznych podzbiorów. Oczywiście z jednej strony możemy to zrobić na \(\displaystyle{ S(n,k)}\) sposobów, co wynika z definicji liczb Stirlinga drugiego rodzaju. Z drugiej strony możemy na to spojrzeć tak:
wyróżnijmy pewien element zbioru \(\displaystyle{ n}\)-elementowego i popatrzmy na zbiór elementów, które nie trafią do jednego podzbioru z tym wyróżnionym elementem. Liczebność tego zbioru może wahać się od \(\displaystyle{ k-1}\) (ponieważ musi być \(\displaystyle{ k-1}\) niepustych podzbiorów, do których nie należy nasz wyróżniony element, a więc co najmniej \(\displaystyle{ k-1}\) elementów, które nie trafiły do tego samego podzbioru) do \(\displaystyle{ n-1}\) (to jasne, bo nasz wyróżniony element będzie należał do tego podzbioru, do którego będzie należał, jak tautologicznie by to nie brzmiało). Ustalamy, ile będzie elementów, które nie trafią do tego samego podzbioru, co nasz wyróżniony element: będzie ich \(\displaystyle{ j, \ k-1\le j\le n-1}\), na \(\displaystyle{ {n-1\choose j}}\) wybieramy spośród \(\displaystyle{ n-1}\) niewyróżnionych elementów \(\displaystyle{ j}\) tych, które trafią do innych podzbiorów, a następnie na \(\displaystyle{ S(j, k-1)}\) sposobów dzielimy ten podzbiór \(\displaystyle{ j}\) elementów na \(\displaystyle{ k-1}\) niepustych, parami rozłącznych podzbiorów. Voila.
lola456
Użytkownik
Użytkownik
Posty: 71
Rejestracja: 16 lis 2019, o 21:50
Płeć: Kobieta
wiek: 19
Podziękował: 36 razy
Pomógł: 1 raz

Re: Liczby Stirlinga drugiego rodzaju dowód

Post autor: lola456 »

I czy taki zapis "słowny" wystarczy aby to udowodnić? Bo szczerze powiedziawszy to myślałam, że trzeba tę sumę jakoś rozpisać... Jakoś nie czuję tych liczb Stirlinga :(
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Liczby Stirlinga drugiego rodzaju dowód

Post autor: Premislav »

Tak, wystarczy. Nie każdy dowód musi być ścianą znaczków. To jest w ogóle bardzo szkodliwa rzecz, zniechęcanie uczniów do pisania pełnymi zdaniami, bo jak matematyka, to muszą być wzorki. Można pewnie jakoś przekształcić tę sumę, na przykład korzystając ze znanego równania rekurencyjnego \(\displaystyle{ S(n, k)=kS(n,k-1)+S(n-1, k-1)}\), ale na tę chwilę nie mam żadnego dobrego pomysłu, jak to dokładnie zrobić, a to, co napisałem, korzystało tylko z definicji liczb Stirlinga drugiego rodzaju i szkolnej kombinatoryki.
lola456
Użytkownik
Użytkownik
Posty: 71
Rejestracja: 16 lis 2019, o 21:50
Płeć: Kobieta
wiek: 19
Podziękował: 36 razy
Pomógł: 1 raz

Re: Liczby Stirlinga drugiego rodzaju dowód

Post autor: lola456 »

Rozumiem. Dziękuję bardzo za pomoc.
janusz47
Użytkownik
Użytkownik
Posty: 7911
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Re: Liczby Stirlinga drugiego rodzaju dowód

Post autor: janusz47 »

Dowód z rozpisaną sumą można znaleźć w monografii

Witolda Lipskiego i Wiktora Marka Analiza Kombinatoryczna str. 50-51. PWN Warszawa 1986.
lola456
Użytkownik
Użytkownik
Posty: 71
Rejestracja: 16 lis 2019, o 21:50
Płeć: Kobieta
wiek: 19
Podziękował: 36 razy
Pomógł: 1 raz

Re: Liczby Stirlinga drugiego rodzaju dowód

Post autor: lola456 »

janusz47 pisze: 17 lis 2019, o 15:48 Dowód z rozpisaną sumą można znaleźć w monografii

Witolda Lipskiego i Wiktora Marka Analiza Kombinatoryczna str. 50-51. PWN Warszawa 1986.
O dziękuję bardzo za polecenie książki, bo widzę, że sporo pojęć stamtąd mi się przyda. Czy jest może jeszcze jakiś w miarę przyjazny zbiór zadań z rozwiązaniami z matematyki dyskretnej?
ODPOWIEDZ