szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 14 kwi 2019, o 17:38 
Użytkownik

Posty: 2216
Lokalizacja: Kraków
Niech D_n oznacza liczbę nieporządków zbioru n-elementowego dla n>0, czyli permutacji bez punktów stałych, ponadto D_0=1. Wykaż, że

D_{n+1}=n(D_n+D_{n-1})

Jak to zrobić?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
Mężczyzna Online
PostNapisane: 14 kwi 2019, o 18:46 
Użytkownik
Avatar użytkownika

Posty: 13584
Lokalizacja: Wrocław
Zobacz tutaj: https://pl.wikipedia.org/wiki/Nieporz%C4%85dek#Zliczanie_nieporz%C4%85dk%C3%B3w
Góra
Mężczyzna Offline
PostNapisane: 17 kwi 2019, o 01:16 
Użytkownik

Posty: 2216
Lokalizacja: Kraków
Czyli jak rozumiem uczeń pierwszy może dostać sprawdzian nie swój na (n-1) możliwości, niech to będzie i-ty sprawdzian, stąd te (n-1) na początku wyrażenia po prawej stronie. Jeśli i-ty uczeń nie otrzymał sprawdzianu pierwszego, to wywalamy pierwszego ucznia, pozostali są ponumerowani 2,3,...,n, a sprawdziany są ponumerowane 1,...,n, ale bez i-tego i w tej sytuacji dla każdego ucznia znowu jest dowolny wybór poza jednym zakazanym, to znaczy dla uczniów o numerach 2,3,...,n, ale nie i jest zakazany odpowiednio sprawdzian 2,3,...,n, a dla ucznia i zakazany jest 1. Stąd mamy składnik (n-1)(!(n-1). Natomiast jeśli i-ty uczeń otrzymał sprawdzian pierwszy to uczeń pierwszy z i- tym tworzą cykl i pozostaje nam n-2 uczniów ponumerowanych 2,3,...,n, ale bez i i n-2 sprawdzianów ponumerowanych tak samo. Czyli w tym przypadku będzie składnik (n-1)!(n-2). Te dwa przypadki wyczerpują wszystkie możliwości zatem ogólnie !n=(n-1)(!(n-1)+!(n-2)) czyli !(n+1)=n(!n+!(n-1)).
Czy tak jest dobrze?
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczba przedstawień liczby n w postaci sumy k liczb  Anonymous  2
 Liczba niezależności (grafy)  snowjay  0
 liczba uczniów - zadanie 2  myszka666  1
 Liczba dzielników, słów, układów brydżowych.  Leossj  1
 Liczba kombinacji zbioru z maksymalną sumą  mar1986  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl