Навчання / Бібліотека / Комбінаторика

Кругові заповнення символами

КомбінаторикаСкладне

Круговий журнал має $10$ комірок, причому комірка $10$ сусідить із коміркою $1$ . Кожна комірка отримує один із $3$ символів так, щоб сусідні комірки завжди відрізнялися. Заповнення, що відрізняються лише поворотом, вважаються різними. Скільки існує заповнень?

Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.

Підказка

Порівняй кругові заповнення з прямими рядами, кінці яких можуть збігатися або ні.

Розв’язок

Нехай $c (n)$ — кількість правильних кругових заповнень $n$ комірок; прямий ряд із $n$ комірок із різними сусідами можна заповнити $3 \times 2^{n - 1}$ способами.
У такому ряді останній символ або відрізняється від першого, і це кругове заповнення, враховане в $c (n)$ , або дорівнює першому; злиття цих однакових кінців дає кругове заповнення з $n - 1$ комірок, враховане в $c (n - 1)$ .
Отже, $c (n) = 3 \times 2^{n - 1} - c (n - 1)$ з $c (2) = 6$ .
Значення для $n = 3, \dots, 10$ — це $6, 18, 30, 66, 126, 258, 510, 1026$ , тож $c (10) = 1026$ .

Відповідь: $1026$

Наступна задача Назад до бібліотеки