Question

Есть десять друзей и у каждого друга есть своя ручка (все ручки разные ) . То сколькими способами можно раздать ручки так ; что бы ни кто из них не получил свою ручку .

Answer 1

Ответ:

1334961

Пошаговое объяснение: ${}$ У меня не получается придумать простое решение. Надеюсь, в своем сложном решении я не допустил ошибку. Обозначим через $S_n$ требуемое количество способов в случае, когда друзей не десять, а n. Очевидно, что $S_1=0;\ S_2=1;\ S_3=2$ (при  n=3 два способа - или первый передает свою ручку второму, второй третьему, третий первому, или первый третьему, третий второму, второй первому). Можно выписать все возможные перемещения ручек при  n=4, но легче вывести в общем виде рекуррентную формулу. Назвав одного из друзей первым, мы в первую очередь будем отслеживать судьбу его ручки.

1) Пусть первый отдал ручку k-му другу, а он отдал свою ручку первому. То есть мы имеем цикл длины 2 с участием первого друга. Таких циклов ровно (n-1). Далее нужно продумать судьбу остальных

(n-2) ручек, количество способов их перераспределить равно $S_{n-2}.$

Перемножая, получаем, что количество способов раздать ручки при условии, что первый друг участвует в цикле длины 2, равно

                                         $(n-1)\cdot S_{n-2}.$  

2)  Пусть первый участвует в цикле длины 3 (таких циклов (n-1)(n-2)). Остальные (n-3) ручки можно перераспределить $S_{n-3}$ способами, общее количество способов в этом случае равно

                                    $(n-1)(n-2)\cdot S_{n-3}.$

3) Аналогичная формула получается, если первый участвует в цикле длины 4, 5, и так далее, длины k - общее число способов будет равно                  $(n-1)(n-2)\ldots (n-(k-1))\cdot S_{n-k}$.

4) Если первый участвует в цикле длины (n-2), общее число способов будет равно  $(n-1)\cdot(n-2)\cdot\ldots \cdot4\cdot 3\cdot S_2.$

5) В цикле длиной (n-1) первый участвовать не может, так как иначе один друг остался бы со своей ручкой.

6) Последний случай - когда первый участвует в цикле длиной n - тут мы получаем $(n-1)\cdot(n-2)\cdot \ldots \cdot 3\cdot 2\cdot 1=(n-1)!$  способов.

Суммируя, получаем

$S_n=(n-1)\cdot S_{n-2}+(n-1)(n-2)\cdot S_{n-3}+\ldots +(n-1)\cdot\ldots\cdot 3\cdot S_2+(n-1)!.$

В принципе этой формулы уже достаточно, чтобы последовательно найти $S_4,\ S_5,\ \ldots ,\ S_{10}.$ Постараемся упростить вычисления. Заметим, что если заменить в выведенной формуле n на (n-1), получим

$S_{n-1}=(n-2)\cdot S_{n-3}+(n-2)(n-3)\cdot S_{n-4}+\ldots+(n-2)\cdot \ldots\cdot 3\cdot S_2+(n-2)!,$

откуда

                               $S_{n}=(n-1)(S_{n-2}+S_{n-1}).$

На мой взгляд, эта формула делает вычисления достаточно комфортными. Вспоминая, что $S_{2}=1; \ S_3=2,$ последовательно получаем:

                                        $S_4=3(S_3+S_2)=3(2+1)=9;$

                                       $S_5=4(S_4+S_3)=4(9+2)=44;$

                                     $S_6=5(S_5+S_4)=5(44+9)=265;$

                                   $S_7=6(S_6+S_5)=6(265+44)=1854;$

                                 $S_8=7(S_7+S_6)=7(1854+265)=14833;$

                               $S_9=8(S_8+S_7)=8(14833+1854)=133496;$

                             $S_{10}=9(S_9+S_8)=9(133496+14833)=1334961.$