Помогите решить задачу по комбинаторике.

Сообщение №8738 от nik 05 февраля 2002 г. 04:15
Тема: Помогите решить задачу по комбинаторике.

Помогите решить задачу по комбинаторике.
Комбинаторная задача подсчета количества перестановок с повторениями.
Задано несколько различных наборов однотипных элементов с повторениями.
Например. 1-й набор - 111(11)(11)(111) - состоит из 6 элементов одного типа (единиц). 3-единицы единичные (т.е. каждая , 2- двоичные и 1 – троичная.
2-й набор состоит из 7 элементов второго типа (например двоек) – 2222(222)(222)(22) – 4 единичных двойки, 2-троичные двойки и 1 –двоичная двойка.
Могут быть добавлены наборы элементов 3-го, и n-го типа.
Необходимо подсчитать количество всевозможных перестановок между элементами всех типов при условии, что 2 любых элемента одного типа не могут находиться рядом.(Например 1(11) или (11)(111) недопустимая перестановка). (В примерах выше также показаны недопустимые перестановки. Они служат только для показа набора).
Пример допустимого сочетания. (22)(1)(22)(1)(2)(1)(2)(11)(2)(11)(2)(111)(222)
В этом примере все элементы первого типа (единицы) разделены двойками. Также нет соседних элементов 2 –го типа (двоек).Все они разделены единицами.(т.е. элементами другого типа).
Количество перестановок одного типа можно подсчитать по известной формуле перестановок с повторениями
К!
------------------------------
К(1)! * К(2)! * К(n)! Где К! = К(1) + К(2) + К(n)

Но количество перестановок между всеми элементами (при вышеприведенном условии) я найти не могу.
Могут встречаться условия, где колл. элементов 1-го типа значительно меньше колл. Элементов 2-го типа.
Например. 1111(11)(111) – 6 элементов 1-го типа.
22(22) – всего 3 элемента 2-го типа.
Естественно, что при таком наборе невозможно расположить единицы и двойки между собой таким образом, чтобы 2 единицы не находились рядом. (т.к. при 6 элементах единиц между ними должны располагаться минимум 5 элементов 2-го типа для соблюдения условия). Но при таких условиях в условия задачи обязательно будут включены наборы других типов. Например набор 33(33)(333). (4 элемента).Тогда 3 элемента из двоек плюс 4 элемента иэ троек равно 7 и все элементы одного типа будут разделены элементами другого типа.
Возможная перестановка -- (2)(1)(2)(1)(3)(1)(3)(1)(22)(11)(33)(111)(333)
Иными словами всегда будет выполняться начальное условие достаточного количества элементов разных типов для перемеживания таким образом, чтобы 2 элемента 1-го типа не находились рядом.
Необходимо узнать количество всевозможных перестановок.
Вот первые конкретные условия.
1-й набор из единиц. 1 – 8 (1)
2 – 4 (11)
3 – 2 (111)
4 – 1 (1111)
8 единичых единиц, 4-двоичных , 2 троичных и одна из 4 единиц подряд.
Всего 8+4+2+1=15 элементов.
2-й набор из двоек. 1 - 9 (2)
2 - 2 (22)
9 единичных двоек
2 двоичные двойки. Всего 9+2=11 элементов.
3-й набор - 6 троек.
4-й набор - 3 четверки.
5-й набор - 1 пятерка.
6-й набор - 1 шестерка.
7-й набор - 1 семерка.
Суммарный набор 15+11+6+3+1+1+1=38 элементов.
Необходимо узнать полное количество всевозможных перестановок из 38 элементов без соседствующих элементов одного типа
Если эта задача относится к классическим задачам по комбинаторике, то пожалуйста помогите с алгоритмом подсчета. Если это очень сложная задача, то при возможности ее решения сообщите по e-mail контактную информацию для оплаты ее решения. Заранее большое спасибо.
bovin-nik@yandex.ru



Отклики на это сообщение:

Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100