Помощь в математике
 FAQ  •  Поиск  •  Пользователи  •  Группы   •  Регистрация  •  Профиль  •  Войти и проверить личные сообщения  •  Вход
 комбинаторика Следующая тема
Предыдущая тема
Начать новую темуОтветить на тему
Автор Сообщение
Arthur88



Зарегистрирован: 03.02.2011
Сообщения: 1

СообщениеДобавлено: Чт Фев 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 }.

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

Заранее Спасибо.
Посмотреть профильОтправить личное сообщение

Показать сообщения:      
Начать новую темуОтветить на тему


 Перейти:   



Следующая тема
Предыдущая тема
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах


Часовой пояс: GMT + 2
Powered by phpBB © 2001, 2002 phpBB Group