В разных городах мира есть три тайных агента. Нужно осуществить их ротацию, так, чтобы каждый из них сменил свою дислокацию. Сколькими способами это можно сделать? (Можно перебором, это очевидно: 231, 312. Всего: 2 способа).
В разных городах есть 4 тайных агента. Нужно осуществить их ротацию, так, чтобы каждый из них сменил дислокацию. Сколькими способами это можно сделать? (Можно перебором, это очевидно: 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321. Всего: 9 способов).
В разных городах есть 5 тайных агентов. Нужно осуществить такую ротацию, чтобы каждый сменил дислокацию. Сколькими способами это можно сделать?
Решить эту задачу для 6 и 7 тайных агентов. Решить ту же задачу для n.
*** нужны решения для 5, 6, 7 и n.
*** для 5 перебором получается вроде бы: 44.
В разных городах есть 4 тайных агента. Нужно осуществить их ротацию, так, чтобы каждый из них сменил дислокацию. Сколькими способами это можно сделать? (Можно перебором, это очевидно: 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321. Всего: 9 способов).
В разных городах есть 5 тайных агентов. Нужно осуществить такую ротацию, чтобы каждый сменил дислокацию. Сколькими способами это можно сделать?
Решить эту задачу для 6 и 7 тайных агентов. Решить ту же задачу для n.
*** нужны решения для 5, 6, 7 и n.
*** для 5 перебором получается вроде бы: 44.
Answers & Comments
Verified answer
Можно рассмотреть сразу для n, так для любых других будет понятно
Пусть имеется позиций
12345....n
1)Рассмотрим число вариантов для которых число 1 лежит на первой позиции это всего (n-1)! (потому что при фиксации 1-цы остальные будут «перетасовываться») аналогично и для остальных 2,3,4,...n то есть всего n*(n-1)!=n!
2) Рассмотрим случай когда будут ПО ДВА числа при их соответсвующие позициях к примеру (12)4579...n зафиксировав положение (12) и учитывая перемещение остальных получаем (n-2)! но всего таких вариантов C 2 n = n!/(2!*(n-2)!) тогда всего вариантов n!/2!
3) Аналогично и для всех остальных случаев для 3,4,...n
К примеру для 3-х фиксированных положений (123)...n
(n-3)!*n!/(3!*(n-3)!) = n!/3!
Так как нужно найти то положение в котором вышеперечисленные элементы НЕ ВХОДЯТ то используя формулы «включения и исключения» выходит
S=n!*(1-1+1/2!-1/3!+1/4!+...+(-1)^(n)/n!)
Проверим для n=5
S=5!*(1-1+1/2-1/6+1/24-1/120)=44
А [1/e] как раз равно:
1/e = 1/0!-1/1!+1/2!-1/3!+1/4!... и т.п.
Только в ответе к этой задаче – ряд не бесконечный, поэтому множитель [1/e] даёт дробную ошибку при его использовании, поскольку само [1/e] содержит в себе бесконечный ряд.
Забавно, что при замене (1-1+1/2!-1/3!+1/4!+...+(-1)^(n)/n!) на [1/e] для всех "n" получается тот же ответ, если округлять до ближайшего целого. Даже для n=2 и для n=1.
Не совсем разобрался в вашем решении. Чуть позже посмотрю. Спасибо!
v{n} = n * [v{n-1}] + (-1)^n ;
(через делители, используя результаты с компа)
v{0} = 1 (по определению),
v{1} = 1*[1] - 1 = 0 ,
v{2} = 2*[0] + 1 = 1 ,
v{3} = 3*[1] - 1 = 2 ,
v{4} = 4*[2] + 1 = 9 ,
v{5} = 5*[9] - 1 = 44 ,
v{6} = 6*[44] + 1 = 265 ,
v{7} = 7*[265] - 1 = 1854 и т.д.
Я теперь понял, как её доказать. Через ваше решение как раз получается, если скобки раскрыть.