iterpretacja kombinatoryczna - nieporzadki

[kriegor]

nieporzadki czyli \(\displaystyle{ n}\)- permutacje bez punktow stalych mozna wyrazic za pomoca rekurencji:
\(\displaystyle{ \begin{cases} d_0=1 \\ d_1=0 \\ d_2=1 \\ d_{n+1}=n(d_n+d_{n-1}) \end{cases}}\)

ma ktos pomysl na interpretacje kombinatoryczna??-- 16 mar 2012, o 20:42 --czy da sie rozwiazac ta rekurencje bez uzycia funkcji tworzacych??

[szw1710]

Ale ponieważ \(\displaystyle{ d_0=d_2,}\) taka funkcja nie jest różnowartościowa, więc nie może być permutacją. Sama rekurencja jest poprawnie określona, gorzej z tym określeniem nieporządku.

[kriegor]

\(\displaystyle{ d_n}\) to ilosc \(\displaystyle{ n}\)-nieporzadkow przepraszam ze nie sprecyzowalem

[Qń]

Wskazówka: licząc \(\displaystyle{ d_{n+1}}\) najpierw rozpatrz na co przechodzi \(\displaystyle{ n+1}\), nazwijmy to \(\displaystyle{ k}\). Następnie rozważ dwie opcje: \(\displaystyle{ k}\) przechodzi albo nie przechodzi na \(\displaystyle{ n+1}\).

Q.