Cześć,
Zapisałem się niedawno na studia z informatyki i miałem właśnie pierwsze zajęcia z matematyki dyskretnej.
Ostatni raz kombinatorykę miałem w szkole średniej i ciężko mi poradzić sobie z jednym zagadnieniem, a konkretnie z obliczaniem możliwości podziału zbioru \(\displaystyle{ n}\)-elementowego na \(\displaystyle{ k}\) bloków.
Mam do rozwiązania:
\(\displaystyle{ S(6,4)}\)
Wiem jedynie, że mógłbym to rozpisać \(\displaystyle{ S(6,4) = S(5,3) + 4S(5,4)}\) i na tym moja wiedza się kończy
Z tego co już zdążyłem się dowiedzieć, to chyba trzeba wykorzystać tu rekurencje, ale tu zaczynają się schody, bo nie mam pojęcia jak to liczyć, tj. jak rozłożyć każdy składnik równania (\(\displaystyle{ S(5,3)}\)) i dostać wynik?
Proszę o wskazówki.
Pozdrawiam
Liczba Stirlinga drugiego rodzaju
-
- Użytkownik
- Posty: 157
- Rejestracja: 7 paź 2009, o 11:16
- Płeć: Mężczyzna
- Podziękował: 53 razy
- Pomógł: 1 raz
Liczba Stirlinga drugiego rodzaju
Ostatnio zmieniony 21 paź 2019, o 11:56 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.
- kerajs
- Użytkownik
- Posty: 8589
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3352 razy
Re: Liczba Stirlinga drugiego rodzaju
Działasz tak samo dalej:
\(\displaystyle{ S(6,4) = S(5,3) + 4S(5,4)=S(4,2)+3S(4,3)+4\left( S(4,3)+4S(4,4)\right)=... }\)
Ponieważ \(\displaystyle{ S(n,n)=1}\) to wyrażenie się upraszcza do:
\(\displaystyle{ ...=S(4,2)+7S(4,3)+16}\)
Kilka dalszych rozkładów doprowadzi do liczbowego wyniku (65).
-
- Użytkownik
- Posty: 157
- Rejestracja: 7 paź 2009, o 11:16
- Płeć: Mężczyzna
- Podziękował: 53 razy
- Pomógł: 1 raz
Re: Liczba Stirlinga drugiego rodzaju
A mógłbyś mi rozpisać skąd co się wzięło? Dlaczego \(\displaystyle{ S(n,n) = 1}\)? Gdzie jest takie wyrażenie, które możemy tak uprościć?
Sorry za takie trywialne pytania, ale jest to dla mnie kompletnie nowe i jeszcze nie zatrybiłem dobrze.
Sorry za takie trywialne pytania, ale jest to dla mnie kompletnie nowe i jeszcze nie zatrybiłem dobrze.
-
- Administrator
- Posty: 34338
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5204 razy
Re: Liczba Stirlinga drugiego rodzaju
A na ile sposobów możesz podzielić \(\displaystyle{ n}\)-elementowy zbiór na \(\displaystyle{ n}\) bloków?
JK
- kerajs
- Użytkownik
- Posty: 8589
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3352 razy
Re: Liczba Stirlinga drugiego rodzaju
Liczmy kolorowo:
\(\displaystyle{ S(6,4) = \red{ S(5,3)} +4\blue{ S(5,4)}=\left( \red{S(4,2)+3S(4,3)}\right) +4\left( \blue{S(4,3)+4S(4,4)}\right)=}\)
\(\displaystyle{ =\red{S(4,2)}+\left[ \red{3S(4,3)}+4\blue{ S(4,3)} \right] +16\blue{S(4,4)}=...}\)
Ponieważ \(\displaystyle{ S(n,n)=1}\) ( czyli \(\displaystyle{ S(4,4)=S(3,3)=...=S(0,0)=1}\) ) to wyrażenie się upraszcza do:
\(\displaystyle{ ...=S(4,2)+7S(4,3)+16}\)
Ponadto:
\(\displaystyle{ S(n,0)=0}\) dla \(\displaystyle{ n \in \NN \setminus \left\{ 0\right\} }\) co przyda się przy \(\displaystyle{ S(2,0)=S(1,0)=0 }\)
\(\displaystyle{ S(6,4) = \red{ S(5,3)} +4\blue{ S(5,4)}=\left( \red{S(4,2)+3S(4,3)}\right) +4\left( \blue{S(4,3)+4S(4,4)}\right)=}\)
\(\displaystyle{ =\red{S(4,2)}+\left[ \red{3S(4,3)}+4\blue{ S(4,3)} \right] +16\blue{S(4,4)}=...}\)
Ponieważ \(\displaystyle{ S(n,n)=1}\) ( czyli \(\displaystyle{ S(4,4)=S(3,3)=...=S(0,0)=1}\) ) to wyrażenie się upraszcza do:
\(\displaystyle{ ...=S(4,2)+7S(4,3)+16}\)
Ponadto:
\(\displaystyle{ S(n,0)=0}\) dla \(\displaystyle{ n \in \NN \setminus \left\{ 0\right\} }\) co przyda się przy \(\displaystyle{ S(2,0)=S(1,0)=0 }\)