38. Слова с разными соседними буквами
Слова, в которых соседние буквы различны, а первая и последняя буквы тоже различны, считаются с помощью рекуррентного соотношения : слов с разными соседями всего , и они делятся на два класса — первая буква отличается от последней () или совпадает с ней (столько, сколько слов длины из первого класса). Ответ: .
Что пригодится из прошлого: рекуррентные соотношения первого порядка — метод «умножить и сложить» (здесь множитель ); размещения с повторениями и правило произведения. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Задача
Задача. Найти число слов длины () в алфавите из букв, в которых соседние буквы различны, а также различны первая и последняя буквы.
Обозначим это число через . При слово из двух букв, значит, нужно, чтобы буквы различались: (первая буква — любая из , вторая — любая из остальных).
Пример: алфавит и . Нужные слова — все слова из трёх различных букв: abc, acb, bac, bca, cab, cba. Их , что совпадёт с формулой ниже: .
Другой взгляд на ту же задачу: бусины в кольце. Вокруг круглого стола стоят стульев, каждый нужно покрасить в один из цветов так, чтобы у любых двух соседних стульев (включая первый и последний) цвета были разными. Число способов — то же : стулья по кругу — это буквы слова по порядку, цвета соседних стульев различны (включая пару «последний — первый»), а это в точности условие нашей задачи.
Как получить соотношение
Сначала посчитаем слова, в которых только соседние буквы различны (первая и последняя могут совпадать). Первую букву выбираем способами. Каждую следующую — любой, кроме предыдущей: способ. По правилу произведения таких слов .
Разделим эти слова на два непересекающихся класса:
- а) первая и последняя буквы различны — по определению таких слов ;
- б) первая и последняя буквы совпадают.
Сколько слов в классе (б)? Возьмём слово с . Отбросим последнюю букву: получится слово длины . Соседние буквы в нём различны. А последняя буква отличается от — значит, первая и последняя буквы короткого слова различны: оно лежит в классе (а) для длины . Обратно: к любому слову длины из такого класса допишем справа первую букву : соседние буквы останутся различными (потому что ), а последняя буква станет равной первой. Эти два действия — «отбросить последнюю букву» и «дописать в конец первую» — взаимно обратны, поэтому слов в классе (б) столько же, сколько в классе (а) для длины , то есть ровно (пример — ниже).
Пример (, ). Слова класса (б) начинаются и кончаются одной буквой: aba, aca, bab, bcb, cac, cbc. Отбросим последнюю букву: ab, ac, ba, bc, ca, cb — это ровно все слова длины с разными буквами, их .
Значит, при
Решение методом умножения
Запишем соотношение как . Это уравнение вида (формула (1) из главы 35; здесь ) с и . Выпишем его для и добавим ; множители :
×1:
x_n=−x_{n-1}+k(k−1)^(n-1)
×(−1):
x_{n-1}=−x_{n-2}+k(k−1)^(n-2)
×(−1)²:
x_{n-2}=−x_{n-3}+k(k−1)^(n-3)
· · ·
×(−1)^(n−3):
x_3=−x_2+k(k−1)²
×(−1)^(n−2):
x_2=k(k−1)
После сложения члены сокращаются, и остаётся
В скобках сумма геометрической прогрессии из слагаемых с первым членом и знаменателем . Её сумма равна , где . Поэтому
Итак,
Проверка подстановкой. Убедимся, что эта формула подходит. При : ✓. Далее
Члены и взаимно уничтожились. Так как соотношение и однозначно определяют все , формула верна.
Проверка перебором
Для сравним: сколько всего слов с разными соседями, как они делятся на два класса, и что даёт формула. Столбец — слова длины , у которых первая буква не совпадает с последней; столбец — слова длины , у которых первая буква совпадает с последней (их ровно , как мы доказали).
| Всего | Формула | |||
|---|---|---|---|---|
| 2 | 6 | 6 | — | 6 |
| 3 | 12 | 6 | 6 | 6 |
| 4 | 24 | 18 | 6 | 18 |
| 5 | 48 | 30 | 18 | 30 |
| 6 | 96 | 66 | 30 | 66 |
| 7 | 192 | 126 | 66 | 126 |
| 8 | 384 | 258 | 126 | 258 |
Числа — значения формулы ; в каждой строке, начиная с , первое число равно сумме двух следующих (, ).
Примеры
1. , : слов. Проверка: первая буква — способа, вторая — , третья должна отличаться от второй и от первой: способа; всего .
2. Кольцо из бусин в цветах: .
Частые ошибки
- Ограничиться соседями. Условие о первой и последней букве обычно меняет ответ: . Например, при , слов с разными соседями , а с разными первой и последней буквами только .
- Решить классы (б) как вместо : удалив последнюю букву, мы переходим к длине .
- Неверный знак . При чётном прибавляется , при нечётном вычитается.
- Применить формулу при . Условие задачи — .
Проверь себя
1. Найдите число слов длины в алфавите из букв, у которых соседние буквы различны и первая буква отличается от последней.
Решение
.
2. Сколько слов длины из букв имеют все соседние буквы различными (первая с последней может совпадать)?
Решение
.
3. Сколько существует способов покрасить кольцо из бусин в цвета так, чтобы соседние бусины были разных цветов?
Решение
: цвета чередуются, и первая бусина может быть любого из двух цветов.
4. Покажите, что для нечётного и таких слов нет.
Решение
. Действительно, при двух цветах соседние буквы чередуются, и при нечётной длине первая и последняя совпадают.
Итог
- Слов с разными соседями ; они делятся на два класса: первая ≠ последней () и первая = последней ().
- Соотношение: , .
- Решение: ; то же число — раскрасок кольца из бусин в цветов.
