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

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

Поставил натурный эксперимент на a=3, n=15, k=5. (Тупо проверил все 14 миллионов строк). Получил R=14364157, Q=738
То есть, строк без повторов радикально меньше, чем строк с повторами.

Что, если переписать формулу, посчитать именно дополнения?

Q(n) = U(n) - R(n)
     = U(n) - R(n-1)*a            - Q(n-1) - Q(n-2) - ... - Q(m)
     = U(n) - (U(n-1)-Q(n-1))*a   - Q(n-1) - Q(n-2) - ... - Q(m)
     = U(n) - U(n-1)*a + Q(n-1)*a - Q(n-1) - Q(n-2) - ... - Q(m)
     =                   Q(n-1)*a - Q(n-1) - Q(n-2) - ... - Q(m)

Хотя где-то я, всё-таки, налажал... Результаты по формуле — меньше результатов брутфорса.