pomylone czapki przedszkolaków

[poetaopole]

Grupa n przedszkolaków zostawiła rano swoje czapki w szatni. Ze względu na zamieszanie po południu każde z nich wróciło do domu w nie swojej czapce. Na ile sposobów jest to możliwe, jeśli: a) n=3, b) n=4, c) n=5? Komentarz: podpunkt a) robimy dość łatwo na piechotę; podpunkt b) nie bez trudu, ale da się, ale już podpunkt c) bez znalezienia algorytmu kombinatorycznego zajmuje mnóstwo czas. Kto da radę?

[Paulina-Anna]

Szukamy permutacji bez punktu stałego - nieporządków.

Powiedzmy, że \(\displaystyle{ n}\)-ty przedszkolak dostał \(\displaystyle{ i}\)-tą czapkę. Może tak się stać na \(\displaystyle{ n -1}\)sposobów. Zachodzą teraz dwie możliwości:

1) Uczeń o numerze \(\displaystyle{ i}\) nie otrzymał czapki pierwszej. Nasz przypadek sprowadza się zatem do problemu z \(\displaystyle{ n -1}\) przedszkolakami i tyloma czapkami: każda z pozostałych \(\displaystyle{ n -1}\) osób ma jeden niedozwolony numer czapki (uczniowi o numerze \(\displaystyle{ i}\) nie wolno wziąć czapki \(\displaystyle{ 1}\).),
2) Uczeń o numerze \(\displaystyle{ i}\) wziął czapkę pierwszą. Teraz przypadek redukuje się do problemu \(\displaystyle{ n- 2}\) osób i \(\displaystyle{ n- 2}\) czapek.

Ogólnie mamy wzór rekurencyjny na liczbę nieporządków:

\(\displaystyle{ !n = (n-1)(!(n-2) + !(n-1))}\), przy czym \(\displaystyle{ !0 = 1, !1=0}\) (identyczna występuje dla silni z odpow. war. pocz.)

Wzór jawny stosuje zasadę włączeń i wyłączeń:

\(\displaystyle{ !n = n! \sum_{0}^{n} \frac{(-1)^i}{i!}}\)

[poetaopole]

a) 2; b) 9; c) 44

[Paulina-Anna]

Zgadza się