Liczby Stirlinga II rodzaju tożsamości

[choko]

Proszę o pomoc w udowodnieniu którejkolwiek z tożsamości: \(\displaystyle{ S(k,n)}\)liczba podziałów zb. k elementowego na n bloków, a\(\displaystyle{ B_k}\)oznacza liczbę wszystkich podziałów zbioru k-elementowego.
a) \(\displaystyle{ S(k,n)=S(k-1,n-1)+nS(k-1,n)}\) dla \(\displaystyle{ 0<n<k}\)
b) \(\displaystyle{ x^{k}= \sum_{n=0}^{k} S(k,n) [x]_n}\) dla \(\displaystyle{ k \ge 0}\)
c) \(\displaystyle{ S(k,n)= \sum_{i=n-1}^{k-1} {k-1\choose i} S(i,n-1)}\) dla \(\displaystyle{ n \ge 2}\)
d) \(\displaystyle{ B_k+1= \sum_{j=0}^{k} {k\choose j} B_j}\)

\(\displaystyle{ [x]_n}\) oznacza \(\displaystyle{ {n\choose k}*k!}\)

[adek05]

a) Rozważ podziały z pewnym wyróżnionym elementem.
b) Co to jest \(\displaystyle{ [x]_n}\)?
d) Coś nie gra w tej sumie, dziwne te granice sumowania.

[choko]

Nie wiem w I myślę tak pr. strona to jakoś tak że element siedzi w bloku lub nie, ale jakoś nie mogę wymyślić.

[adek05]

Dobrze kombinujesz Element siedzie w blokach z wcześniejszego podziału lub nie, a jak nie to znaczy, że tworzy nowy.

[choko]

I Element siedzi w bloku więc pozostałe k-1 el. dzielimy na n-1 bloków.
II A jak nie to może siedzieć w każdym z n bloków w które wkładamy k-1-elementów. I mnożymy przez n bo tyle wyborów bloku, dobrze kombinuje? Ale zaraz czy drugi przypadek nie wyklucza wszystkich możliwości?

[adek05]

Nie. Pomyśl, że masz zrobione podziały \(\displaystyle{ n-1}\) elementów i teraz zastanów się jak z nich wyprodukować podziały \(\displaystyle{ n}\) elementów.
\(\displaystyle{ S(n,k)}\) oznacza, że masz \(\displaystyle{ n}\) elementów i wrzucasz je do \(\displaystyle{ k}\) kubków.

[choko]

Niestety nie pomaga mi to w wymyśleniu odpowiedniego schematu:(

[adek05]

Ach, masz tam odwrotnie, dzielisz \(\displaystyle{ k}\) na \(\displaystyle{ n}\). No ale idea jest taka, że jak masz podział i nowy element to dla każdego podziału:
a) wrzuczasz go do któregoś z kubków podziału
b) tworzysz nowy kubek i tam go wrzucasz.