Fajny wzór

[arek1357]

Znaleźć wzór na ilość wszystkich cykli \(\displaystyle{ S_{n}}\)

np:

Cykle \(\displaystyle{ S_{2}}\):

\(\displaystyle{ \left\{ (1)(2)(12)\right\}}\) - jest ich trzy

Cykle \(\displaystyle{ S_{3}}\):

\(\displaystyle{ \left\{ (1)(2)(3)(12)(13)(23)(123)(132)\right\}}\) - jest ich osiem

itd...

Chodzi mi o znalezienie wzoru rekurencyjnego a nawet jawnego, może ktoś zna lepszy i krótszy sposób niż mój...

[Peter Zof]

Dziel i zwyciężaj. Ile jest cykli \(\displaystyle{ k \leq n}\) elementowych w \(\displaystyle{ \mathcal{S}_n}\)? Oznaczmy tę liczbę przez \(\displaystyle{ \mathcal{C}^{n}_{m}}\). Odpowiedzią więc jest liczba \(\displaystyle{ \mathcal{C}^{n}=\Sigma_{k=1}^{n} \mathcal{C}^{n}_{k}}\). Prawdziwa zabawa to oczywiście jawny opis tych liczb, a nie zabawa w znaczki.

\(\displaystyle{ \mathcal{C}^{n}_{m}=\dots}\)

Ukryta treść:    

Twój cykl długości \(\displaystyle{ m}\) permutuje \(\displaystyle{ m}\) obiektów, reszta obiektów których jest \(\displaystyle{ n-m}\) nie jest permutowana. Tak więc pierwszą rzeczą, która nas interesuje jest policzenie na ile sposobów możemy wybrać te \(\displaystyle{ m}\) obiektów. Z tym sobie na pewno poradzisz. Dalej, mając te \(\displaystyle{ m}\) obiektów, \(\displaystyle{ x_1,\dots,x_m}\), budujemy z nich cykl. Każdy cykl to wyrażenie następującej postaci \(\displaystyle{ \left(x_{\sigma(1)} \dots x_{\sigma(m)}\right)}\), dla pewnej permutacji \(\displaystyle{ \sigma \in \mathcal{S}_m}\). Tak więc masz co najwyżej \(\displaystyle{ m!}\) możliwości. Niestety niektóre permutacje z \(\displaystyle{ \mathcal{S}_m}\) prowadzą do tych samych cykli. Przykład: \(\displaystyle{ (a b c)=(c a b)}\)=. Teraz wystarczy sobie uświadomić, że jest dokładnie \(\displaystyle{ \frac{m!}{m}}\) permutacji z \(\displaystyle{ \mathcal{S}_m}\) prowadzących do różnych cykli.

[arek1357]

Wzór jest taki:

\(\displaystyle{ a_{n}=1+ \sum_{i=2}^{n} {n \choose i}(i-1)!}\)

Teraz kwestia go sprytnie zwinąć...