Сколько слов можно составить из исходного? формула

[vovs]

Здравствуйте, уважаемые!

Подскажите по какой формуле можно подсчитать количество разных слов, которые можно составить из некоего изходного.

Для исходного слова, в котором НЕТ повторяющихся букв формула известна - сумма размещений:
например:
слово "стол"
Количество слов, которые можно составить из исходного считаем так:
А(4 из 4) + А(3 из 4) + А(2 из 4) + А(1 из 4) = 64 слов

Буквы также считаются словами.
с, ст, сто, стол -- это все примеры результатов. Причем "ст" не равно "тс"

У меня не получается вычислить количество слов, которые можно составить из исходного, в котором есть ПОВТОРЯЮЩИЕСЯ буквы.

Так, например, из исходного слова "хата" можно выбрать 34 разных слов(или комбинаций букв так как многие из этих слов никакого смысла не несут).

Какая формула дает это число 34?

Формула интересна для общего случая...

Формула интересна для общего случая...

Сомневаюсь что есть какая-то простая красивая формула.

Можно посчитать динамическим программированием. Это будет двухмерная таблица + формулы для рассчета её ячеек из других. Надо?

[maxal]

Проще дать ответ в терминах производящих функций.

Пусть у нас имеется n1 букв 1-го типа (например, "а"), n2 букв второго типа (например, "б"), ..., nk букв k-го типа.

Тогда ответом будет коэффициент при x^n, где n=n1+n2+...+nk, в произведении:

(1 + x/1! + x^2/2! + ... + x^{n1}/n1!) *
* (1 + x/1! + x^2/2! + ... + x^{n2}/n2!) *
...
* (1 + x/1! + x^2/2! + ... + x^{nk}/nk!) *
* (n! + (n-1)!x + ... + x^(n-1))

Например, для слова "стол" имеем k=4, n1=n2=n3=n4=1, n=4, и поэтому ответом является коэффициент при x^4 в
(1+x)^4 * (24+6x+2x^2+x^3),
который равен 64.

А для слова "хата" имеем k=3, n1=2, n2=n3=1, n=4, и поэтому ответом является коэффициент при x^4 в
(1+x+x^2/2) * (1+x)^2 * (24+6x+2x^2+x^3),
который равен 34.

сколько слов в слове формулировка