Все числа от 1 до 8 выписали в ряд… (вероятность и статистика)

№ .Перестановки без заданных троек подряд

Все числа от 1 до 8 выписали в ряд в каком-то порядке (каждое по одному разу). Расстановку этих чисел назовём хорошей, если в ней нельзя выбрать три числа $a$ , $b$ , $c$ , стоящие именно в таком порядке слева направо (не обязательно подряд), для которых либо $a < b < c$ (три числа идут по возрастанию), либо $b < c < a$ (первое из трёх самое большое, а два следующих по возрастанию). Сколько существует хороших расстановок?

Решение

Расстановка хорошая, если в ней нет троек по возрастанию и троек вида «большое, потом два по возрастанию». Покажем, что достаточно проверять тройки подряд идущих чисел, и посчитаем их количество рекуррентно.

Шаг . Что запрещено у соседних троек. Для трёх подряд идущих чисел запрещены образцы и . Допустимы , , , . Значит:

после подъёма обязательно спуск (два подъёма подряд запрещены);
после спуска можно либо снова спуск , либо подъём, но только с (образец ). Значение между и запрещено.

Шаг . Рекуррентный подсчёт. Будем строить расстановки длины , добавляя в конец новый элемент и пересчитывая числа по рангам. Состояние — ранги двух последних чисел. Обозначим:

— число хороших расстановок длины , в которых последнее число имеет ранг ;
— число способов получить спуск, при котором предпоследнее число имеет ранг ;
— число расстановок, оканчивающихся подъёмом, с последним числом ранга .

Тогда:

Шаг . Вычисления. Общее число хороших расстановок:

:
:
: (набор )
: (набор )
: (набор )

Шаг . Случай . Расстановки, оканчивающиеся спуском:

Расстановки, оканчивающиеся подъёмом:

Итого:

💡 Почему так

В хорошей расстановке нет трёх соседних чисел с образцом или . Поэтому после подъёма всегда идёт спуск, а после спуска подъём допустим только выше предыдущего числа. Это даёт рекуррентный подсчёт по рангам последних элементов.

Ответ

✓ dzmen.ru

Помогло?

Все числа от 1 до 8 выписали в ряд в каком-то порядке…