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

Без однакових сусідів

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

Скільки різних рядків використовують усі $9$ літер слова $COMMITTEE$ (де $M$ , $T$ і $E$ трапляються по $2$ рази) так, щоб жодні $2$ однакові літери не стояли поруч?

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

Підказка

Застосуй принцип включень і виключень до того, які повторювані літери опиняються поруч; склеєна пара поводиться як один об’єкт.

Розв’язок

Без обмежень є $9! \div 2^{3} = 45360$ рядків.
Назвімо літеру склеєною, якщо її копії стоять поруч. Склеювання вибраного набору з $j$ літер лишає $9 - j$ об’єктів, серед яких $3 - j$ літер ще повторюються, що дає $(9 - j)! \div 2^{3 - j}$ рядків.
Для $j = 1$ це $8! \div 4 = 10080$ для кожної з $3$ літер, для $j = 2$ це $7! \div 2 = 2520$ для кожного з $3$ виборів, а для $j = 3$ це $6! = 720$ .
За принципом включень і виключень відповідь дорівнює $45360 - 3 \times 10080 + 3 \times 2520 - 720 = 21960$ .

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

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