А понять такой простой теоремы не можете

[fiviol]

В обязанности дежурного по учреждению во время праздников включен обход здания. Здание имеет n этажей, на каждом этаже один коридор. В концах каждого коридора есть выходы на две лестницы, расположенные в левом и правом крыле здания, соединяющие все этажи. Лифт не работает

Comments

[lithovore]

n!^2

[fiviol]

Нет. При n=1, например, маршрутов, удовлетворяющих условиям, нет вообще.

[lithovore]

А, понял. Тогда точное значение не назову, но предположу, что на бесконечности оно будет приблизительно равно (n!/e)^2.

[irishoak]

Я правильно понимаю, что при n=2 --- тоже?

[irishoak]

Для педантизму. "Обход начинается в левом конце коридора первого этажа" --- значит, что первым делом именно по первому этажу и надо сначала пройти, или можно сначала по лестнице? (Я понимаю, что ответы в n раз различаются, но всё же...)

И более существенный вопрос. Если я начал проходом по первому этажу слева направо --- могу ли я закончить проходом по нему же справа налево? (Ведь маршрут нециклический...)

[fiviol]

Начинать движение можно по коридору, можно по лестнице.

По второму вопросу не понял, в чем затруднение. Можно, если все условия инструкции соблюдены.

[irishoak]

Ответ в виде

[fiviol]

Мною принимается. А вот ЖЖ такой ответ не принял, и отправил его в подозрительные комментарии, где я его только что случайно обнаружил.:)

[iad]

Не окончательный ответ, а предварительный: n! раз по столько, сколько есть пермутаций n элементов, в которых на каком месте k не стоит элемент номер k или k+1.
Для n=3 такая пермутация одна (312), поэтому сотрудников может быть 6 (обход 132132 и то же с произвольной перенумерацией этажей).
Для n=4 их три (3412, 3421, 4123), соответственно сотрудников может быть 72.
Для n=5 их шестнадцать …

[fiviol]

Не понимаю пока, какой комбинаторный смысл имеют эти пермутации, но ответы совпадают с моими.
Верно ли, что из пермутации (312) получается маршрут 132132? Попробую догадаться: на нечетные места ты поставил числа в порядке возрастания 1.2.3., а на четных стоит та самая пермутация: .3.1.2
Остальное додумаю завтра, хотя, кажется, твоя мысль уже понятна.

[iad]

Да, все правильно. Количество пермутаций для n от 1 до 11 (оно действительно стремится к n!/e²): 0, 0, 1, 3, 16, 96, 675, 5413 (это простое число), 48800, 488592, 5379333. Для n=7 получается 3 402 000 сотрудников.

[fiviol]

Есть такая в OEIS:
http://oeis.org/A000271