Porównanie permutacji

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 747 razy

Porównanie permutacji

Post autor: mol_ksiazkowy »

Niech \(\displaystyle{ D_n}\) będzie liczbą nieporządków (permutacji bez punktów stałych) zbioru \(\displaystyle{ X= \{1,..,n \}}\) zaś \(\displaystyle{ E_n}\) liczbą tych permutacji, które mają tylko jeden punkt stały. Udowodnić, że \(\displaystyle{ |D_n - E_n |=1}\)
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Porównanie permutacji

Post autor: Premislav »

Łatwo zauważyć, że \(\displaystyle{ E_{n}=nD_{n-1}}\) – na \(\displaystyle{ n}\) sposobów wybieramy jedyny punkt stały permutacji, na \(\displaystyle{ D_{n-1}}\) sposobów mieszamy pozostałe. Ponadto mamy \(\displaystyle{ D_{n}=(n-1)\left(D_{n-1}+D_{n-2}\right)}\), co sugeruje, że zadziała tutaj prosta indukcja po \(\displaystyle{ n}\): istotnie,
dla \(\displaystyle{ n=2}\) jest \(\displaystyle{ D_{2}=1, \ E_{2}=0}\), więc rzeczywiście \(\displaystyle{ |D_{2}-E_{2}|=1}\). Przypuśćmy, że dla pewnego \(\displaystyle{ n\in \NN^{+}, \ n\ge 2}\) jest \(\displaystyle{ |D_{n}-E_{n}|=1}\), a innymi słowy, z powyższych zależności rekurencyjnych, \(\displaystyle{ |D_{n}-nD_{n-1}|=1}\). Mamy wówczas
\(\displaystyle{ |D_{n+1}-E_{n+1}|=|n(D_{n}+D_{n-1})-(n+1)D_{n}|=|nD_{n-1}-D_{n}|=|D_{n}-nD_{n-1}|=|D_{n}-E_{n}|=1}\)
c.k.d.
ODPOWIEDZ