Здравствуйте, Кодт, Вы писали:



К>Поставил натурный эксперимент на a=3, n=15, k=5. (Тупо проверил все 14 миллионов строк). Получил R=14364157, Q=738
К>Хотя где-то я, всё-таки, налажал...
В общем-то, тот факт, что R получилось больше чем 3¹⁵ (то есть больше чем число всевозможных слов) уже выглядит подозрительно. Не говоря уж о том, что Q+R будет ещё больше

К>>Попробуем построить строки длины n с повторами.

К>R(n) = R(n-1) * a     -- дописали произвольную букву к каждой строке с повторами
К>     ...
К>     + Q(n-2)         -- взяли строку без повторов и удвоили ей хвост длины 2

К>но КАЖЕТСЯ, что мы действительно имеем дело с непересекающимися классами, поэтому можем суммировать как есть.
Круто, но процитированные классы таки пересекаются.
Например, строку "ABABA" можно получить из "ABAB" добавлением "A", либо из "ABA" добавлением суффикса "BA".
То есть в этой уникальной строке повторяются разные подстроки: "ABABA" и "ABABA", и она оказывается посчитанной дважды.