przestawianie książek
-
- Użytkownik
- Posty: 14
- Rejestracja: 20 maja 2009, o 20:21
- Płeć: Kobieta
- Podziękował: 1 raz
przestawianie książek
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ć.
Proszę o jakieś wskazówki, bo nie wiem nawet, jak się za to zadanie zabrać.
- Kacperdev
- Użytkownik
- Posty: 3260
- Rejestracja: 23 mar 2010, o 19:19
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 17 razy
- Pomógł: 686 razy
przestawianie książek
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?
-
- Użytkownik
- Posty: 14
- Rejestracja: 20 maja 2009, o 20:21
- Płeć: Kobieta
- Podziękował: 1 raz
przestawianie książek
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
- Użytkownik
- Posty: 3260
- Rejestracja: 23 mar 2010, o 19:19
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 17 razy
- Pomógł: 686 razy
przestawianie książek
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
-
- Użytkownik
- Posty: 14
- Rejestracja: 20 maja 2009, o 20:21
- Płeć: Kobieta
- Podziękował: 1 raz
przestawianie książek
Nie zawsze. Weź na przykład 5 książek i zamień miejscami 1 z 2 oraz 4 z 5. Trzecia stoi na swoim miejscu.
-
- Użytkownik
- Posty: 14
- Rejestracja: 20 maja 2009, o 20:21
- Płeć: Kobieta
- Podziękował: 1 raz
przestawianie książek
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
-
- Użytkownik
- Posty: 1596
- Rejestracja: 16 maja 2013, o 17:56
- Płeć: Mężczyzna
- Lokalizacja: Trójmiasto
- Podziękował: 11 razy
- Pomógł: 247 razy
przestawianie książek
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)!}\)
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)!}\)