Дано натуральное число п. В Ёжгороде имеется центральная площадь и п периферийных площадей, а также п улиц, соединяющих центральную площадь с периферийными. Мэр хочет создать Реестр городских объектов, записав в строчку названия всех улии, и площадей. Регламент требует, чтобы название каждой улицы стояло в Реестре правее названий обеих площадей, которые она соединяет. Сколькими способами мэр может составить Реестр?
Подсказка
Докажите индукцией по n
Решение
Ответ: 
последовательностей. Решение. Докажем это индукцией по 
. База 
очевидна.
Индукционный переход 
. Последняя запись в реестре города с ( 
) улицей — это название некоторой улицы. Уберем эту запись, а периферийную площадь этой улицы, упомянутую в реестре ранее, выделим красным цветом. Красная запись может находиться в любом месте оставшегося реестра. При ее удалении получается реестр города с улицами. Значит, для составления реестра в городе 
улицей можно
— выбрать периферийную площадь, которую мы будем считать красной (это можно сделать способами),
— взять реестр остальной части города с улицами (по индукционному предположению имеется 
вариантов такого реестра),
— в любое место этого реестра вставить запись о красной площади ( 
вариантов)
— и добавить в конец запись о красной улице.