bulgakov

38. Слова с разными соседними буквами

Слова, в которых соседние буквы различны, а первая и последняя буквы тоже различны, считаются с помощью рекуррентного соотношения xn+xn−1=k(k−1)n−1x_n+x_{n-1}=k(k-1)^{n-1}: слов с разными соседями всего k(k−1)n−1k(k-1)^{n-1}, и они делятся на два класса — первая буква отличается от последней (xnx_n) или совпадает с ней (столько, сколько слов длины n−1n-1 из первого класса). Ответ: xn=(k−1)n+(−1)n(k−1)x_n=(k-1)^n+(-1)^n(k-1).

Что пригодится из прошлого: рекуррентные соотношения первого порядка — метод «умножить и сложить» (здесь множитель −1-1); размещения с повторениями и правило произведения. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Задача

Задача. Найти число слов длины nn (n≥2n\ge2) в алфавите A={a1,a2,…,ak}A=\{a_1,a_2,\dots,a_k\} из k≥2k\ge2 букв, в которых соседние буквы различны, а также различны первая и последняя буквы.

Обозначим это число через xnx_n. При n=2n=2 слово из двух букв, значит, нужно, чтобы буквы различались: x2=k(k−1)x_2=k(k-1) (первая буква — любая из kk, вторая — любая из k−1k-1 остальных).

Пример: алфавит {a,b,c}\{a,b,c\} и n=3n=3. Нужные слова — все слова из трёх различных букв: abc, acb, bac, bca, cab, cba. Их 66, что совпадёт с формулой ниже: x3=23−2=6x_3=2^3-2=6.

Другой взгляд на ту же задачу: бусины в кольце. Вокруг круглого стола стоят nn стульев, каждый нужно покрасить в один из kk цветов так, чтобы у любых двух соседних стульев (включая первый и последний) цвета были разными. Число способов — то же xnx_n: стулья по кругу — это буквы слова по порядку, цвета соседних стульев различны (включая пару «последний — первый»), а это в точности условие нашей задачи.

Как получить соотношение

Сначала посчитаем слова, в которых только соседние буквы различны (первая и последняя могут совпадать). Первую букву выбираем kk способами. Каждую следующую — любой, кроме предыдущей: k−1k-1 способ. По правилу произведения таких слов k(k−1)n−1k(k-1)^{n-1}.

Разделим эти слова на два непересекающихся класса:

  • а) первая и последняя буквы различны — по определению таких слов xnx_n;
  • б) первая и последняя буквы совпадают.

Сколько слов в классе (б)? Возьмём слово w1w2…wnw_1w_2\dots w_n с wn=w1w_n=w_1. Отбросим последнюю букву: получится слово w1…wn−1w_1\dots w_{n-1} длины n−1n-1. Соседние буквы в нём различны. А последняя буква wn−1w_{n-1} отличается от wn=w1w_n=w_1 — значит, первая и последняя буквы короткого слова различны: оно лежит в классе (а) для длины n−1n-1. Обратно: к любому слову длины n−1n-1 из такого класса допишем справа первую букву w1w_1: соседние буквы останутся различными (потому что wn−1≠w1w_{n-1}\ne w_1), а последняя буква станет равной первой. Эти два действия — «отбросить последнюю букву» и «дописать в конец первую» — взаимно обратны, поэтому слов в классе (б) столько же, сколько в классе (а) для длины n−1n-1, то есть ровно xn−1x_{n-1} (пример — ниже).

Пример (k=3k=3, n=3n=3). Слова класса (б) начинаются и кончаются одной буквой: aba, aca, bab, bcb, cac, cbc. Отбросим последнюю букву: ab, ac, ba, bc, ca, cb — это ровно все слова длины 22 с разными буквами, их x2=3⋅2=6x_2=3\cdot2=6.

Значит, при n≥3n\ge3

xn+xn−1=k(k−1)n−1,x2=k(k−1).\boxed{x_n+x_{n-1}=k(k-1)^{n-1},\qquad x_2=k(k-1)}.

Решение методом умножения

Запишем соотношение как xn=−xn−1+k(k−1)n−1x_n=-x_{n-1}+k(k-1)^{n-1}. Это уравнение вида xm+1=p xm+f(m)x_{m+1}=p\,x_m+f(m) (формула (1) из главы 35; здесь m=n−1m=n-1) с p=−1p=-1 и f(m)=k(k−1)mf(m)=k(k-1)^m. Выпишем его для n,n−1,…,3n,n-1,\dots,3 и добавим x2=k(k−1)x_2=k(k-1); множители 1,−1,(−1)2,…,(−1)n−21,-1,(-1)^2,\dots,(-1)^{n-2}:

×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)

После сложения члены xn−1,…,x3x_{n-1},\dots,x_3 сокращаются, и остаётся

xn=k((k−1)n−1−(k−1)n−2+(k−1)n−3−⋯+(−1)n−2(k−1)).x_n=k\Bigl((k-1)^{n-1}-(k-1)^{n-2}+(k-1)^{n-3}-\dots+(-1)^{n-2}(k-1)\Bigr).

В скобках сумма геометрической прогрессии из n−1n-1 слагаемых с первым членом (k−1)n−1(k-1)^{n-1} и знаменателем r=−1k−1r=-\dfrac1{k-1}. Её сумма равна a1(1−rn−1)1−r\dfrac{a_1(1-r^{n-1})}{1-r}, где 1−r=kk−11-r=\dfrac k{k-1}. Поэтому

xn=k (k−1)n−1⋅1−(−1k−1)n−1kk−1=(k−1)((k−1)n−1−(−1)n−1)=(k−1)n+(−1)n(k−1).\begin{aligned} x_n&=k\,(k-1)^{n-1}\cdot\frac{1-\left(-\frac1{k-1}\right)^{n-1}}{\frac k{k-1}}\\ &=(k-1)\Bigl((k-1)^{n-1}-(-1)^{n-1}\Bigr)\\ &=(k-1)^n+(-1)^n(k-1). \end{aligned}

Итак,

xn=(k−1)n+(−1)n(k−1).\boxed{x_n=(k-1)^n+(-1)^n(k-1)}.

Проверка подстановкой. Убедимся, что эта формула подходит. При n=2n=2: (k−1)2+(k−1)=(k−1)k(k-1)^2+(k-1)=(k-1)k ✓. Далее

xn+xn−1=(k−1)n+(−1)n(k−1)+(k−1)n−1+(−1)n−1(k−1)=(k−1)n−1((k−1)+1)=k(k−1)n−1 ✓.\begin{aligned} x_n+x_{n-1}&=(k-1)^n+(-1)^n(k-1)\\ &\quad+(k-1)^{n-1}+(-1)^{n-1}(k-1)\\ &=(k-1)^{n-1}\bigl((k-1)+1\bigr)=k(k-1)^{n-1}\ \checkmark. \end{aligned}

Члены (−1)n(k−1)(-1)^n(k-1) и (−1)n−1(k−1)(-1)^{n-1}(k-1) взаимно уничтожились. Так как соотношение и x2x_2 однозначно определяют все xnx_n, формула верна.

Проверка перебором

Для k=3k=3 сравним: сколько всего слов с разными соседями, как они делятся на два класса, и что даёт формула. Столбец xnx_n — слова длины nn, у которых первая буква не совпадает с последней; столбец xn−1x_{n-1} — слова длины nn, у которых первая буква совпадает с последней (их ровно xn−1x_{n-1}, как мы доказали).

nn Всего xnx_n xn−1x_{n-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

Числа 6,6,18,30,66,126,2586,6,18,30,66,126,258 — значения формулы 2n+(−1)n⋅22^n+(-1)^n\cdot2; в каждой строке, начиная с n=3n=3, первое число равно сумме двух следующих (24=18+624=18+6, 48=30+1848=30+18).

Примеры

1. k=4k=4, n=3n=3: 33−3=243^3-3=24 слов. Проверка: первая буква — 44 способа, вторая — 33, третья должна отличаться от второй и от первой: 22 способа; всего 4⋅3⋅2=244\cdot3\cdot2=24.

2. Кольцо из 55 бусин в 33 цветах: x5=25−2=30x_5=2^5-2=30.

Частые ошибки

  • Ограничиться соседями. Условие о первой и последней букве обычно меняет ответ: xn≤k(k−1)n−1x_n\le k(k-1)^{n-1}. Например, при k=3k=3, n=3n=3 слов с разными соседями 1212, а с разными первой и последней буквами только 66.
  • Решить классы (б) как xnx_n вместо xn−1x_{n-1}: удалив последнюю букву, мы переходим к длине n−1n-1.
  • Неверный знак (−1)n(-1)^n. При чётном nn прибавляется k−1k-1, при нечётном вычитается.
  • Применить формулу при n=1n=1. Условие задачи — n≥2n\ge2.

Проверь себя

1. Найдите число слов длины 44 в алфавите из 33 букв, у которых соседние буквы различны и первая буква отличается от последней.

Решение

x4=(3−1)4+(−1)4⋅2=16+2=18x_4=(3-1)^4+(-1)^4\cdot2=16+2=18.

2. Сколько слов длины 55 из 44 букв имеют все соседние буквы различными (первая с последней может совпадать)?

Решение

k(k−1)n−1=4⋅34=324k(k-1)^{n-1}=4\cdot3^4=324.

3. Сколько существует способов покрасить кольцо из 66 бусин в 22 цвета так, чтобы соседние бусины были разных цветов?

Решение

x6=(2−1)6+(−1)6(2−1)=1+1=2x_6=(2-1)^6+(-1)^6(2-1)=1+1=2: цвета чередуются, и первая бусина может быть любого из двух цветов.

4. Покажите, что для нечётного nn и k=2k=2 таких слов нет.

Решение

xn=1n+(−1)n⋅1=1−1=0x_n=1^n+(-1)^n\cdot1=1-1=0. Действительно, при двух цветах соседние буквы чередуются, и при нечётной длине первая и последняя совпадают.

Итог

  • Слов с разными соседями k(k−1)n−1k(k-1)^{n-1}; они делятся на два класса: первая ≠ последней (xnx_n) и первая = последней (xn−1x_{n-1}).
  • Соотношение: xn+xn−1=k(k−1)n−1x_n+x_{n-1}=k(k-1)^{n-1}, x2=k(k−1)x_2=k(k-1).
  • Решение: xn=(k−1)n+(−1)n(k−1)x_n=(k-1)^n+(-1)^n(k-1); то же число — раскрасок кольца из nn бусин в kk цветов.
ПрактикаЗагружаем тест…