Подсчет количества слов, удовлетворяющих условию

[Joker_vD]

Имеется некий конечный алфавит $\mathbb A = \{\, a,b,c,\,\dots \,\},\; |\mathbb A| = n$. Ясно, что слов длины $m$ над этим алфавитом существует ровно $|\mathbb A^m| = n^m$. Теперь вводится некий предикат $P(x),\; x\in \mathbb A^*$ и рассматриваются слова длины $m$, удовлетворяющие этом предикату. Нужно найти их количество, т.е. $|\{\,x\in\mathbb A^m \mid P(x) \,\}|$.

Мне интересны в основном предикаты, накладывающие условия вида "в слове встречается $n_i$ раз определенное подслово $A_i$, $n_i \geqslant 0,\; i = \overline{1,k}$". Как к этому подступиться? Подскажите какие-нибудь общие соображения, литературу?

[VAL]

Joker_vD в сообщении #414314 писал(а):

Мне интересны в основном предикаты, накладывающие условия вида "в слове встречается $n_i$ раз определенное подслово $A_i$, $n_i \geqslant 0,\; i = \overline{1,k}$". Как к этому подступиться? Подскажите какие-нибудь общие соображения, литературу?

Начните с простых ситуаций, когда все интересующие нас подслова "хорошие". К "плохим" отнесем ситуации, когда какое-то интересующее нас подслово является частью другого, возникает при приписывании других подслов и т.п.
Например, подслово abab будет плохим, поскольку в сочетании ababab встречается, но не укладывается два раза. А подслова abc и fbe, в ситуации когда других интересующих нас подслов нет - хорошие.

Если плохих подслов нет, задача решается тривиально.

Нет. Погорячился. Даже в этом случае, все равно не так уж тривиально