Inne, zadanie nr 105

Autor	Zadanie / Rozwiązanie
tomnow postów: 10	2012-12-12 17:43:10 Mamy n listów i n zaadresowanych kopert. Na ile sposobów można listy włożyć do kopert tak aby k listów trafiło do właściwych kopert?

tumor postów: 8070	2012-12-12 18:51:29 Z $n$ kopert wybieramy te $k$ kopert, w których listy będą właściwe. To zrobimy na ${n \choose k}$ sposobów. Pozostałe listy mają być pomieszane, ale skutecznie, to znaczy nie mają trafić do właściwych kopert. Chodzi tu o liczbę permutacji bez punktów stałych, czyli tzw. nieporządków. k-elementowych nieporządków jest $D(k)=k!\sum_{i=0}^{k}\frac{(-1)^i}{i!}$ a nas interesują nieporządki pozostałych n-k elementów, czyli $D(n-k)=(n-k)!\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}$ Ostatecznie jest możliwości ${n \choose k}D(n-k)={n \choose k}(n-k)!\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}$

tomnow postów: 10	2012-12-13 10:35:01 Dzięki tumor, działa :) Mam jeszcze takie zadanie nieco odwrotne: Mamy zaadresowanych n listów. Na ile sposobów można włożyć listy do kopert tak, aby żaden list nie znalazł się we właściwej kopercie?

tumor postów: 8070	2012-12-13 12:20:05 Jeśli rozumiem dobrze treść, to chodzi tu po prostu o liczbę n-elementowych nieporządków, czyli D(n).

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj