Дискретка (Жаркова)
.pdf
Практическое занятие №1 по лекции 2 Тема: «Элементы комбинаторики»
(часть 1, продолжение на занятии № 3, но Д.З. сделать к занятию № 2)
Обсуждаемые понятия, утверждения, алгоритмы
Выборки. Использование правила произведения и правила суммы для подсчета числа выборок. Сочетания и размещения без повторений и с повторениями. Перестановки. Формулы подсчета числа сочетаний, размещений, перестановок.
Учебная литература, используемая на занятии
1.Олейник Т.А. Основы дискретной математики: теория и практика. – М.: МИЭТ, 2010
2.Клюшин А.В., Кожухов И.Б., Олейник Т.А. Сборник задач по дискретной математике.
–М.: МИЭТ, 2008.
Теоретические сведения
Теоретические сведения и примеры решения типовых задач базового уровня приведены в Л1, § 1.2.
Практика под руководством педагога
Обязательные задачи
Правило суммы
На тарелке лежат пять яблок и три груши, сколькими способами можно выбрать
1фрукт?
Аесли мы будем брать по два фрукта, применимо ли правило суммы?
Правило произведения.
1.Турист планирует побывать в трех городах А, В и С. Из А в В можно добраться пятью маршрутами, а из В в С – тремя. Сколькими способами турист может составить маршрут от города А до города С через В?
Использование правила произведения и правила суммы для подсчета числа выборок. Сочетания и размещения без повторений и с повторениями. Перестановки. Формулы подсчета числа сочетаний, размещений, перестановок
2.Из группы в 15 человек должны быть выделены на субботник бригадир и 4 члена бригады. Сколькими способами это можно сделать?
3.Ольга Ивановна, отправляясь на курорт на 7 дней, решила, что каждый день перед сном будет смотреть лирическую комедию, и скачала себе на ноутбук 10 фильмов.
а) Сколько различных наборов фильмов она может посмотреть за время отдыха? б) Сколько различных планов просмотров она может составить?
4. Сколько различных «слов» можно составить перестановкой букв в словах:
а) «вектор», |
б) «элемент», |
в) «математика». |
|
|
|
5. а) Сколькими способами можно нарисовать флаг с тремя продольными полосами одинаковой ширины, если имеются краски пяти цветов?
б) Сколькими способами можно выбрать три различные краски из пяти?
в) В магазине имеется по десять банок синего, красного, желтого, зеленого и
1
белого цвета. Сколько различных наборов из 3-х красок можно купить?
г) Сколькими способами можно покрасить кухню, дом и сарай на даче, если
имеется краска 5-и цветов и каждое здание планируется окрасить в один цвет?
6. В буфете имеются пирожные 5-ти видов.
а) Сколько различных наборов из 12 пирожных можно купить?
б) Сколькими способами могут купить по одному пирожному 12 человек,
стоящие в очереди?
7. Сколькими способами можно расставить семь различных книг на полке, если
две книги из семи – книги по геометрии и должны стоять рядом?
8. а) Сколько существует упорядоченных наборов из 0 и 1 длины 12, i-ая координата которого при любом i, i 1,2,...,12 не меньше i-ой координаты вектора
(011001000000)?
б) Пусть дан конкретный упорядоченный набор из 0 и 1 1, 2 ,... n , у которого
ровно k |
координат равны 0. Сколько существует |
упорядоченных наборов из 0 и 1 |
||
длины |
n, i-ая координата которых при любом |
i i 1,2,..., n |
не меньше |
i-ой |
|
|
|
|
|
координаты заданного набора?
Ответы: 1. 15. 2. 15015. 3. а) 120, б) 604800. 4. а) 720, б) 2520, в) 151200. 5. а) 60, б) 10, в) 35, г) 125. 6. а) 1820, б) 512 . 7. 1440. 8. а) 512, б) 2к .
Самостоятельная практика
9. а) Сколькими способами можно разместить n различных шаров по k различным коробкам, если в одну коробку можно поместить любое число шаров?
б) Сколькими способами можно разместить n различных шаров по k различным коробкам, если в одну коробку можно поместить не более одного шара? ( n k )
в) Сколькими способами можно разместить n одинаковых шаров по k различным коробкам, если в одну коробку можно поместить не более одного шара? ( n k )
г) Сколькими способами можно разместить n одинаковых шаров по k различным коробкам, если в одну коробку можно поместить любое число шаров?
Задания повышенного уровня сложности в контрольной работе формируются на основе и с использованием банка задач, приведенного в учебном пособии Олейник Т.А. «Основы дискретной математики: теория и практика. М.:МИЭТ, 2010»: Л.1. § 1.1, задачи повышенной сложности 1.1 – 1.10; § 1.2, задачи повышенной сложности 1.11 – 1.25. Для подготовки к контрольной работе № 1 рекомендуется порешать задачи из этого списка (обсуждение этих задач возможно только на консультации)
2
Домашняя работа № 1 по теме занятия 1 (по теме лекции 2 )
Элементы комбинаторики. Подсчет числа элементов конечных множеств с использованием правила суммы, правила произведения и основных комбинаторных формул.
Обязательные задачи
1.В группе 20 человек. Сколькими способами из них можно выбрать старосту, профорга и культорга?
2.Сколькими способами можно упорядочить множество 1,2,..., n так, чтобы числа 1,2,3
стояли рядом в порядке возрастания?
3.В группе 25 человек. Сколькими способами из них можно выбрать делегацию из 5 человек на конференцию?
4.Обычно наибольшее число очков на одной кости домино равно 12. Сколько костей содержала бы игра, если бы это число равнялось 18?
5.Сколькими способами на пять различных конвертов можно наклеить по одной марке, если на почте имеется 7 различных видов марок?
6.а) Сколько существует упорядоченных наборов из 0 и 1 длины n, которые одинаково читаются справа налево и слева направо?
б) Сколько существует упорядоченных наборов из 0 и 1 длины 12, i-ая координата которого при
любом i i 1,2,...,12 не больше i-ой координаты вектора (011001000000)?
в) Пусть дан конкретный упорядоченный набор из 0 и 1 1, 2 ,... n , у которого ровно k координат равны 0. Сколько существует упорядоченных наборов из 0 и 1 длины n, i-ая координата
которых при любом i i 1,2,..., n не больше i-ой координаты заданного набора?
Ответы к заданиям: 1. 6840. 2. n 2 !. 3. 53130. 4. 55. 5. 16807.
6. если n – четно, то 2n / 2 ; если n – нечетно, то 2 n / 2 1 ; б) 8; в) 2n k .
1 – 4. Л.2. 1.5 - 1.8
1.5.Имеется два свитера, четверо брюк и три пары туфель. Каким числом способов можно одеться?
1.6.Сколько существует упорядоченных последовательностей из 0 и 1 длины 5?
1.7. Пусть |
A {a b c d e} . Сколько подмножеств (включая пустое и само A) содержится в |
множестве A? |
|
1.8. Пусть |
A {a b c d e} . Сколько подмножеств из 3–х элементов содержится в множестве A? |
Ответы 1.5. 24-мя способами. 1.6. 32. 1.7. 32. 1.8. 10 .
Дополнительное задание
7*. Сколькими способами можно представить число 12 как упорядоченную сумму 4-х
неотрицательных целых чисел?
8*. Найти число способов представления целого положительного числа k как упорядоченной суммы n неотрицательных целых чисел (задача Муавра).
|
n k 1 |
||
Ответы к заданиям: 7. 455. 8. |
|
|
. |
|
|
k |
|
|
|
|
|
3
Р а зм е щ е н и е |
Сочет ание |
Размещ ени е с |
Сочет ание с |
из n элеме нт ов по k |
из n элеме нт ов по k |
повт орениям и |
повт орениям и |
|
|
из n элеме нт ов |
из n элеме нт ов по k . |
|
|
по k |
|
|
|
|
|
в ы б о р к а о б ъ е м а k и з n э л е м е н т о в |
|
||
( упо р ядо че н на я ) |
{ н е уп о р я до ч ен н ая } |
( упо р ядо че н на я |
{ н е уп о р я до ч ен н ая } |
без по в то р е н и й |
без по в то р е н и й |
) |
с по в то р е н и ям и |
|
|||
|
|
с по в то р е н и ям и |
|
Ank n(n 1)(n 2)...(n k 1) |
|
|
n! |
Сk |
|
|
|
n! |
|
|
|
|
|
Ank |
|
|
|
|
|
k |
|
k |
|
|
|
Ck |
Сk |
|
|
|
|
(n k 1)! |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
k !(n 1)! |
|
||||||||||||||||||||||||||
(n |
k)! |
|
|
|
|
|
|
k ! |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
n k 1 |
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
п у с т ь м н о ж е с т в о M с о с т о и т и з 3 - е х э л е м е н т о в : M = { 1 , 2 , 3 } |
||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
размещение с |
|
сочетание с повторениями |
||||||||||||||||||||
размещение из 3 по 2 – шесть |
|
|
сочетание из 3 по 2 – три |
повтор-ми из 3 по 2 – |
|
|
|
из 3 по 2 – шесть |
||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
девять |
|
|
|
|
неупорядоченных выборок |
|||||||||||||||||||||||||||||||||||||
упорядоченных наборов без |
|
|
неупорядоченных |
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||
|
|
|
|
упорядоченных |
|
|
|
с повторениями |
||||||||||||||||||||||||||||||||||||||||
|
повторений |
|
|
|
|
набора без повторений |
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
выборок с |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
повторениями |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
( ), (1 ,2 ) , (1 ,3 ), |
|
|
|
|
{ |
} , {1 ,2 }, {1 ,3 }, |
|
(1 ,1 ), (1 ,2 ), (1 ,3 ), |
|
|
|
{1 ,1 }, {1 ,2 }, {1 ,3 }, |
|
|
||||||||||||||||||||||||||||||||||
(2 ,1 ), ( |
) , (2 ,3 ), |
|
|
|
|
{ |
}, { |
}, {2 ,3 }, |
|
(2 ,1 ), (2 ,2 ), (2 ,3 ), |
|
|
|
|
{ |
} , {2 ,2 }, {2 ,3 }, |
|
|
||||||||||||||||||||||||||||||
(3 ,1 ), (3 ,2 ), ( ) . |
|
|
|
|
{ |
} , { |
}, |
{ |
|
|
|
} . |
|
(3 ,1 ), (3 ,2 ), (3 ,3 ) . |
|
|
|
|
{ |
} , { |
|
}, {3 ,3 } . |
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Сколькими способами |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
Сколько способов разместить 2 |
|
|
|
Сколько способов |
|
можно разместить 2 |
|
|
|
Сколькими способами |
||||||||||||||||||||||||||||||||||||||
|
|
разложить 2 одинаковых |
|
различных шара по |
|
|
|
можно разместить 2 |
||||||||||||||||||||||||||||||||||||||||
различных шара по трем |
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
шара по трем |
|
|
|
|
|
|
|
|
трем |
|
|
|
|
одинаковых шара по трем |
||||||||||||||||||||||||||||
пронумерованным ящикам, если в |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||
|
пронумерованным |
|
пронумерованным |
|
пронумерованным ящикам, |
|||||||||||||||||||||||||||||||||||||||||||
каждый ящик может попасть только |
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||
ящикам, если в каждый |
|
|
|
ящикам, если в |
|
если в каждый ящик может |
||||||||||||||||||||||||||||||||||||||||||
|
|
один шар. |
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
ящик может попасть |
|
каждый ящик может |
|
поместиться более одного |
||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
только один шар. |
|
|
поместиться более |
|
|
|
|
|
|
|
шара? |
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
одного шара. |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
К |
С |
|
|
|
|
|
|
|
|
Ш |
|
Ш |
|
|
|
|
|
|
|
|
|
|
|
К |
|
|
С |
|
|
|
|
|
|
|
|
Ш |
|
|
|
|
Ш |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
С |
К |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
С |
|
К |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
К |
С |
|
|
|
|
|
|
|
|
|
|
Ш |
|
|
Ш |
|
|
|
|
|
|
|
|
|
|
К |
|
|
С |
|
|
|
|
|
|
|
|
|
|
Ш |
|
Ш |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
С |
К |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
С |
|
|
К |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
К |
|
С |
|
|
|
|
|
|
|
Ш |
|
|
|
|
Ш |
|
|
|
|
|
|
|
К |
|
|
|
|
|
С |
|
|
|
|
|
Ш |
|
|
|
|
|
|
Ш |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
С |
|
К |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
С |
|
|
|
|
К |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
К С |
|
|
|
|
|
|
|
|
|
|
Ш Ш |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
К С |
|
|
|
|
|
|
|
|
|
|
|
|
Ш Ш |
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
К С |
|
|
|
|
|
|
|
|
|
|
|
|
Ш Ш |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Число пе рест ановок |
|
Число пе рест ановок с повт орениям и и з n эл емент ов – имеется n элементов |
||||||||||||||||||||||||||||||||||||||||||||||
|
m различных типов, и рассматриваются перестановки из всех этих элементов с точностью |
|||||||||||||||||||||||||||||||||||||||||||||||
из n элеме нт ов |
|
|||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
без повт орений |
|
|
до порядка следования однотипных элементов ki |
– количество элементов i-го типа и |
||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
k k |
k n . |
Pk1 k2 km |
|
|
|
|
n! |
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
Pn n! |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
k !k ! k ! |
|
|
|
|
|
||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
1 |
|
2 |
|
|
|
|
|
m |
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
|
|
m |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Практическое занятие №2 по лекции 1 Тема: «Множества и бинарные отношения»
Обсуждаемые понятия, утверждения, алгоритмы
Операции над множествами. Подсчет элементов конечных множеств с помощью правила суммы, формулы включений и исключений. Определение свойств бинарных отношений на множестве. Построение разбиений множеств на классы эквивалентности.
Учебная литература, используемая на занятии
1.Олейник Т.А. Основы дискретной математики: теория и практика. – М.: МИЭТ, 2010
2.Клюшин А.В., Кожухов И.Б., Олейник Т.А. Сборник задач по дискретной математике. – М.:
МИЭТ, 2008.
Теоретические сведения
Теоретические сведения и примеры решения типовых задач базового уровня приведены в Л1, § 1.1. Краткое изложение теории есть в Л2: Глава 1. § 1.1, стр. 3-4; § 1.3, стр. 7-9.
Типовые задачи семинара-тренинга
Практика под руководством педагога
№ |
Обязательные задачи |
|
|
|
|
|
|
|
Дополнительные задачи |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1. |
|
|
|
|
Множества и операции над ними |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
Л2. 1.1, 1.9 |
|
|
|
|
|
|
|
|
Л2. 1.4 |
||
|
|
|
|
|
|
|
|
|
|
||||
|
|
(1.1 – 1.4) Для следующих множеств A и B и универсального |
|
|
------------//-------------- |
|
|||||||
|
|
множества X найдите множества A B, A B, A \ B, B \ A, |
|
, |
|
. |
|
|
|
|
|||
|
|
A |
B |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
1.4. A ( 2] {4} (69] , |
|
|
|
1.1. A {2 4 68} , B {3 4 5 6 7} , X {1 23 45 6 789} . |
|
|
B [1 4) {7} (8) , X R . |
|
|||||||
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1.9. В научно–исследовательском институте работают 67 человек. |
|
|
|
||||||||
|
|
Из них 47 знают английский язык, 35 – немецкий язык и 23 – оба |
|
|
|
||||||||
|
|
языка. Сколько человек в институте не знают ни английского, ни |
|
|
|
||||||||
|
|
немецкого языка? |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|||||
2. |
|
|
|
|
Бинарные отношения на множестве |
|
|
|
|||||
|
|
|
|
|
|
||||||||
|
|
Выясните, является ли |
следующее бинарное отношение на |
|
Л2. 1.29 |
||||||||
|
|
множестве M : а) |
рефлексивным, б) симметричным, в) |
|
|
|
|||||||
|
|
антисимметричным, г) транзитивным. Будет ли отношением |
|
|
|
||||||||
|
|
эквивалентности или порядка? |
|
|
|
||||||||
|
1. |
M 0,1,2 , |
x y x2 |
y2 1 . |
|
|
|
||||||
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
2. |
M 0,1,2 , |
x 2 y x y 1. |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
3. M 1,0,1 , x 3 y x y .
Л.2. 1.25, 1.26, 1.28
1.25.Приведите пример рефлексивного, симметричного, но не транзитивного бинарного отношения на множестве из 3-х элементов.
1.26.Приведите пример рефлексивного, транзитивного, но не симметричного бинарного отношения на множестве из 3-х элементов.
(1.28 – 1.30) Выясните, является ли следующее бинарное
отношение на множестве натуральных чисел
1) рефлексивным; 2) симметричным; 3) антисимметричным;
4) транзитивным. Будет ли отношением эквивалентности или
порядка?
1.28. m n m n – четно.
------------//--------------
1.29.
m n m n – нечетно.
Самостоятельная практика
Л2. 1.10, 1.27
1.10. В научно-исследовательском институте работают 67 человек. Из них 47 знают английский язык, 35 – немецкий язык и 20 – французский язык. Далее, 23 человека знают английский и немецкий языки, 12 человек – английский и французский и 11 человек знают немецкий и французский языки. Наконец, 5 человек знают все три языка. Сколько человек в институте не знают ни одного из этих языков?
1.27. Приведите пример симметричного, транзитивного, но не рефлексивного бинарного отношения на множестве из 3-х элементов.
6
Домашняя работа № 2 по теме лекции 1
Множества и бинарные отношения. Операции над множествами. Подсчет элементов конечных множеств с помощью правила суммы, формулы включений и исключений. Определение свойств бинарных отношений на множестве. Построение разбиений множеств на классы эквивалентности.
Обязательные задачи
1 – 3: Л-2: № 1.2. 1.3, 1.30.
(1.1 – 1.4) Для следующих множеств A и B и универсального множества X найдите множества A B, A B, A \ B, B \ A, A, B .
1.2. A {1 3 5 7 9} , B {23 4 6} , X {1 23 45 6 78 9} .
1.3. A (1] [34] [5), B (1 2) [45] (6), X R .
(1.28 – 1.30) Выясните, является ли следующее бинарное отношение на множестве
натуральных чисел 1) рефлексивным; 2) симметричным; 3) антисимметричным; 4)
транзитивным. Будет ли отношением эквивалентности или порядка?
1.30. m n m n – четно.
(4 – 6) Выясните, является ли следующее бинарное отношение на множестве M : а) рефлексивным, б) симметричным, в) антисимметричным, г) транзитивным. Будет ли отношением эквивалентности или порядка?
4. M N , x y x y 1. 5. M N , x y x y . 6. M N , x y y x 1 .
7. Пусть на множестве A 1, 2,3, 4,5,6,7 определено бинарное отношение : x y ( x y неотрицательно и делится нацело на 2). Показать, что есть отношение порядка на A .
7
|
|
|
|
Банк дополнительных задач и задач на дом |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1. |
Выясните, |
является ли |
бинарное |
отношение |
: |
x y ( x делит |
y ), |
|
|
|
|||
|
определенное на множестве |
натуральных чисел: |
|
|
|
|
|
|
|
||||
|
а) рефлексивным, б) симметричным, в) антисимметричным, г) транзитивным. |
|
|
|
|||||||||
|
Будет ли отношением эквивалентности или порядка? |
|
|
|
|
|
|
||||||
|
|
|
|
|
|
||||||||
|
2. Пусть на множестве натуральных чисел определено бинарное отношение |
|
|
|
|||||||||
|
: x y ( x делит y или x y ). Показать, что есть отношение линейного |
|
|
|
|
|
|||||||
|
порядка. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Л.2. 1.21 – 1.24 |
|
|
|
|
|
|
|
|
|
Кусок, |
|
|
|
1.21. Сколько |
существует |
бинаpных |
отношений |
на |
множестве из |
3-х |
|
|
перенесенный |
|
||
|
элементов? |
|
|
|
|
|
|
|
|
|
из |
|
|
|
|
|
|
|
|
|
|
|
|
комбинаторики |
|
||
|
1.22. Сколько существует pефлексивных бинаpных отношений на множестве |
|
|
|
|||||||||
|
|
|
|
|
|||||||||
|
из 3-х элементов? |
|
|
|
|
|
|
|
|
|
|
||
|
1.23. Сколько существует симметpичных бинаpных отношений на множестве |
|
|
|
|
||||||||
|
из 3-х элементов? |
|
|
|
|
|
|
|
|
|
|
||
|
1.24. Сколько существует антисимметpичных бинаpных отношений на |
|
|
|
|
||||||||
|
множестве из 3-х элементов? |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ответы |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1.21. 512. |
1.22. 64. |
1.23. 64. |
1.24. 216. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
Задания повышенного уровня сложности в контрольной работе формируются |
|
|
|
||||||||
|
на основе и с использованием банка задач, приведенного в учебном пособии |
|
|
|
|||||||||
|
Олейник Т.А. «Основы дискретной математики: теория и практика. М.:МИЭТ, 2010»: |
|
|
|
|||||||||
|
Л.1. |
§ 1.1, задачи повышенной сложности 1.1 – 1.10; § 1.2, задачи повышенной |
|
|
|
||||||||
|
сложности 1.11 – 1.25. Для подготовки к контрольной работе № 1 рекомендуется |
|
|
|
|||||||||
|
порешать задачи из этого списка (обсуждение этих задач возможно только на |
|
|
|
|||||||||
|
консультации) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8
Практическое занятие №3 по лекциям 1 и 2 Тема: «Элементы комбинаторики» (продолжение)
Тема: «Множества и бинарные отношения» (обсуждение)
Обсуждаемые понятия, утверждения, алгоритмы
Приемы доказательства комбинаторных тождеств. Бином Ньютона. Биномиальные коэффициенты. Треугольник Паскаля.
Учебная литература, используемая на занятии
1.Олейник Т.А. Основы дискретной математики: теория и практика. – М.: МИЭТ, 2010
2.Клюшин А.В., Кожухов И.Б., Олейник Т.А. Сборник задач по дискретной математике. – М.: МИЭТ,
2008.
Теоретические сведения
Теоретические сведения и примеры решения типовых задач базового уровня приведены в Л1, § 1.2.
Практика под руководством педагога
Отработка первых двух занятий Обсуждение первой части БДЗ. Подготовка к КР № 1
Обязательные задачи
1.Сколькими способами можно представить число 12 как упорядоченную сумму 4-х
неотрицательных целых чисел?
2.Найти число способов представления целого положительного числа k как упорядоченной суммы n неотрицательных целых чисел (задача Муавра).
|
n k 1 |
||
Ответы к заданиям: 1. 455. 2. |
|
|
. |
|
|
k |
|
|
|
|
|
3. Сколько непустых подмножеств множества 1,2,3,...16, :
а) содержат только четные числа; б) содержат, по крайней мере, одно нечетное число?
Ответ. а) 255; б) 65280.
4. Доказать комбинаторные тождества:
а) n k n 1 k k n 1 k 1 ; |
обозначение (n)k Ank |
и |
n |
Сnk |
|
||||
|
|
|
k |
|
б) |
n m |
k n |
m |
(указание: использовать метод производящих |
|||
|
|
|
|
|
|
||
|
|
|
|
|
|
||
|
|
k |
|
i 0 i k i |
|
||
функций).
9
Пусть задана последовательность комбинаторных |
чисел { ai } и |
последовательность функций { i (x) } ( i = 0, 1, |
… }. |
Определение. Производящей функцией называется следующая функция
|
|
|
|
|
|
F(x) = ai i (x) . |
|
|
|
i 0 |
|
Пример. a Ci |
, |
( i = 0, 1, …, n ), |
(x) xi . |
i n |
|
|
i |
В этом случае в качестве производящей функции будет бином Ньютона, т.е.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F(x) = ( 1 + x ) |
= Cni xi . |
|
|
|
|
|
|
|
|||
|
|
|
|
|
i 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
5. Доказать комбинаторные тождества: |
|
|
|
|
|
|
|
|
|
||||
|
а) n k n n 1 k 1 ; |
б) n k |
n k 1 n k 1 ; обозначение: |
(n)k Ank |
|
|||||||||
|
Доказать комбинаторное |
тождество |
n |
n 1 |
n 2 |
|
|
k 1 |
|
|||||
|
|
|
|
|
|
|
... |
. |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
k |
k 1 |
k 1 |
|
|
k 1 |
|
|||
|
обозначение: |
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
Сnk |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
k |
|
|
|
|
|
|
|
|
|
|
|
|
Домашняя работа № 3 + БДЗ
Доказательство комбинаторных тождеств.
Обязательные задачи
Дополнительное задание на дом.
1. |
Доказать комбинаторные тождества: |
|
|
а) n k n n 1 k 1 ; |
б) n k n k 1 n k 1 ; обозначение: |
(n)k Ank |
|
|
|
|
|
2. |
БДЗ к 5-му занятию |
|
|
Подготовка к КР № 1 состоится на 4-ом занятии |
|
||
Задания повышенного уровня сложности в контрольной работе формируются на основе и с использованием банка задач, приведенного в учебном пособии Олейник Т.А. «Основы дискретной математики: теория и практика. М.:МИЭТ, 2010»: Л.1. § 1.1, задачи повышенной сложности 1.1 – 1.10; § 1.2, задачи повышенной сложности 1.11 – 1.25. Для подготовки к контрольной работе № 1 рекомендуется порешать задачи из этого списка (обсуждение этих задач возможно только на консультации)
10