комбинаторика

Добавлено: Чт Фев 03, 2011 12:30 pm

Нужно найти количество возможных перестановок для множества, имея правила следования элементов.
Пример.
1) Задача:
имеем множество { a,b,c,d } и правила к нему { a>b, c>d }.
Решение:
количество возможных перестановок 4!=24,
правило a>b "отсекает" половину возможных перестановок 24/2=12 (перестановок),
правило c>d "отсекает" оставшеюся часть 12/2=6(перестановок).
Ответ: 6 перестановок.
2) Задача:
имеем множество { a,b,c,d,e } и правила к нему { a>b, b>c, c>d }.
Решение:
количество возможных перестановок 5!=120,
правило a>b "отсекает" половину возможных перестановок 1/2, 120*(1/2)=60(перестановок),
правило b>c "отсекает" 1/3 от оставшихся перестановок 60*(1/3)=20 (перестановок),
правило c>d "отсекает" 1/4 от оставшихся перестановок 20*(1/4)=5 (перестановок).
Ответ: 5 перестановок.

Вывод:
для правил которые не содержат одинаковых элементов { a>b, c>d, e>f } происходит деление на 2 для
каждого правила (задача №1),
для правил которые имеют вид { a>b, b>c, c>d, d>e } происходит деление на 2, 3, 4, 5 и т.д. (задача №2),
для правил которые имеют вид { a>b, a>c, a>d, a>e } происходит умножение на дробь 1/2, 2/3, 3/4, 4/5 и т.д.

Это все то, что я смог найти экспериментальным путем. Совершенно не понятно, какая закономерноть для "смешенных правил" { a>b, a>c, e<d>e, b>e .. } множества могут иметь разное кол. элементов и правила могут быть самые разные. причем правило { a>b, b>c } можно раскрыть как { a>b, a>c, b>c }.

Помогите плиз. или тыкнети меня в литературу, где возможно найти ответ.
Искал по википедий нашел такие понятия как: "частично упорядоченное множество", "гуппы", "решетки".
Но что начать изучать и даст ли это ответ на мою задачу, я не знаю(

Заранее Спасибо.