Количество последовательностей букв из слова.

[svloyso]

Здравствуйте.
Возникла у меня следующая задача: дано слово длины $n$, при том, что некоторые буквы этого слова повторяются, необходимо найти количество последовательностей длины меньшей или равной $n$, которые можно составить из букв этого слова.

То есть задача сводится по-сути к следующей: дано $m$ множеств, в $i$-м множестве $k_i$ элементов, необходимо посчитать количество $n$-элементных выборок из этих множеств. Для $n<k_i$ при любом $i$ выборки сводятся к числу сочетаний с повторениями, при $n=\sum\limits_{i=0}^m k_i$ выборка - это мультиномиальный коэфициент $\binom n{k_1,k_2,\ldots,k_m}$, но вот для остальных $n$ я не могу вывести единую формулу.

Надеюсь, вы мне подскажете, с какой стороны за неё браться. Спасибо.

[svloyso]

Вопрос всё еще актуален, господа.

[Cash]

Если ничего не путаю, то это количество решений неравенства
при $\sum x_i \leq n, \; x_i \leq a_i$

Если вам не нужна формула, а нужен алгоритм, то легко составить рекуррентное уравнение (берете первую переменную и проходитесь по всем его возможным значениям). Тогда вычисляется или рекурсией (если тупо) или динамическим программированием.