Перестановку $(a_1, a_2, a_3, ..., a_{n-1}, a_n)$ элементов множества $\{1, 2, 3, ..., n\}$ назовем легальной, если нет двух последовательных членов, чья сумма кратна 3, и нет членов таких, что разность двух соседних с ними членов кратна 3. Например, перестановка $(4, 6, 2, 5, 3, 1)$ является легальной перестановкой множества чисел $\{1, 2, 3, 4 , 5, 6\}.$ Но $(1, 2, 5, 3, 4, 6)$ не является легальной перестановкой того же множества, так как числа 1 и 2 являются соседними и их сумма кратна 3. Более того, разность чисел, соседних с числом 4, то есть чисел 3 и 6, кратна 3.
a) Определите количество легальных перестановок множества $\{1, 2, 3, 4, 5, 6\}.$
b) Определите количество легальных перестановок множества $\{1, 2, 3, ..., 2016\}.$
Примечание: Перестановкой элементов множества называется упорядоченная последовательность, которая содержит все элементы множества по одному разу.
| |
