Материал: Методические указания по выполнению лабораторных работ по дисциплине Дискретная математика для студентов специальности 230101. Леденева Т.М., Недикова Т.Н

д) , где ,

9. Установите, является ли каждое из перечисленных ниже отношений на множестве эквивалентностью. Для каждого отношения эквивалентности постройте классы эквивалентности.

а) и есть отношение, заданное условием , если ,

б) - множество упорядоченных пар целых чисел и , если ,

в) и , если ,

г) и , если .

10. Какое из приведенных ниже отношений является отношением частичного порядка на ?

а) ,

б) ,

в) ,

г) .

11. Являются ли следующие отношения частичным порядком?

а) ,

б) на множестве людей определено условием: , если и являются братом и сестрой,

в) на множестве всех упорядоченных пар положительных целых чисел определено условием: , если , и если , то .

12. Постройте диаграммы Гессе для следующих частично упорядоченных множеств :

а) , ,

б) , ,

в) и , если делит нацело,

г) , где и , если делит нацело, если , то делит нацело,

д) - множество положительных целых чисел, которые делят 27 нацело, и , если делит нацело.

13. Для каждого частичного порядка из предыдущего упражнения перечислите элементы:

а) не сравнимые с , б) не сравнимые с ,

в) не сравнимые с , г) не сравнимые с .

14. Диаграмма Гессе частичного порядка на множестве показана на рис 2.

Рис. 2.

Перечислите элементы отношения и найдите минимальный и максимальный элементы частично упорядоченного множества .

15. Для данного отношения , заданного на множестве выполните следующие действия:

а) постройте для соответствующий граф ;

б) достройте до отношения эквивалентности и укажите соответствующее фактор-множество;

в) достройте до отношения частичного порядка, укажите максимальные и минимальные элементы, а также несравнимые элементы;

г) достройте до отношения линейного порядка, укажите наибольший и наименьший элементы;

д) достройте до отношения строгого порядка.

Замечание. Отношение достраивается с помощью введения минимально необходимого числа дополнительных ребер.

Элементы комбинаторики

Ключевые слова: правило умножения, правило суммы, метод включений и исключений, перестановки с повторениями и без повторений, размещения с повторениями и без повторений, сочетания с повторениями и без повторений

Задача 4.1. Сколько четырехзначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, если:

а) ни одна из цифр не повторяется более одного раза;

б) цифры могут повторяться.

Решение. Каждое четырехзначное число, по сути, представляется как упорядоченный набор из четырех цифр, принадлежащий декартовому произведению множеств , где - множество цифр, которые могут занимать данное место в четырехзначном числе. Мощность декартова произведения определяет количество четырехзначных чисел, удовлетворяющих данному условию.

а) Так как ни одна из цифр не может повторяться более одного раза, то , , , , откуда .

б) Если цифры могут повторяться, то на каждом месте может стоять любая из цифр, следовательно, и .

Задача 4.2. Сколько нечетных чисел находится между и ?

Решение. Пусть - множество нечетных чисел между и , для - подмножество такое, что является последней цифрой его элемента. Для каждого существует вариантов выбора первой цифры и - второй, так что каждое множество содержит элементов. Так как , то

.

Задача 4.3. Из колоды, содержащей 52 карты, вынули 10 карт. Сколькими различными способами это можно сделать? В скольких случаях среди этих карт окажется хотя бы один туз? В скольких случаях окажется ровно один туз? В скольких случаях ровно 4 туза?

Решение. Выбор 10 карт из колоды можно осуществить способами. Определим, в скольких случаях среди выбранных карт нет ни одного туза, тогда во всех остальных случаях будет хотя бы один туз. Но если среди выбранных карт нет ни одного туза, то выбор совершался не из 52, а из 48 карт (всех карт кроме тузов), а потому число таких выборов равно . Следовательно, хотя бы один туз будет в случаях.

Чтобы найти, в скольких случаях будет ровно один туз, разобьем операцию выбора карт на две: сначала выбирают из четырех тузов один туз - это можно сделать способами, а потом из оставшихся 48 карт выберем 9, что можно сделать способами. В соответствии с комбинаторным принципом умножения получаем, что существует способов.

Наконец выбор, содержащий четыре туза, можно осуществить способами - надо взять 4 туза и выбрать еще 6 карт из 48.

Задача 4.4. Сколько целых неотрицательных решений имеет уравнение ?

Решение. Заметим, что если - целые неотрицательные числа, такие что , то можно составить сочетания из элементов по с повторениями среди которых элементов первого типа, элементов второго типа, ..., элементов -го типа. С другой стороны, имеем сочетание из элементов по , получим решение уравнения в целых неотрицательных числах. Следовательно, между множеством всех сочетаний из элементов по с повторениями и множеством всех целых неотрицательных решений уравнения существует взаимно однозначное соответствие, поэтому число решений определяется формулой .