У нас есть <tex> n </tex> чисел и столько же мест. Мы должны найти количество способов разместить эти числа так, что ни одно из чисел не оказалось на месте с таким же номером.
Предположим, что первое число оказалось на месте с номером <tex> i </tex>. Это можно сделать <tex> n-1 </tex> способами, так как первое число может оказаться на любом месте, кроме первого. Теперь есть 2 варианта, зависящие от того, окажется ли число с номером <tex> i </tex> на первом месте или нет.
1) * Число <tex> i </tex> на первом месте. Остается <tex> n-2 </tex> мест и <tex> n-2 </tex> чисел. То есть количество беспорядков от <tex> n-2 </tex>2) * Число <tex> i </tex> не может оказаться на первом месте. Это эквивалентно решению задачи с <tex> n-1 </tex> местами и <tex> n-1 </tex> числами (первое число уже заняло место, а остальные еще нет): у каждого числа будет одно запрещенное место (у числа с номером <tex> i </tex> запрещенным будет первое место). Получается количество беспорядков от <tex> n-1 </tex>. Эти 2 случая не пересекаются и поэтому суммируются. В первом случае число <tex> i </tex> занимает первое место, затем идет распределение остальных чисел, не зависящее от первого и <tex i </tex>-го чисел. Во втором же случае число с номером <tex> i </tex> попасть на первое место не может, а значит займет какое-то другое место, и распределение остальных чисел уже будет другое.
В итоге получается необходимая формула.
