Пусть $W i$ — это количество слов инопланетят, состоящих из $i$ букв.

Заметим, что единственное однобуквенное слово — это слово А. Двухбуквенных слов вообще нет, так как первая и последняя, то есть первая и вторая буквы — это А, но тогда две буквы А стоят рядом, что противоречит определению инопланетного слова. Трёхбуквенное слово тоже только одно — АБА. И четырёхбуквенное слово единственно — АББА. Таким образом,

W1 =1,W2 =0,W3 =1,W4 =1

Рассмотрим теперь какое-нибудь слово $ω$ длины $n,$ где $n >4.$ Его последняя буква — это точно буква А, так как каждое слово начинается и заканчивается буквой А. Предпоследняя буква — это Б, так как две буквы А не могут идти подряд. Есть два варианта, какой может быть буква перед Б, то есть предпредпоследняя буква слова $ω$ :

1) Это буква А. Тогда слово $ω$ имеет вид А...АБА. Рассмотрим строку из первых $n− 2$ букв этого слова. Она начинается и заканчивается на А, а так же в ней нет двух букв А подряд или трёх букв Б подряд, так как иначе $ω$ не было бы словом. А значит эта строка сама является словом.

2) Это буква Б. Тогда перед этой буквой Б стоит буква А, там как три буквы Б не могут идти подряд, и слово $ω$ имеет вид А...АББА. Аналогично случаю 1, строка, образованная первыми $n− 3$ буквами $ω$ будет являться словом.

Получается, что слово $ω$ могло быть получено либо приписыванием строки БА в конец какого-нибудь слова из $n − 2$ букв, либо приписыванием строки ББА в конец какого-нибудь слова из $n− 3$ букв. При этом, приписав в конец каждого из $Wn−2$ слов длины $n− 2$ строку БА, мы получим $Wn−2$ различных слов длины $n.$ Аналогично, приписав в конец каждого из $Wn −3$ слов длины $n − 3$ строку ББА, мы получим $Wn −3$ различных слов длины $n.$ Отсюда,

Wn = Wn−2+ Wn−3

Пользуясь этой формулой, найдем $Wi$ для $i= 5,...,20.$


$W1$	$W2$	$W3$	$W4$	$W5$	$W6$	$W7$	$W8$	$W9$	$W10$

$1$	$0$	$1$	$1$	$1$	$2$	$2$	$3$	$4$	$5$

Итак, в словаре сказочной планеты 86 20-буквенных слов.

Комбинаторика и логика на ПВГ