2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Число слов с ограничениями на повторения букв
Сообщение16.12.2009, 09:04 
Прошу совета по комбинаторике.

Задача. Найти число слов длины $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!}$.

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

 
 
 
 Re: Число слов с ограничениями на повторения букв
Сообщение24.12.2009, 02:02 
Аватара пользователя
Найти число слов можно без всякого перебора.

Можно, например, воспользовать принципом включений-исключений. А именно, посчитать количество слов длины $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.$

 
 
 
 Re: Число слов с ограничениями на повторения букв
Сообщение28.12.2009, 12:13 
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$, о чём я мог только мечтать. :D Спасибо!

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

 
 
 
 Re: Число слов с ограничениями на повторения букв
Сообщение28.12.2009, 18:21 
Аватара пользователя
Егор в сообщении #275882 писал(а):
Первый совет, насчёт включения-исключения, я не понял. Не могу сообразить простой формулы даже для числа элементов множества $P_1$.

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

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

 
 
 
 Re: Число слов с ограничениями на повторения букв
Сообщение13.04.2010, 02:53 
Аватара пользователя
romanz в сообщении #308704 писал(а):
См.:Заторский Р.А. Подсчет $m$-подмультимножеств через их вторичные спецификации.//Комбинаторный анализ. Вып. 7, Под ред. К.А. Рыбникова. М. МГУ, 1986, с 136-145.

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

 
 
 
 Re: Число слов с ограничениями на повторения букв
Сообщение15.04.2010, 16:22 
К сожалению, нет. Но кое-что можно переслать по электр. адр.

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group