Число слов с ограничениями на повторения букв

[Егор]

Прошу совета по комбинаторике.

Задача. Найти число слов длины $L$, составленных из букв алфавита $\{1,\ldots,n\}$, причём каждую букву $k$ можно использовать не более $a_k$ раз ($1\le k\le n$).

Например, посчитать слова (цепочки букв) длины 2, которые можно составить из букв слова "МАТЕМАТИКА" (букву К можно использовать только 1 раз, а букву М два раза).

Тривиальный переборный алгоритм:
Перебирать все мультиподмножества заданного мультимножества, имеющие заданную мощность $L$, и суммировать число их перестановок ("перестановок с повторениями", ибо мультимножества).
Другими словами, перебирать неотрицательные кортежи $(b_1,\ldots,b_n)$, такие что $(b_1,\ldots,b_n)\le(a_1,\ldots,a_n)$ и $b_1+\dots+b_n=L$, и суммировать величины $\displaystyle\frac{L!}{b_1!\cdots b_n!}$.

Как называется эта задача? Есть ли эффективный способ решения (алгоритм полиномиальной сложности)?

[maxal]

Найти число слов можно без всякого перебора.

Можно, например, воспользовать принципом включений-исключений. А именно, посчитать количество слов длины $L$, не удовлетворяющих ни одному из свойств $P_1, P_2, \dots, P_n$, где:
$P_k =$ "количество букв $k$ в слове больше $a_k$".

Можно также рассмотреть экспоненциальную производящую функцию:

$$\prod_{k=1}^n \sum_{j=1}^{a_k} \frac{x^j}{j!}$$

и вычислить в ней коэффициент при $x^L.$

[Егор]

maxal, спасибо за решение!

Думаю, что понял второй совет. Действительно, коэффициент при $x^L$ в этой производящей функции как раз равен нужной мне сумме

$$\sum_{\substack{(b_1,\ldots,b_n)\le(a_1,\ldots,a_n)\\b_1+\dots+b_n=L}}\frac{1}{b_1!\cdot\dots\cdot b_n!},$$

но вычисляется без перебора, просто перемножением многочленов! То есть формула работает за полиномиальное время от числового параметра $a_1+\ldots+a_n$, о чём я мог только мечтать. Спасибо!

Первый совет, насчёт включения-исключения, я не понял. Не могу сообразить простой формулы даже для числа элементов множества $P_1$.

[maxal]

Егор в сообщении #275882 писал(а):

Первый совет, насчёт включения-исключения, я не понял. Не могу сообразить простой формулы даже для числа элементов множества $P_1$.

Да, похоже, что и там без производящих функций не обойтись. Но использование включения-исключения теряет смысл в виду наличия экспоненциальной производящей функции непосредственно для искомой величины.

[romanz]

Решить эту задачу можно с помощью общей формулы для числа всех $m$-подмультимножеств мультимножества $a_1^{k_1}a_2^{k_2}\ldots a_n^{k_n}$.
См.:Заторский Р.А. Подсчет $m$-подмультимножеств через их вторичные спецификации.//Комбинаторный анализ. Вып. 7, Под ред. К.А. Рыбникова. М. МГУ, 1986, с 136-145.

[maxal]

romanz в сообщении #308704 писал(а):

См.:Заторский Р.А. Подсчет $m$-подмультимножеств через их вторичные спецификации.//Комбинаторный анализ. Вып. 7, Под ред. К.А. Рыбникова. М. МГУ, 1986, с 136-145.

А нет ли этой статьи в электронном виде?

[romanz]

К сожалению, нет. Но кое-что можно переслать по электр. адр.