Задание EGEINF01E706: Подсчёт слов и последовательностей

Основание системы b = 10, длина n = 4. Разрешённые чётные цифры: 0, 2, 4, 6, 8; нечётные: 1, 3, 5, 7, 9. Первая цифра не может быть нулём, иначе число имеет меньшую длину.

Соседние цифры обязаны иметь разную чётность. Значит, после выбора чётности первой цифры весь порядок чётностей однозначен. Обозначим чётную позицию Ч, нечётную Н. Цифры не повторяются; из разных классов одна и та же цифра появиться не может, поэтому отдельно распределяем чётные и нечётные цифры.

Обозначим A(m, k) число упорядоченных выборов k различных элементов из m: A(m, k) = m · (m − 1) · … · (m − k + 1), а A(m, 0) = 1. Первый множитель в каждом случае — число допустимых первых цифр. Затем исключаем уже занятые цифры из соответствующих классов и заполняем оставшиеся позиции.

Шаблон ЧНЧН. Первую цифру выбираем из 2, 4, 6, 8. После фиксации крайних цифр остаётся выбрать 1 чётных из 4 и 2 нечётных из 5.
Число способов = 4 · A(4, 1) · A(5, 2) = 4 · 4 · 20 = 320.

Шаблон НЧНЧ. Первую цифру выбираем из 1, 3, 5, 7, 9. После фиксации крайних цифр остаётся выбрать 2 чётных из 5 и 1 нечётных из 4.
Число способов = 5 · A(5, 2) · A(4, 1) = 5 · 20 · 4 = 400.

Всего = 320 + 400 = 720.

Проверка: перебираем все упорядоченные наборы различных разрешённых цифр нужной длины, убираем ведущий ноль и проверяем каждую соседнюю пару. Получается 720. Разбиение по первому классу исчерпывает все возможности, поэтому ни один подходящий набор не потерян и не посчитан дважды.

Ответ: 720.