Несколько задач по комбинаторике

[Alexey1]

Попробуйте следующее. Имеется $n$ ячеек и в каждую их них Вы ставите число от $1$ до $n$. Общее количество способов которыми можно это сделать равно $n^n$.
Теперь выбрасываем одно число и $A_1$ - множество способов которыми можете разместить $n-1$ числа по $n$ ячейкам. Ясно, что как минимум два элемента будут совпадать. Выбрасываем два числа и $A_2$ - множество способов которыми можете разместить $n-2$ числа по $n$ ячейкам. Также, как минимум 3 элемента будут совпадать. И так далее до $A_n$.
Теперь $\cup_{i=1}^n A_i$ - множество комбинаций в которых как минимум два элемента совпадают. Подсчитайте по формуле включения исключения количество элементов в этом объединении. После этого найдите сколько элементов содержится в дополнении. Затем используйте то, что количество комбинаций в которых все элементы разные равно $n!$, количество элементов в дополнении.