Ile jest permutacji, w których...

[klaudiak]

Mamy zbiór liczb natualnych {1,2,3,4,5,...,n-1,n}. Ile jest permutacja tego zbioru, w których
a) co najmniej jeden element nie stoi na swoim miejscu
b) żaden element nie stoi na swoim miejscu?

[Wicio]

a)
Mozna po prostu policzyć wszystkie permutacje i odjąć tą jedną gdy wszystkie elementy stoja na swoim miejscu ;p

Więc po prostu będzie:

\(\displaystyle{ P=n!-1}\)

[Wasilewski]

b) Zdaje się, że:
\(\displaystyle{ P_{n} = n! \sum_{k=0}^{n} \frac{(-1)^{k}}{k!}}\)
Żeby do tego dojść trzeba najpierw zauważyć, że spełniona jest taka rekurencja:
\(\displaystyle{ P_{1} = 0 \\
P_{2} = 1 \\
P_{n} = (n-1) (P_{n-1} + P_{n-2})}\)
I wystarczy sprawdzić, że podany przez mnie wzór ją spełnia. Z tej zależności można też wywieść, że:
\(\displaystyle{ P_{1} = 0 \\
P_{n} = nP_{n-1} + (-1)^{n}}\)
W tym przypadku chyba łatwiej sprawdzić prawdziwość podanego wzoru.