Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 03.09.2010, 22:08
Новичок

Отправить личное сообщение для vovs Посмотреть профиль Найти все сообщения от vovs
 
Регистрация: 10.12.2007
Адрес: Черкассы, Украина
Сообщений: 6

Сколько слов можно составить из исходного? формула
Здравствуйте, уважаемые!

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

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

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

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

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

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

Формула интересна для общего случая...
  #2  
Старый 03.09.2010, 23:21
гость

 
Сообщений: n/a

Цитата:
Формула интересна для общего случая...
Сомневаюсь что есть какая-то простая красивая формула.

Можно посчитать динамическим программированием. Это будет двухмерная таблица + формулы для рассчета её ячеек из других. Надо?
  #3  
Старый 04.09.2010, 09:49
Пользователь

Отправить личное сообщение для maxal Посмотреть профиль Найти все сообщения от maxal
 
Регистрация: 28.11.2006
Сообщений: 68

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

Пусть у нас имеется 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.
  #4  
Старый 23.11.2010, 19:31
гость

 
Сообщений: n/a

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Формула размещений с фиксированным разнообразием malira Математические алгоритмы (другое) 3 03.09.2010 13:01
Интерполяционная формула Уиттекера-Шеннона TerraDon Математические алгоритмы (другое) 1 13.05.2010 06:27
Перебор комбинаций слов timugatu Математические алгоритмы (другое) 4 29.11.2009 18:55
Формула Мезона (Мэйсона) Denis_ya Графы 0 19.05.2009 16:38
помогите составить рекуррентное ур-ие lavan Математические алгоритмы (другое) 2 24.04.2009 08:57