Podaj zwartą postać symboli
-
- Użytkownik
- Posty: 71
- Rejestracja: 16 lis 2019, o 21:50
- Płeć: Kobieta
- wiek: 19
- Podziękował: 36 razy
- Pomógł: 1 raz
Podaj zwartą postać symboli
Witam,
mam problem z zadaniem z matematyki dyskretnej:
Podaj zwartą postać symboli \(\displaystyle{ S(n,3)}\) i \(\displaystyle{ S(n, n-2)}\) dla \(\displaystyle{ n \ge 3 }\).
Oczywiście chodzi o liczby Stirlinga drugiego rodzaju.
Niestety nikt nie wytłumaczył mi w jaki sposób można to zrobić, a w internecie nie mogę znaleźć żadnych przykładów.
mam problem z zadaniem z matematyki dyskretnej:
Podaj zwartą postać symboli \(\displaystyle{ S(n,3)}\) i \(\displaystyle{ S(n, n-2)}\) dla \(\displaystyle{ n \ge 3 }\).
Oczywiście chodzi o liczby Stirlinga drugiego rodzaju.
Niestety nikt nie wytłumaczył mi w jaki sposób można to zrobić, a w internecie nie mogę znaleźć żadnych przykładów.
Ostatnio zmieniony 16 lis 2019, o 22:44 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
Powód: Używaj LaTeXa do wszystkich wyrażeń matematycznych.
-
- Użytkownik
- Posty: 71
- Rejestracja: 16 lis 2019, o 21:50
- Płeć: Kobieta
- wiek: 19
- Podziękował: 36 razy
- Pomógł: 1 raz
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Podaj zwartą postać symboli
To nie tak hop siup zasada włączeń i wyłączeń, indukcja itd... , są książki na ten temat ...
Ostatnio zmieniony 19 lis 2019, o 23:26 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- 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: Podaj zwartą postać symboli
To wiem, ale czy mogę po prostu za \(\displaystyle{ k }\) wstawić \(\displaystyle{ n-2 }\) i to już koniec zadania?
- Gosda
- Użytkownik
- Posty: 340
- Rejestracja: 29 cze 2019, o 19:46
- Płeć: Mężczyzna
- Lokalizacja: Oulu
- Podziękował: 42 razy
- Pomógł: 60 razy
Re: Podaj zwartą postać symboli
Nie, bo to nie będzie zwarta postać. Musisz pozbyć się znaku sumy. Nie za ładny wynik wyjdzie:
\(\displaystyle{ S(n, 3) = \frac {3^{n-1}+1} 2 - 2^{n-1}}\)
\(\displaystyle{ S(n, n-2) = \frac{1}{24} (n-2)(n-1) \cdot n \cdot (3n - 5)}\)
\(\displaystyle{ S(n, 3) = \frac {3^{n-1}+1} 2 - 2^{n-1}}\)
\(\displaystyle{ S(n, n-2) = \frac{1}{24} (n-2)(n-1) \cdot n \cdot (3n - 5)}\)
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Podaj zwartą postać symboli
Pierwszy wynik jest bardzo ładny, a drugi lepiej prezentuje się w formie
\(\displaystyle{ {n\choose 3}+3{n\choose 4}}\), w której to łatwo widać schemat dowodu przez bajeczkę kombinatoryczną.
\(\displaystyle{ {n\choose 3}+3{n\choose 4}}\), w której to łatwo widać schemat dowodu przez bajeczkę kombinatoryczną.
-
- 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: Podaj zwartą postać symboli
Czy w przypadku \(\displaystyle{ S(n,3) }\) też mam napisać taką "bajkę" ?
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Podaj zwartą postać symboli
A można, jak najbardziej, jeszcze jak.
Na przykład taką:
dzielimy zbiór \(\displaystyle{ n}\)-elementowy na trzy niepuste, parami rozłączne podzbiory. Popatrzmy na te zbiory jak na pudełka, do których wrzucamy poszczególne elementy.
Korzystamy z zasady włączeń i wyłączeń: dla trzech zbiorów, by to zliczyć. Wszystkich przyporządkowań elementów tym pudełkom jest \(\displaystyle{ 3^{n}}\), odejmujemy od nich te, w których do pewnych dwóch pudełek trafią wszystkie elementy (gdyż podzbiory, na które dzielimy zbiór, mają być niepuste), a takich jest \(\displaystyle{ {3\choose 2}2^{n}}\), następnie zauważmy, że odejmując te przypadki, w których co najmniej jedno pudełko jest puste, policzyliśmy \(\displaystyle{ 6}\) razy układ, w którym do jednego pudełka trafiają wszystkie elementy zbioru, a powinniśmy policzyć tylko \(\displaystyle{ 3}\) razy (wszystkie w pierwszym pudełku, w drugim pudełku, w trzecim pudełku). Dlaczego tak się stało? Dla ustalenia uwagi, na przykład sytuację, w której wszystkie elementy trafiły do pierwszego pudełka zliczyliśmy raz jako sytuację, w której łącznie do pierwszego i drugiego pudełka trafiły wszystkie elementy, a drugi raz jako sytuację, w której do pierwszego i trzeciego pudełka trafiły wszystkie elementy.
Zatem musimy jeszcze dodać \(\displaystyle{ 3}\).
Na koniec zauważmy, że numeracja pudełek nie ma znaczenia, więc otrzymany wynik, czyli \(\displaystyle{ 3^{n}-{3\choose 2}2^{n}+3}\) dzielimy przez \(\displaystyle{ 3!=6}\), dostając \(\displaystyle{ \frac{3^{n-1}+1}{2}-2^{n-1}}\).
Na przykład taką:
dzielimy zbiór \(\displaystyle{ n}\)-elementowy na trzy niepuste, parami rozłączne podzbiory. Popatrzmy na te zbiory jak na pudełka, do których wrzucamy poszczególne elementy.
Korzystamy z zasady włączeń i wyłączeń:
Kod: Zaznacz cały
https://pl.wikipedia.org/wiki/Zasada_w%C5%82%C4%85cze%C5%84_i_wy%C5%82%C4%85cze%C5%84
Zatem musimy jeszcze dodać \(\displaystyle{ 3}\).
Na koniec zauważmy, że numeracja pudełek nie ma znaczenia, więc otrzymany wynik, czyli \(\displaystyle{ 3^{n}-{3\choose 2}2^{n}+3}\) dzielimy przez \(\displaystyle{ 3!=6}\), dostając \(\displaystyle{ \frac{3^{n-1}+1}{2}-2^{n-1}}\).