Вот, например, классическая задача из школьного курса комби:
В первом ряду театра 20 мест. Сколькими способами можно рассадить на них 20 зрителей так, чтобы каждый сел либо на своё место (по билету), либо на соседнее?

Здесь всё просто. Если первый сидит на своём месте, то задача сводится к аналогичной с аргументом на 1 меньше. Если же первый сел на второе место, то на первом месте может сидеть только второй, откуда находим рекуррентное соотношение $$a_n=a_{n-2}+a_{n-1},$$ причём $$a_1=1, a_2=2,$$ получается Фибоначчи. И тогда для $$n=20$$ ответом будет 21-е число Фибоначчи, сиречь 10946.

А что если капельку изменить условие? Скажем, разрешить зрителю, чтобы модуль разности между занятым им местом и местом, указанным в билете, не превышал 2? То есть, либо он садится на своё, либо на соседнее, либо через одно от своего. Вот как тогда считать?

Заранее спасибо!

задан 23 Ноя '14 12:54

изменен 24 Ноя '14 17:17

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
1

Здесь тоже получается рекуррентная последовательность, но несколько более сложная.

Обычно в таких случаях приходится рассматривать несколько "близкородственных" последовательностей, выражая их друг через друга. Прежде всего, пусть $%a_n$% есть количество тех расстановок, которое мы ищем. Будем их анализировать с конца. Число $%n$% находится либо на последнем месте, и тогда это даёт $%a_{n-1}$% расстановок, или на предпоследнем, или на третьем с конца.

Рассмотрим случай, когда $%n$% предпоследнее. Тогда у нас имеется $%n-1$% мест, на которых стоят числа от $%1$% до $%n-1$%, причём места мы нумеруем по порядку, и тогда ситуация слегка отличается от того, что было в оригинале. А именно, число $%n-3$% в исходной ситуации не могло быть на последнем месте. Так как у нас последнее место в результате перенумерации стало считаться $%(n-1)$%-м, появляется ограничение, что $%n-3$% не находится на $%(n-1)$%-м месте, а все остальные ограничения те же. Тогда количество случаев равно $%b_{n-1}$%, где через $%b_n$% мы обозначаем количество допустимых расстановок на $%n$% символах, в которых $%n-2$% не занимает последнее место.

Теперь проанализируем случай, когда $%n$% в исходной перестановке идёт третьим с конца. Здесь $%n-3$% не может идти на последнем месте, а $%n-4$% не идёт ни на одном из двух последних. Как и выше, сдвигаем номера мест, считая, что они занумерованы подряд числами от $%1$% до $%n-1$% после исключения символа $%n$% из перестановки. Тогда новое ограничение гласит, что $%n-3$% не занимает $%(n-1)$%-е место, а $%n-4$% не занимает $%(n-2)$%-е место. Эту величину мы считаем равной $%c_{n-1}$%, где через $%c_n$% обозначено число перестановок на $%n$% символах с дополнительными ограничениями, что $%n-2$% не может быть на $%n$%-м месте, а $%n-3$% не стоит на $%(n-1)$%-м.

Из сказанного выше следует, что $%a_n=a_{n-1}+b_{n-1}+c_{n-1}$%. Свяжем теперь аналогичными рекуррентными соотношениями две другие последовательности.

Пусть имеется перестановка на $%n$% символах, где $%n-2$% не находится на последнем месте. Если на последнем месте находится $%n$%, то предыдущие символы расставляются $%a_{n-1}$% способами, так как дополнительное ограничение исчезает. Пусть $%n$% находится на предпоследнем месте. Тогда на самом последнем может идти только $%n-1$%, и вариантов получается $%a_{n-2}$%. Наконец, если $%n$% находится на третьем справа месте, то на последнем месте по-прежнему $%n-1$%, а второе справа место не может занимать $%n-4$%. Легко видеть, что после обычного сдвига мест мы приходим к величине $%b_{n-2}$%, откуда $%b_n=a_{n-1}+a_{n-2}+b_{n-2}$%.

Наконец, анализируем соотношение для $%c_n$%. Если $%n$% находится на последнем месте, то одно из ограничений пропадает, и оказывается, что $%n-3$% не занимает $%(n-1)$%-е место; таких вариантов $%b_{n-1}$%. Если $%n$% на предпоследнем месте, то в самом конце стоит $%n-1$%, и вариантов оказывается $%a_{n-2}$%. Наконец, если $%n$% на третьем месте справа, то последним идёт $%n-1$%, а между ними может быть только $%n-2$%, что приводит к $%a_{n-3}$% вариантам и формуле $%c_n=b_{n-1}+a_{n-2}+a_{n-3}$%.

Теперь всё определено однозначно, и остальное лишь дело техники. Фактически, здесь всё сводится к задачам о матрицах. Из формул, указанных выше, путём исключения неизвестных можно прийти к формуле $%a_{n+1}=a_n+2(a_{n-1}+a_{n-2}+a_{n+3})-(a_{n-4}+a_{n-5})$%. Характеристическое уравнение здесь разложимо на множители, и если этим воспользоваться, то получается далее не упрощаемое рекуррентное выражение одного члена последовательности через пять предыдущих. Вот как оно выглядит: $%a_{n+5}=2a_{n+4}+2a_{n+2}-a_n$%. Сама последовательность, начиная с нулевого члена, при этом такова: 1, 1, 2, 6, 14, 31, 73, 172, ... и так далее. Заметим, что только $%a_0=a_1=1$% можно задавать в качестве начальных условий, а далее действует рекуррентное соотношение, если члены с отрицательными номерами считать равными нулю.

ссылка

отвечен 23 Ноя '14 20:33

изменен 24 Ноя '14 15:35

@falcao: Я эмпирически тоже получил результат $%a_{n+5}=2a_{n+4}+2a_{n+2}−a_n$%, но не знал, как его доказать.

(23 Ноя '14 20:44) EdwardTurJ

@EdwardTurJ: здесь интересно было бы "задним числом" установить некую естественную биекцию между двумя множествами (понятно, какими). Такого рода конструкции почти всегда проходят.

(23 Ноя '14 21:26) falcao

@falcao, Большое спасибо! Сразу так много материала, попытаюсь разобраться.

(24 Ноя '14 15:29) حنين
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,482
×1,405
×1,141
×376
×49

задан
23 Ноя '14 12:54

показан
1492 раза

обновлен
24 Ноя '14 15:35

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru