Liczba Stirlinga drugiego rodzaju

[razelll]

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

[kerajs]

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

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).

[razelll]

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.

[Jan Kraszewski]

Dlaczego \(\displaystyle{ S(n,n) = 1}\)?

A na ile sposobów możesz podzielić \(\displaystyle{ n}\)-elementowy zbiór na \(\displaystyle{ n}\) bloków?

JK

[kerajs]

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 }\)

[razelll]

Ok, wreszcie to zrozumiałem Dziękuję bardzo za pomoc!