dzielenie zbioru n-elementowego na 3 części - ile sposobów

[pandyzio]

Takie zadanie:

Na ile sposobów zbiór \(\displaystyle{ n}\)-elementowy można podzielić na 3 części? (Bez założeń, czyli części mogą być puste).

Wydaje mi się, że powinno być \(\displaystyle{ 3 ^{n}}\), a jako, że części są nierozróżnialne, wynik ten trzeba podzielić przez \(\displaystyle{ 3!}\) (3 zbiory można "poprzestawiać na 3! sposobów). Dałoby to wynik \(\displaystyle{ \frac{3 ^{n}}{3!}}\), co jednak jest złe, bo nie daje liczby całkowitej.
Co jest złego w mym myśleniu?

[brzoskwinka1]

Ilość rozbić \(\displaystyle{ S_n}\) zbioru \(\displaystyle{ n}\) elementowego na 3 niepuste podzbiory otrzymasz rozwiązując równanie rekurencyjne:
\(\displaystyle{ S_0 =0 ,S_1 =0, S_2 =0 , S_3 =1 ,}\) \(\displaystyle{ S_{n+1} =3S_n +2^{n-2} -1}\)

Ilość wszystkich rozbić uzyskasz jeżeli uwzględnisz rozbicia na:
- 3 niepuste
- jeden pusty
- dwa puste.