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.
Liczby Stirlinga drugiego rodzaju dowód
- Premislav
- 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
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.
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.
-
- 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
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
- Premislav
- 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
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.
-
- 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
Dowód z rozpisaną sumą można znaleźć w monografii
Witolda Lipskiego i Wiktora Marka Analiza Kombinatoryczna str. 50-51. PWN Warszawa 1986.
Witolda Lipskiego i Wiktora Marka Analiza Kombinatoryczna str. 50-51. PWN Warszawa 1986.
-
- 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
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?