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

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

Да, именно это у меня и вышло в брутфорсе.
Получается, что надо дробить класс Q(n) строк без повторов длины n на подклассы вида Q(n, t1,t2,...) где ti — длина паразитного повтора

Подкласс t=2
xxxABA + BA = xxxABABA
                 --==
Подкласс t=3
xxxABCA + BCA = xxxABCABCA
                   ---===
Подкласс t=4
xxxABCDA + BCDA = xxxABCDABCDA
                     ----====

Подкласс t=2,4         --==
xxxABACA + CA   = xxxABACACA
xxxABACA + BACA = xxxABACABACA
                     ----====

Подкласс t=2,5
xxxABCADA + DA
xxxABCADA + BCADA

Подкласс t=3,5
xxxABACDA + CDA
xxxABACDA + BACDA

Тогда формула будет выглядеть вот так:

Q(n) = Q(n-1)*a
     - Q(n-1)             - повторы длины 1
     - Q(n-2) + Q(n-2,2)  - поскольку мы
     - Q(n-3) + Q(n-3,2) + Q(n-3,3)
     - Q(n-4) + Q(n-4,2) + Q(n-4,3) + Q(n-4,4) - Q(n-4,2,4)
     . . .

(если ничего не путаю)

Длины паразитных повторов — это положения вхождений последней буквы, с конца.
И вот это мне очень не нравится: чтобы за ними проследить, нам придётся не расписывать формулу для каждого подкласса
Q(n,t1) = Q(n-1,t1)*a + ... — ...,
а в завуалированной форме рожать все строки. А их, понятное дело, экспонента по основанию мощности алфавита (a). (Ну, ближе к (a-1), но всё равно не сахар).