Я тогда тоже поделюсь своими пока незаконченными рассуждениями. Можно разделить все нежелательные исходы на три группы, которые не пересекаются:
- В последовательности нет G
- Есть какое-то количество G, и все они находятся на расстоянии как минимум 1 буквы
- Есть только одна ‘GG’, которая занимает только первые две позиции
Для первого и третьего случая посчитать нетрудно. В первом случае это просто 3^{100}, а в третьем — 3^{98}. Сейчас я пытаюсь понять, как можно найти число комбинаций для второго случая. Пробую посчитать это число для коротких последовательностей и потом вывести для общего случая, при длине в n букв.