Тема 5.5. Примеры комбинаторных задач

Пример 5.4:человек садятся за круглый стол. Два размещения по местам будем считать совпадающими, если каждый человек имеет одних и тех же соседей в обоих случаях. Сколько существует способов сесть за стол.

Решение:Общее число перестановок равно, но отношение соседства сохраняется при циклических перестановках (повороте) ихдля каждого различного размещения и при симметричном отображении (их 2). Следовательно.

Пример 5.5:Из колоды в 52 карты вынули 10 карт. В скольких случаях среди этих карт окажется а) хотя бы один туз; б) ровно один туз; в) не менее двух тузов; г) ровно два туза.

Решение:

а) Существует способов взять 10 карт из 52. При этом вслучаях в этой выборке не окажется ни одного туза. Следовательно

б)

в)

г)

Пример 5.6:Сколько чиселв первой сотне натуральных чисел не делится ни на одно из чисел 2,3,5.?

Решение:В этом случае. Пустьподмножества, элементы которых делятся соответственно на 2,3,5. Тогда

,,

,,

где - целая часть числа. Воспользовавшись формулой включения исключения приполучаем.

Раздел 6. Соответствие, отношение, отображение Тема 6.1. Понятие кортежа. Декартово произведение множеств

Определение:Упорядоченный набор, конечная последовательность каких-либо объектов, внешне связанных определённым положением, которое они занимают в данной совокупности объектов, называется упорядоченным множеством иликортежем.

Объекты, входящие в кортеж называются компонентами.

Число компонент кортежа называется его длиной. В отличие от множества в кортеже могут быть и одинаковые компоненты, и порядок расположения элементов важен.

Пример 6.1:можно как кортеж рассматривать буквы в слове, слова в фразе, абзацы в тексте.

Определение:Декартовым произведениемдвух непустых множеств и называется множество , состоящее из всех упорядоченных пар,

Замечание:Если одно из множеств пустое, то понятие декартова произведения множеств не определено.

Пример 6.2:

Обратим внимание, что речь идёт об упорядоченных парах, т.е. в отличие от множеств .

Примером декартова произведения является система географических координат: для любой географической точки её место на карте определяет пара чисел, обозначающие широту и долготу.

Декартово произведение множества самого на себя называется степенью множества. Так, привычная система координат на плоскости есть не что иное, как декартово произведение множества вещественных чисел само на себя, или квадрат множества вещественных чисел.

и любая точка на плоскости задаётся .

Свойства декартового произведения множеств:

Тема 6.2. Определения и свойства

Рассмотрим два множества и. Элементы этих множеств могут каким-либо образом сопоставляться друг другу, образуя пары. Если задан способ такого сопоставления, то говорят что между множествами установлено соответствие. При этом совершенно необязательно, чтобы в сопоставлении участвовали все элементы множестви.

Определение:Соответствиеммежду множествами и называется любое подмножество – декартова произведения множеств.

Пример 6.3:Рассмотрим два множества:

А={Гагарин, Дунаевский, Носов, Рахманинов}

В={1900,1901,….2000} – годы 20 века.

Установим соответствие между этими двумя множествами, например, человек – год рождения.

Г = {(Гагарин, 1934);(Дунаевский, 1900);(Носов,1908)}

(Рахманинов, 1973) – естественно не вошёл в множество.

Другим примером соответствия, установленного между этими множествами, может быть такое: человек – год смерти.

Г={(Гагарин,1968);(Дунаевский,1955);(Носов,1986);(Рахманинов,1943)}

Определение:Множество , такое что, называетсяобластью определения соответствия .

Определение:Множество , такое что, называетсяобластью значений соответствия .

Таким образом, соответствие можно задать ООС, ОЗС и законом, определяющим соответствие.

Определение:Есликаждомуэлементу множества ставится в соответствие один или более элемент множества , то говорят что заданоотображениемножествана множество .

В ранее приведённом примере соответствие человек – год рождения – не является отображением (т.к. не каждому элементу множества ставится в соответствие элемент из множества ), а соответствие (человек, год смерти) – является отображением.

Определение:Функциейназывается такое отображение множества на множество , когда каждому элементу множества ставится в соответствие единственный элемент множества .

Замечание:При этом множества и могут совпадать.

Определение:Если область определения отображения и область значения отображения совпадают, то отображение называетсяотношением.

Отметим некоторые возможные свойства отношений, пусть на множестве задано отношение :

Отношение называетсярефлексивным, если – истинно, т.е. существует отношение элементак.

Отношение называетсяантирефлексивным, если – ложно, т.е. не существует отношенияк.

Отношение называетсясимметричным, еслииз существования отношения следует существования отношения .

Отношение называетсяантисимметричным, если, таких что существуют отношения , следует .

Отношение называетсянесимметричным, еслитаких, что существует отношение, следует, что не существует отношение .

Отношение называетсятранзитивным, еслииз существования отношенияи , следует существование отношения.

Пример 6.4:Алфавит русского языка, как и любого другого языка – это упорядоченное множество букв. Назовём отношение между элементами этого множества отношением предшествования и обозначим его значком.

Мы знаем, что и т.д.

Укажем свойства этого отношения:

• – ложно, т.к. ни одна из букв не предшествует сама себе. Т.е. отношение предшествования антирефлексивно.

• если– истинно, то– ложно. Т.е. отношение предшествования несимметрично.

• Если- истинно и- истинно, то- истинно. Следовательно, отношение транзитивно.

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

Пример 6.5:Можно ввести на множестве из предыдущего примера отношение «непосредственно предшествует», основываясь на уже существующем и исследованном нами отношении «предшествует». Будем говорить, чтонепосредственно предшествует, еслии

Упражнение:определите свойства этого отношения самостоятельно.