przestawianie książek

Glamourbjb · Post autor: **Glamourbjb** » 29 paź 2014, o 18:14

Na półce stoi \(\displaystyle{ n}\) książek w porządku alfabetycznym według nazwisk. Na ile sposobów można poprzestawiać książki tak, aby żadna nie stała na swoim poprzednim miejscu?

Proszę o jakieś wskazówki, bo nie wiem nawet, jak się za to zadanie zabrać.

Kacperdev · Post autor: **Kacperdev** » 29 paź 2014, o 18:18

Masz \(\displaystyle{ n}\) miejsc na ksiązki. Bierzesz pierwszą książke i masz \(\displaystyle{ n-1}\) możliwości jej rożłożenia (wypada ta mozliwosc gdzie ksiazka stala przed chwila)... jak myslisz, co dalej?

Glamourbjb · Post autor: **Glamourbjb** » 29 paź 2014, o 18:26

Załóżmy, że jest tak, jak piszesz, czyli wynik to teoretycznie \(\displaystyle{ (n-1)(n-2)(n-3)...}\) A jeśli poukładam książki tak, że dla ostatniej zostanie tylko to miejsce, na którym ona stała?

Kacperdev · Post autor: **Kacperdev** » 29 paź 2014, o 18:29

To niemożliwe. Każda poprzednia książka zajmie inne miejscie niż poprzednio stąd któraś z tych książek zajmie miejscie tej ostatniej gdzie stała ostatnio

Glamourbjb · Post autor: **Glamourbjb** » 29 paź 2014, o 18:31

Nie zawsze. Weź na przykład 5 książek i zamień miejscami 1 z 2 oraz 4 z 5. Trzecia stoi na swoim miejscu.

norwimaj · Post autor: **norwimaj** » 29 paź 2014, o 19:03

Kacperdev · Post autor: **Kacperdev** » 29 paź 2014, o 19:06

nie doceniłem problemu

Glamourbjb · Post autor: **Glamourbjb** » 29 paź 2014, o 20:03

Dziękuję za gotowca wpadłam już na to wcześniej i jestem w trakcie rozwiązywania, ale miło, że potwierdza się moje rozumowanie i że nie idę w las

Gouranga · Post autor: **Gouranga** » 4 lis 2014, o 22:06

Można tu zastosować metodę włączania i wyłączania:
Wszystkich ustawień książek jest \(\displaystyle{ n!}\)
Ustawień, gdzie co najmniej jedna ksiązka jest na swoim miejscu a reszta nie jest dokładnie \(\displaystyle{ {n \choose 1}(n-1)!}\) (wybieramy która ksiązka ma stać na swoim miejscu i permutujemy resztę)
Ustawień, gdzie co najmniej dwie książki swoją na swoim miejscu jest \(\displaystyle{ {n \choose 2}(n-2)!}\) bo wybieramy 2 książki z n na ich miejsca a resztę permutujemy itd.
I teraz od wszystkich ustawień musimy odjąć te, gdzie co najmniej jedna jest na swoim miejscu, potem musimy dodać wszystkie, gdzie 2 są na swoich miejscach (bo te przekroje odjęliśmy dwa razy odejmując pojedyncze), następnie odejmujemy te, gdzie trzy są na swoich miejsach itd., otrzymamy:
\(\displaystyle{ \sum_{i=0}^{n} (-1)^i {n \choose i} (n-1)!}\)