Разделы презентаций


Элементы теории множеств. Комбинаторика

Содержание

Литература и интернет - ресурсыДорофеев Г.В., Суворова С.Б., Бунимович Е.А., Кузнецова Л.В., Минаева С.С. Математика. Алгебра. Функции. Анализ данных. 8 класс: Учеб. для общеобразоват. учеб. заведений. – М.: Дрофа, 2002. –

Слайды и текст этой презентации

Слайд 1ФБГОУ ВПО Уральский государственный педагогический университет – УрГПУ Математический факультет Кафедра высшей

математики МАТЕМАТИКА_2сем Часть 1. Элементы теории множеств. Комбинаторика Бодряков Владимир Юрьевич, д.ф.-м.н.,

проф. E-mail: Bodryakov_VYu@e1.ru

Екатеринбург
2013 - 2014

ФБГОУ ВПО Уральский государственный педагогический университет – УрГПУ Математический факультет Кафедра высшей математики   МАТЕМАТИКА_2сем

Слайд 2Литература и интернет - ресурсы
Дорофеев Г.В., Суворова С.Б., Бунимович Е.А.,

Кузнецова Л.В., Минаева С.С. Математика. Алгебра. Функции. Анализ данных. 8

класс: Учеб. для общеобразоват. учеб. заведений. – М.: Дрофа, 2002. – 304 с.
Виленкин Н.Я., Ивашев-Мусатов О.С., С.И. Шварцбурд. Алгебра и математический анализ. 11 кл.: Учеб. пособие для шк. и кл. с углубл. изуч. математики. – М.: Мнемозина, 2001. – 288 с.
Вернер А.Л., Карп А.П. Математика: Учеб. пособие для 11 кл. гуманит. профиля. – М.: Просвещение, 2002. – 191 с.
Никольский С.М., Потапов М.К., Решетников Н.Н., Шевкин А.В. Алгебра и начала анализа: Учеб. для 10 кл. общеобразоват. учреждений. - М.: Просвещение, 2003. – 383 с.
Гмурман В.Е. Теория вероятностей и математическая статистика: Учеб. пособие. – М.: Высшее образование, 2006. – 479 с.
Колмогоров А.Н. Основные понятия теории вероятностей. М.: Фазис, 1998. – 144 с.
http://http://wwwhttp://www.school.edu.ru
http://school-collection.edu.ru
Бунимович Е.А., Булычев В.А., Калманович В.В. Вероятность и статистика в школьном курсе математики (ИУМК). Методическое пособие для учителя. – М., 2008. – 139 с. – Режим доступа: http://school-collection.edu.rБунимович Е.А., Булычев В.А., Калманович В.В. Вероятность и статистика в школьном курсе математики (ИУМК). Методическое пособие для учителя. – М., 2008. – 139 с. – Режим доступа: http://school-collection.edu.ru

Литература и интернет - ресурсыДорофеев Г.В., Суворова С.Б., Бунимович Е.А., Кузнецова Л.В., Минаева С.С. Математика. Алгебра. Функции.

Слайд 3Предваряя теорию множеств… Повторим известное
Задача 1. Пусть A и B –

некоторые множества. Верно ли утверждение: если A∪B = C, то

A = C\B?

Задача 2. Пусть B и C – некоторые множества. Верно ли утверждение: если A = C\B, то A∪B = C?


Предваряя теорию множеств… Повторим известноеЗадача 1. Пусть A и B – некоторые множества. Верно ли утверждение: если

Слайд 4Предваряя теорию множеств… Повторим известное
Ответ к задаче 1: В общем случае

утверждение неверно. Имеет место включение C\B ⊂ A. Равенство имеет

место лишь при условии A∩B = ∅ (см. рис.):



Ответ к задаче 2: В общем случае утверждение неверно. Имеет место включение C ⊂ A∪B. Равенство имеет место лишь при условии B ⊂ C (см. рис.):

A

B

B


C

Предваряя теорию множеств… Повторим известноеОтвет к задаче 1: В общем случае утверждение неверно. Имеет место включение C\B

Слайд 5Предваряя теорию множеств… Повторим известное.
Пусть A, B и C – некоторые

множества.
Задача 3. Верно ли что: A∪(B\C) = (A∪B)\C?
Если равенство

в общем случае неверно, то в какую сторону имеет место включение? При каких условиях равенство все же справедливо? Результаты расчетов отобразить с помощью диаграмм Эйлера – Венна.
Задача 4. Верно ли что: (A\B)∩C = A\(B∩C)?
Если равенство в общем случае неверно, то в какую сторону имеет место включение? При каких условиях равенство все же справедливо? Результаты расчетов отобразить с помощью диаграмм Эйлера – Венна.

Предваряя теорию множеств… Повторим известное.Пусть A, B и C – некоторые множества.Задача 3. Верно ли что: A∪(B\C)

Слайд 6Предваряя теорию множеств… Повторим известное.
Ответ к задаче 3: В общем случае

утверждение неверно. Имеет место включение A∪(B\C) ⊃ (A∪B)\C. Равенство имеет

место лишь при условии A∩С = ∅ (см. рис.):


Ответ к задаче 4: В общем случае утверждение неверно. Имеет место включение (A\B)∩C ⊂ A\(B∩C). Равенство имеет место лишь при условии A ⊂ C (см. рис.):

B

A

C

B

C

A

Предваряя теорию множеств… Повторим известное.Ответ к задаче 3: В общем случае утверждение неверно. Имеет место включение A∪(B\C)

Слайд 72.1 Элементы теории множеств 2.1.1 Основные определения
«Определение»: Множеством называют совокупность элементов

любой природы, объединенных по некоторому признаку. Множество считается заданным, если

о каждом элементе можно однозначно сказать, принадлежит он этому множеству или нет.
Замечание: Строго говоря, понятие «Множество» не определяется, а лишь иллюстрируется примерами.
Обычно множества обозначают прописными буквами латинского алфавита (A, B, C, … X, Y, Z), а их элементы – малыми (a, b, c, … x, y, z). Если элемент x принадлежит множеству X, то пишут x ∈ X; в противном случае пишут x ∉ X.
П р и м е р. Если X – множество русских слов из словаря В.И. Даля, а x1 = «семья»; x2 = «family», x3 = «ъ», то x1 ∈ X, а x2, x3 ∉ X.
Определение: Два множества называются равными, если они состоят из одних и тех же элементов. В этом случае пишут X = Y.
П р и м е р. Равными будут множества X = {1; 2; 3; 4} и Y – множество корней уравнения (x – 1)(x – 2)(x – 3)(x – 4) = 0.
2.1 Элементы теории множеств 2.1.1 Основные определения«Определение»: Множеством называют совокупность элементов любой природы, объединенных по некоторому признаку.

Слайд 8
Определение: Множество, не содержащее ни одного элемента, называются пустым и

обозначается символом ∅.
П р и м е р. Пустым будет

множество X действительных корней уравнения x2 + 1 = 0; в этом случае X = ∅.
Определение: Множество, содержащее конечное число элементов, называются конечным; множество содержащее бесконечное число элементов, называется бесконечным. (В последнем случае бесконечные множества подразделяются на счетные и несчетные).
Если множество конечно, то его можно задать указанием всех элементов, которые ему принадлежат. В этом случае пишут: A = {a1; a2; …; an} – множество A содержит n элементов a1; a2; …; an; тем самым задается список элементов множества. Два списка элементов одного и того же множества могут отличаться лишь порядком элементов в них.
Для большинства приложений порядок элементов в множестве оказывается несущественным, хотя возможно рассмотрение и упорядоченных множеств, список элементов в которых строится по заранее определенному принципу. Такими свойствами, например, обладает множество слов какого-либо языка, упорядоченных по лексикографическому (алфавитному) признаку.
Определение: Множество, не содержащее ни одного элемента, называются пустым и обозначается символом ∅.П р и м е

Слайд 9
Если множество бесконечно, или конечно, но содержит очень большое число

элементов, то его задают указанием характеристического свойства данного множества. В

этом случае пишут X = {x: P(x)}, где P(x) – характеристическое свойство, т.е. условие, которому удовлетворяют все элементы множества X. Иногда этот подход удобен и для задания конечных множеств.
П р и м е р. Множество A цифр десятичной системы исчисления конечно и может быть задано перечислением всех своих элементов: A = {0; 1; 2; 3; 4; 5; 6; 7; 8; 9}. Множество B учеников в классе конечно и может быть задано перечислением всех своих элементов, например, в виде списка в классном журнале. Множество равносторонних треугольников бесконечно и в этом случае указывают: Y = {ΔABC: AB = BC = CA}.

Если множество бесконечно, или конечно, но содержит очень большое число элементов, то его задают указанием характеристического свойства

Слайд 10
Множества и операции над множествами удобно изображать с помощью диаграмм

Эйлера – Венна. Здесь каждое множество символически изображается кругом (овалом)

(рис. 1).
  
 
Рис. 1
Определение: Если каждый элемент множества X является в то же время элементом множества Y, то X называется подмножеством множества Y. В этом случае говорят, что X включено в Y и пишут X ⊆ Y или, эквивалентно, Y ⊇ X. Если, сверх того, множество Y содержит элементы, которые не принадлежат множеству X, то включение является строгим: X ⊂ Y или, эквивалентно, Y ⊃ X (рис. 2).


Рис. 2

Множества и операции над множествами удобно изображать с помощью диаграмм Эйлера – Венна. Здесь каждое множество символически

Слайд 11
Определение: Пересечением (произведением) двух множеств A и B называется множество

C = A∩B, состоящее из элементов, которые принадлежащих как множеству

A, так и множеству B. Это можно записать как C = A∩B = {x: x ∈ A и x ∈ B} (рис. 3).



Рис. 3

Замечание: Когда речь о двух множествах, то, в общем случае, каждое из них может содержать два типа элементов (два непересекающихся подмножества). А именно, i) собственные элементы, которые принадлежат исключительно данному множеству, и ii) элементы, общие с другим множеством:
A = {x: xA ∪ xAB}; B = {x: xB ∪ xAB}.
Здесь учтено, что {xAB} = {xBA}. В этих обозначениях пересечением множеств будет множество C = {x: xAB}.

Определение: Пересечением (произведением) двух множеств A и B называется множество C = A∩B, состоящее из элементов, которые

Слайд 12
Определение: Объединением (суммой) двух множеств A и B называется множество

C = A∪B, состоящее из элементов, принадлежащих хотя бы одному

из множеств A, B (рис. 4). Это можно записать как C = A∪B = {x: x ∈ A или x ∈ B} или, с учетом возможных типов элементов, C = A∪B = {x: xA ∪ xB ∪ xAB}.






Рис. 4.


Определение: Объединением (суммой) двух множеств A и B называется множество C = A∪B, состоящее из элементов, принадлежащих

Слайд 13
Определение: Разностью двух множеств A и B называется множество C

= A\B, состоящее из собственных элементов, принадлежащих исключительно множеству A.

Этот факт можно записать как C = A\B = {x: x ∈ A и x ∉ B} или, с учетом возможных типов элементов, C = A\B = {x: xA} (рис. 5).
 




Рис. 5

Замечание: Когда речь о числовых множествах, то, в общем случае, при нахождении разности C = A\B из множества A следует удалить граничные точки, общие с множеством B.
Определение: Разностью двух множеств A и B называется множество C = A\B, состоящее из собственных элементов, принадлежащих

Слайд 14
Определение: Множество U, состоящее из элементов всех множеств, рассматриваемых в

данной задаче, называется универсальным. Разность Ā = U\A называется дополнением

множества A. Поскольку U ⊃ A, то U = {x: xU ∪ xUA}; A = {x: xUA}; и дополнение множества Ā = U\A = {x: xU} (рис. 6).

 
 
Рис. 6

П р и м е р. Пусть множество A – множество учащихся в 11а классе; B – в 11б классе; C – в 11в классе. Тогда множество U учащихся всех трех 11-x классов (11а, 11б, 11в) будет универсальным по отношению ко множеству A, а дополнением множества A будет множество Ā = U\A = B∪C.
Определение: Мощностью множества A с конечным числом элементов называется число его элементов; это обозначается как n(A) или |A|.

Определение: Множество U, состоящее из элементов всех множеств, рассматриваемых в данной задаче, называется универсальным. Разность Ā =

Слайд 152.1.2 Законы алгебры множеств
Операции над множествами обладают свойствами, отчасти напоминающими

свойства действий над действительными числами. Приведем некоторые из них:
A∪B =

B∪A;
A∩B = B∩A;
(A∪B)∪C = A∪(B∪C);
(A∩B)∩C = A∩(B∩C);
(A∪B)∩C = (A∩C)∪(B∩C);
(A∩B)∪C = (A∪C)∩(B∪C);
(Ā) = A;
∅ = U;
U = ∅;
A ∩ B = A ∪ B;
A ∪ B = A ∩ B, и др.

2.1.2 Законы алгебры множествОперации над множествами обладают свойствами, отчасти напоминающими свойства действий над действительными числами. Приведем некоторые

Слайд 16
Докажем, например, законы (10), (11) – законы (принцип) двойственности де

Моргана.
Доказательство: Ясно, что A ⊂ U; B ⊂ U. В

общем случае указанные множества содержат следующие типы элементов:
U = {x: xU ∪ xUA ∪ xUB ∪ xUAB};
A = {x: xUA ∪ xUAB};
B = {x: xUB ∪ xUAB}.
Соответственно,
A∩B = {x: xUAB} и A∩B = {x: xU ∪ xUA ∪ xUB};
A = {x: xU ∪ xUB}; B = {x: xU ∪ xUA} и A ∪ B = {x: xU ∪ xUA ∪ xUB}.
Равенство (10) доказано. Аналогично,
A∪B = { x: xUA ∪ xUB ∪ xUAB } и A∪B = {x: xU};
A = {x: xU ∪ xUB}; B = {x: xU ∪ xUA} и A ∩ B = {x: xU}.
Равенство (11) доказано.
Докажем, например, законы (10), (11) – законы (принцип) двойственности де Моргана.Доказательство: Ясно, что A ⊂ U; B

Слайд 172.1.3 Разбиение множества на подмножества
В основе всевозможных классификаций, применяемых в

биологии, лингвистике, социологии, экономике, юриспруденции и др. науках лежит операция

разбиения множества на попарно непересекающиеся части.
Определение: Пусть U – некоторое множество и Xk – система подмножеств множества U, обладающая следующими свойствами:
Объединение всех множеств Xk совпадает с U, т.е. U = ∪ Xk;
Множества Xk попарно не пересекаются, т.е. если k ≠ m, то Xk ∩ Xm = ∅.
П р и м е р. Множество всех действительных чисел R разбивается на два класса непересекающихся числовых множеств – на множество Q рациональных и множество Ir – иррациональных чисел: R = Q∪Ir, причем Q∩Ir = ∅. Множество всех слов русского языка разбивается на непересекающиеся классы слов, начинающихся с буквы а, б, в, ….

2.1.3 Разбиение множества на подмножестваВ основе всевозможных классификаций, применяемых в биологии, лингвистике, социологии, экономике, юриспруденции и др.

Слайд 18Предваряя комбинаторику… Повторим известное
Задача 1. В магазине "Все для чая'' есть

5 разных чашек и 3 разных блюдца. Сколькими способами можно

купить чашку с блюдцем?
Задача 2. Маша на свой день рождения пригласила в гости трех лучших подруг - Дашу, Глашу и Наташу. Когда все собрались, то по случаю дня рождения Маши решили обняться - каждая пара по одному разу. Сколько получилось разных пар?
Задача 3. На шахматном турнире каждый участник с каждым сыграл по одной партии. Всего сыграно 36 партий. Сколько шахматистов участвует в турнире?
Задача 4. Назовем натуральное число «симпатичным», если в его записи встречаются только нечетные цифры. Сколько существует 4-значных «симпатичных» чисел?
Задача 5. (Шутка) Как-то раз в воскресенье семеро друзей зашли в кафе, уселись за один столик и заказали мороженое. Хозяин кафе сказал, что если друзья в каждое следующее воскресенье будут садиться по-новому и перепробуют все способы посадки, то с этого момента он обещает кормить их мороженым бесплатно. Удастся ли друзьям воспользоваться предложением хозяина кафе?
Задача 6. Докажите, что среди 9 человек есть либо 3 попарно знакомых, либо 4 попарно незнакомых.




Предваряя комбинаторику… Повторим известноеЗадача 1. В магазине

Слайд 19Предваряя комбинаторику… Ответы
Ответ к задаче 1: n = 5⋅3 =15;
Ответ к

задаче 2: n = C42 = 6;
Ответ к задаче 3:

n = 9
Ответ к задаче 4: n = 54 = 625
Ответ к задаче 5: Различных способов посадки 7 друзей n = 7! = 5040; 5040 недель ≈ 96 лет.
Решение задачи 6: Присвоим каждому из 9 человек номера от 1 до 9; тогда множество X этих людей есть X = {x1; x2; …; x9}. Выберем произвольного человека, например, x1 и каждого из оставшихся 8-ми человек отнесем к одному из двух непересекающихся классов: A – множество людей, знакомых с x1 и B – множество людей, незнакомых с x1. Тогда минимальное число людей в каждом классе не может быть меньше 4 чел.

Предваряя комбинаторику… ОтветыОтвет к задаче 1: n = 5⋅3 =15;Ответ к задаче 2: n = C42 =

Слайд 202.2 Комбинаторика 2.2.1 Основные определения
При решении многих практических задач приходится выбирать

из некоторой совокупности объектов элементы, обладающие тем или иным свойством,

располагать эти элементы в определенном порядке и т.д. Поскольку в таких задачах речь идет о тех или иных комбинациях объектов, их называют комбинаторными задачами.
Определение: Область математики, в которой изучаются комбинаторные задачи, называют комбинаторикой.
В школьном курсе математики изучают лишь задачи, в которых надо найти число способов решения той или иной комбинаторной проблемы. Эти задачи образую часть комбинаторики, называемую перечислительной комбинаторикой или теорией перечислений.
Замечание: Характерной чертой математического подхода к решению практических задач является абстрагирование, т.е. отвлечение от конкретных черт, выявление глубинного содержания, общего для задач, внешне отличающихся друг от друга. Это приводит к построению модели задачи, к введению общих понятий, охватывающих различные частные случаи. В комбинаторике такие модели обычно строят с привлечением разобранных выше понятий множества, подмножества, упорядоченного множества и др.

2.2 Комбинаторика 2.2.1 Основные определенияПри решении многих практических задач приходится выбирать из некоторой совокупности объектов элементы, обладающие

Слайд 21Предваряя комбинаторные принцип умножения и сложения …
Задача 1. Тест состоит

из 30 вопросов на которые нужно дать ответ «Да» или

«Нет». Сколько существует различных вариантов ответов на вопросы теста?
Задача 2. Сколько существует подмножеств множества S, содержащего 5 элементов?
Задача 3. На блюде лежит 7 яблок и 4 груши. Каким количеством способов можно выбрать один плод?

Предваряя комбинаторные принцип умножения и сложения …Задача 1. Тест состоит из 30 вопросов на которые нужно дать

Слайд 22
Решение задачи 1: Поскольку существует два варианта ответа на каждый

вопрос, то полное количество вариантов ответов на 30 вопросов теста

составляет n = 230.
Ответ: n = 230.
Решение задачи 2: Пусть S = {s1; s2; s3; s4; s5}. Сопоставим каждому подмножеству множества S битовую строку длины 5 (по числу элементов). Если k-ый элемент принадлежит формируемому подмножеству, то сопоставляем ему 1; в противном случае – 0. В итоге получаем битовую строку длины 5, заполненную 0 или 1. Например, подмножеству {s1; s2; s5} соответствует битовая строка 11001. Всего существует n = 25 = 32 различных битовых строк длины 5.
Ответ: n = 25 = 32.
Решение задачи 3: Существует 7 вариантов выбора яблока и 4 варианта выбора груши: всего 11 вариантов.
Ответ: n = 11.


Решение задачи 1: Поскольку существует два варианта ответа на каждый вопрос, то полное количество вариантов ответов на

Слайд 232.2.2 Комбинаторные принципы умножения и сложения  Комбинаторный принцип умножения.
Комбинаторный принцип умножения.

Пусть задана последовательность событий
E1; E2; …; Em
таких, что событие

E1 осуществляется n1 способами, событие E2 осуществляется n2 способами (после осуществления события E1), …, событие Em осуществляется nm способами (после осуществления событий E1; E2; …; Em–1).
Тогда существует n1 × n2 × … nm способов осуществления всей последовательности событий.
2.2.2 Комбинаторные принципы умножения и сложения  Комбинаторный принцип умножения.Комбинаторный принцип умножения. Пусть задана последовательность событий E1; E2;

Слайд 24Комбинаторный принцип сложения
Комбинаторный принцип сложения. Пусть задана последовательность S1; S2;

…; Sm – попарно непересекающихся множеств (т.е. при i ≠

j пересечение Si ∩ Sj = ∅) и пусть множество S1 содержит n1 элементов; S2 содержит n2 элементов; …; множество Sm содержит nm элементов.
Тогда количество вариантов выбора одного элемента из S1 или S2; …; или Sm равно n1 + n2 + … + nm.
На языке теории множеств это утверждение может быть переписано как
|S1 ∪ S2 ∪ … ∪ Sm| = |S1| + |S2| + … + |Sm|
при условии, что пересечение Si ∩ Sj = ∅ при i ≠ j .


Комбинаторный принцип сложенияКомбинаторный принцип сложения. Пусть задана последовательность S1; S2; …; Sm – попарно непересекающихся множеств (т.е.

Слайд 25
Задача 4. Сколько существует натуральных чисел между 0 и 1000,

содержащих ровно одну цифру 6?





Задача 4. Сколько существует натуральных чисел между 0 и 1000, содержащих ровно одну цифру 6?

Слайд 26
Решение задачи 4: Разобьем множество S натуральных чисел между 0

и 1000, содержащих ровно одну цифру 6 на непересекающиеся классы:

1-цифровое множество S1, 2х-цифровое множество S2 и, наконец, 3х-цифровое множество S3. Очевидно,
|S1| = |6| = 1;
|S2| = |6; 6 | + |6, 0; 6| = 9 + 8 = 17;
|S3| = |6; 6; 6| + |6, 0; 6; 6| + | 6, 0; 6; 6| = 9⋅9 + 8⋅9 + 8⋅9 = 81 + 72 + 72 = 225.
|S| = |S1| + |S2| + |S3| = 1 + 17 + 225 = 243.
Ответ: |S| = |S1| + |S2| + |S3| = 243.


Решение задачи 4: Разобьем множество S натуральных чисел между 0 и 1000, содержащих ровно одну цифру 6

Слайд 27
Задача 5. Сколько существует натуральных чисел между 0 и 1000,

содержащих хотя бы одну цифру 6?





Задача 5. Сколько существует натуральных чисел между 0 и 1000, содержащих хотя бы одну цифру 6?

Слайд 28
Решение задачи 5: Разобьем множество S натуральных чисел между 0

и 1000, на непересекающиеся подмножества чисел, содержащих 6:
1-цифровое множество

S1 может содержать ровно одну цифру 6;
2-цифровое множество S2 может содержать одну или две цифры 6;
3-цифровое множество S3 может содержать одну, две или три цифры 6.
В первом случае, как и в предыдущем примере:
|S1| = |6| = 1.
Во втором случае:
|S2| = |6; 6| + |6, 0; 6| + |6; 6| = 9 + 8 + 1 = 17 + 1 = 18.
Наконец, в третьем случае: |S3| = |6; 6; 6| + | 6, 0; 6; 6| + | 6, 0; 6; 6| +
+ |6; 6; 6| + |6; 6; 6| + | 6, 0; 6; 6| + |6; 6; 6| =
= 9⋅9 + 8⋅9 + 8⋅9 + 9 + 9 + 8 + 1 = 81 + 72 + 72 = 225 + 26 + 1 = 252.
|S| = |S1| + |S2| + |S3| = 1 + 18 + 252 = 271.
Ответ: |S| = |S1| + |S2| + |S3| = 271.


Решение задачи 5: Разобьем множество S натуральных чисел между 0 и 1000, на непересекающиеся подмножества чисел, содержащих

Слайд 29
Задача 6. Сколько среди первых 100 натуральных чисел не делятся

ни на 2, ни на 3, ни на 5? Есть

ли среди этих чисел составные, и если да, то сколько их?


Задача 6. Сколько среди первых 100 натуральных чисел не делятся ни на 2, ни на 3, ни

Слайд 30
Решение задачи 6: Представим натуральное число a, меньшее 100 (100

является четным числом и поэтому не годится) в виде:
a

= 10⋅l + k.
С учетом условия, k ∈ {1; 3; 7; 9}; l ∈ {0; 1; 2; 3; 4; 5; 6; 7; 8; 9},
причем сумма l + k не должна делиться на 3.
Суммы l + k (красным выделены суммы, кратные 3)






Ответ: |A| = 26: A = {1; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 49; 53; 59; 59; 61; 67; 71; 73; 77; 79; 83; 89; 91; 97}.


Решение задачи 6: Представим натуральное число a, меньшее 100 (100 является четным числом и поэтому не годится)

Слайд 31Комбинаторный принцип сложения для двух пересекающихся множеств
Комбинаторный принцип сложения для

двух пересекающихся множеств. Пусть S и T – произвольные множества

(возможно пересекающиеся). Тогда количество элементов, которые можно выбрать из S или T равно |S ∪ T| = |S| + |T| – |S∩T|.
Доказательство. Для доказательства воспользуемся законами алгебры множеств. Нетрудно доказать, что справедливы следующие разложения множеств на попарно непересекающиеся подмножества:
S ∪ T = (S\T) ∪ (T\S) ∪ (S∩T);
S = (S\T) ∪ (S∩T);
T = (T\S) ∪ (S∩T).
В соответствии с комбинаторным принципом сложения для непересекающихся множеств имеем:
|S ∪ T| = |S\T| + |T\S| + |S∩T|;
|S| = |S\T| + |S∩T|;
|T| = |T\S| + |S∩T|.
Складывая два последних равенства и вычитая сумму из первого, получим требуемое утверждение: |S ∪ T| = |S| + |T| – |S∩T|, ч.т.д.


Комбинаторный принцип сложения для двух пересекающихся множествКомбинаторный принцип сложения для двух пересекающихся множеств. Пусть S и T

Слайд 32
Задача 7. В группе из 100 студентов 60 чел изучают

математику; 75 – историю; 45 чел – и то и

другое. Сколько человек изучают математику или историю? Сколько человек не изучают ни математику, ни историю?



Задача 7. В группе из 100 студентов 60 чел изучают математику; 75 – историю; 45 чел –

Слайд 33
Решение задачи 7: Обозначим через M – множество студентов, изучающих

математику (возможно, совместно с историей); H – множество студентов, изучающих

историю (возможно, совместно с математикой). Тогда M∩H – множество студентов, изучающих и математику, и историю. По условию:
|M| = 60; |H| = 75; |M∩H| = 45.
Согласно комбинаторному принципу сложения для двух произвольных множеств имеем для числа студентов, изучающих математику или историю:
|M∪H| = |M| + |H| – |M∩H| = 60 + 75 – 45 = 90 чел.
Тогда число студентов, не изучающих ни математику, ни историю, составляет
| M ∪ H | = 100 – 90 = 10 чел.
Ответ: |M∪H| = |M| + |H| – |M∩H| = 90 чел; | M ∪ H | = 10 чел.


Решение задачи 7: Обозначим через M – множество студентов, изучающих математику (возможно, совместно с историей); H –

Слайд 342.2.3 Перестановки, размещения, сочетания
Пусть имеется набор из некоторого числа объектов.

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

упорядоченные n-элементные множества, различающиеся порядком элементов. Число перестановок n-элементного множества может быть найдено по формуле Pn = n!
Задача 7. В коробке имеется 4 пронумерованных шара с номерами {1; 2; 3; 4}. Шары вынимаются по одному и кладутся в ряд, образуя 4-значное число. Сколько различных чисел может быть получено при вынимании шаров? Сколько из них будет начинаться с 1?
Решение: Количество 4-значных чисел, очевидно, равно числу перестановок из 4 цифр {1; 2; 3; 4} и составляет P4 = 4! = 24.
Количество 4-значных чисел, с единицей на первой позиции, очевидно, равно числу перестановок из 3 оставшихся цифр {2; 3; 4} и составляет P3 = 3! = 6.
Ответ: P4 = 4! = 24; P3 = 3! = 6.
2.2.3 Перестановки, размещения, сочетанияПусть имеется набор из некоторого числа объектов. Переставляя их, будем получать различные порядки их

Слайд 35
П р и м е р. Пусть в некоторой организации

20 чел и из них требуется выбрать президента, вице-президента, секретаря

и казначея (должности не совмещаются).
Решение: Имеется 20 вариантов выбора президента; 19 вариантов выбора вице-президента (после того, как президент выбран); 18 вариантов выбора секретаря из оставшихся членов организации и, наконец, 17 вариантов выбора казначея.
Число вариантов выбора 4-х должностных лиц в определенном порядке следования составляет:
20 × 19 × 18 × 17 = 20!/16! = 20!/(20-4)! = 116280.
Ответ: A204 = 116280.
 Определение: Размещениями из n элементов по k элементов называются упорядоченные k-элементные подмножества n-элементного множества, различающиеся порядком элементов. Число размещений из n элементов по k элементов может быть найдено по формуле
Ank = n!/(n-k)! = n(n – 1)(n – 2) … (n – k + 1).
П р и м е р. Пусть в некоторой организации 20 чел и из них требуется выбрать

Слайд 36
Задача 8. Сколькими способами можно составить трехцветный полосатый флаг, если

имеются ткани пяти различных цветов? Сколькими способами можно составить трехцветный

полосатый флаг, если одна полоса должна быть красной?
Решение: Количество способов выбрать ткани трех различных цветов из 5-ти может быть найдено как число размещений:
n1 = A53 = 5!/(5-3)! = 5⋅4⋅3 = 60.
Если одна полоса должна быть красной, то две оставшиеся полосы могут быть одного из 4-х оставшихся цветов. Количество способов выбрать ткани двух различных цветов из 4-х может быть найдено как число размещений:
n2 = A42 = 4!/(4-2)! = 3⋅4 = 12.
Ответ: n1 = 60; n2 = 12.
Задача 8. Сколькими способами можно составить трехцветный полосатый флаг, если имеются ткани пяти различных цветов? Сколькими способами

Слайд 37
П р и м е р. Пусть в некоторой организации

20 чел и из них требуется выбрать комитет из 4-х

человек, при этом порядок персоналий безразличен.
Решение: Имеется 20 вариантов выбора первого члена комитета; 19 вариантов выбора второго члена комитета (после того, как первый выбран); 18 вариантов выбора третьего члена комитета из оставшихся членов организации и, наконец, 17 вариантов выбора 4-го члена комитета.
Число вариантов выбора 4-х должностных лиц составляет
A204 = 20 × 19 × 18 × 17 = 116280.
Полученное число следует уменьшить в P4 = 4! раз, так как порядок следования персоналий значения не имеет, а число перестановок элементов в выбранной четверке должностных лиц составляет именно P4. Поэтому число способов выбора членов комитета
C204 = A204/P4 = 20! / (20-4)!⋅4! = 20 × 19 × 18 × 17 / 24 = 4845.
  Ответ: C204 = 4845.
П р и м е р. Пусть в некоторой организации 20 чел и из них требуется выбрать

Слайд 38
Определение: Сочетаниями из n элементов по k элементов называются k-элементные

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

из n элементов по k элементов может быть найдено по формуле
Cnk = Ank / Pk = n! / (n-k)!⋅k!
Определение: Сочетаниями из n элементов по k элементов называются k-элементные подмножества n-элементного множества, безотносительно к порядку следования

Слайд 39
Задача 9. Сколькими способами можно в строку выписать шесть плюсов

и четыре минуса?


Задача 9. Сколькими способами можно в строку выписать шесть плюсов и четыре минуса?

Слайд 40
Решение задачи 9: Заметим, что выписанные шесть плюсов задают уже

тем самым положения минусов. Поэтому, для ответа на вопрос задачи

достаточно найти число способов выписать шесть плюсов на 10 позициях. Количество способов сделать это может быть найдено как число сочетаний из 10 элементов по 6:
C106 = 10! / (10-6)!⋅6! = 10! / 4!⋅6! = 7⋅8⋅9⋅10 / 24 = 210.
Ответ: n = C106 = 210.
Замечание. Очевидно, что аналогичное рассуждение с точки зрения размещения четырех «-» на 10 позициях должно приводить к тому же результату, и это действительно так:
C104= 10! / (10-4)!⋅4! = 10! / 6!⋅4! = C106 = 210.
Вообще,
Cnk = Cnn-k .
Решение задачи 9: Заметим, что выписанные шесть плюсов задают уже тем самым положения минусов. Поэтому, для ответа

Слайд 41Спасибо за внимание! Данный раздел закончен.
Ваши вопросы, замечания, предложения …

Спасибо за внимание! Данный раздел закончен.Ваши вопросы, замечания, предложения …

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.


Для правообладателей

Яндекс.Метрика