XII OM - III - Zadanie 6

Ktoś napisał sześć listów do sześciu osób i zaadresował do nich sześć kopert. Iloma sposobami można listy tak włożyć do kopert, żeby żaden list nie trafił do właściwej koperty?

Rozwiązanie

Niech $ F (n) $ oznacza ilość wszystkich sposobów takiego włożenia $ n $ listów $ L_1, L_2, \ldots, L_n $ do $ n $ kopert $ K_1, K_2, \ldots, K_n $, żeby żaden list $ L_i $ nie trafił do właściwej koperty $ K_i $, czyli krócej, żeby nie było żadnego ,,trafienia''. Mamy obliczyć $ F (6) $.

Przypuśćmy, że wkładamy fałszywie wszystkie listy umieszczając list $ L_1 $ w kopercie $ K_i $ ($ i \ne 1 $). Możliwe są $ 2 $ przypadki :

a) List $ L_i $ trafił do koperty $ K_1 $. Pozostałe $ 4 $ listy należy wówczas włożyć fałszywie do pozostałych $ 4 $ kopert, na co jest $ F (4) $ sposobów. Ponieważ $ K_i $ może być każdą z $ 5 $ kopert $ K_2 $, $ K_3 $, $ K_4 $, $ K_5 $, $ K_6 $, więc przypadek a) może się zdarzyć $ 5 \cdot F (4) $ razy.

b) List $ L_i $ nie trafia do koperty $ K_1 $. Przypisując listowi $ L_i $ kopertę $ K_1 $ jako ,,niby-właściwą'' możemy powiedzieć, że wtedy żaden z listów $ L_2 $, $ L_3 $, $ L_4 $, $ L_5 $, $ L_6 $ nie trafia do właściwej koperty, na co jest $ F (5) $ sposobów. A ponieważ $ K_i $ może być - jak poprzednio - każdą z $ 5 $ kopert, więc przypadek b) może się zdarzyć $ 5 \cdot F (5) $ razy.

Ponieważ przypadki a) i b) obejmują wszystkie możliwości, więc

\[<br />
F (6) = 5P (5) + 5P (4)<br />
\]

Analogicznie

\[ F (5) = 4F (4) + 4F (3) \]
\[ F (4) = 3F (3) + 3F (2) \]
\[ F (3) = 2F (2) + 2F (1). \]

Lecz oczywiście

\[<br />
F(1)=0, \     F(2) = 1,<br />
\]

wobec czego z równań poprzednich otrzymujemy kolejno,

\[<br />
F (3) = 2,\   F (4) = 9,\   F (5) = 44, \  F (6) = 265.<br />
\]

Uwaga. W rozumowaniach powyższych rozwiązań I i II liczba $ 6 $ nie odgrywa żadnej istotnej roli. Można je równie dobrze zastosować do $ n $ listów i $ n $ kopert. Sposób I prowadzi wówczas do wzoru

\[<br />
(1) \qquad F (n) = (n - 1) F (n - 1) + (n - 1) F (n - 2).<br />
\]

Jest to tzw. wzór zwrotny, albo redukcyjny, z którego można obliczyć $ F (n) $, gdy znane są wartości $ F (n - 1) $ i $ F (n - 2) $. Podobnie sposób II prowadzi do wzoru redukcyjnego

\[<br />
(2) \qquad F(n) = n!- \binom{n}{1} F(n - 1) - \binom{n}{2} F(n - 2) - \ldots - \binom{n}{n-2} F (2) - 1.<br />
\]

Wzór (1) pozwala w następujący sposób obliczyć $ F (n) $ w zależności od $ n $. Napiszemy ten wzór w postaci

\[<br />
(3) \qquad F (n) - n F (n - 1 )= - [F (n - 1) - (n - 1) F(n-2)].<br />
\]

Ze wzoru (3) widzimy, że funkcja $ F (k) - kF (k - 1) $ ma dla każdego naturalnego $ k > 1 $ tę samą wartość bezwzględną, ale zmienia znak przy przejściu od $ k $ do $ k + 1 $. A ponieważ

\[<br />
F (2) - 2F (1) = 1,<br />
\]

więc

\[<br />
(4) \qquad F (n) - kF (n - 1) = (- 1)^n,\quad (n > 1).<br />
\]

Z równości (4) wynika, że

\[<br />
(5) \qquad \frac{F(n)}{n!} - \frac{F(n-1)}{(n - 1)!} = \frac{(-1)^n}{n!}.<br />
\]

Wprowadźmy oznaczenia

\[<br />
\frac{F(n)}{n!} = \varphi(n).<br />
\]

Wzór (5) przybiera postać

\[<br />
\varphi (n) - \varphi (n - 1) = \frac{(- 1)^n}{n!}.<br />
\]

Analogicznie

\[ \varphi (n - 1) - \varphi (n - 2) = \frac{(-1)^{n-1}}{(n-1)!} \]
\[ \ldots \]
\[ \varphi(2) - \varphi(1) = \frac{1}{2}.\]

Dodając te wzory i uwzględniając, że $ \varphi (1) = \frac{F(1)}{1} = 0 $ otrzymujemy

\[<br />
\varphi = \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \ldots + \frac{(-1)^n}{n!}.<br />
\]

Zatem

\[<br />
F (n) = n! \left[ \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \ldots + \frac{(-1)^n}{n!} \right].<br />
\]

Zadanie, które rozwiązaliśmy, nazywa się zagadnieniem Bernoulli'ego-Eulera o pozamienianych listach.

Komentarze

Dodaj nową odpowiedź