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

Сентябрь 3, 2022

Главная
Алгебра
Основы теории множеств Элементы комбинаторики

Содержание

2. Множества Множество —понятие не сводится к другим понятиям и не определяется Предметы (объекты), составляющие множество, называют
3. Операции над множествами Если каждый элемент множества A является элементом множества B, то говорят, что A
4. Операции над множествами Объединением двух множеств А и В называется множество, состоящее из всех элементов, принадлежащих
5. Операции над множествами Симметрической разностью множеств А и В называется множество, состоящее из всех элементов, принадлежащих
6. Свойства = U \ A= {х | х ∈ U, х ∉ A} А ∪ А
7. Формула включений и исключений «+», если количество множеств нечетное «–», если количество множеств четное. Чаще эту
8. Формула включений и исключений Обозначим через А — множество школьников, знающих английский язык; N — множество
9. Формула включений и исключений С помощью диаграмм Эйлера-Венна: Так как 3 языка знают 3 школьника, то
10. Элементы комбинаторики Комбинаторика – это раздел математики, в котором исследуются и решаются задачи выбора элементов из
11. Правила комбинаторики Правило суммы: Если элемент можно выбрать способами, элемент - способами, …, - способами, то
13. Элементы комбинаторики Задача 2. В магазине есть 7 видов шариковых ручек и 5 видов гелиевых. Сколько
14. Упорядоченные выборки Если исходное множество состоит из n различных элементов, и при каждом выборе мы будем
15. Упорядоченные выборки Всякая упорядоченная выборка объема m из множества, состоящего из n различных объектов, называется размещением
16. Неупорядоченные выборки Всякая неупорядоченная выборка объема m из множества, состоящего из n различных объектов, называется сочетанием
18. О выборках Нулевое правило: Каково основное множество и сколько элементов оно содержит? Сколько элементов содержат сами
19. Задачи Задача 6. Из 30 участников собрания надо выбрать председателя и секретаря. Сколькими способами это можно
21. Скачать презентацию

Слайд 2

Множества
Множество —понятие не сводится к другим понятиям и не определяется
Предметы (объекты),

составляющие множество, называют его элементами
Предложение «объект a является элементом множества A» записывается а ∈ А
Множество, не содержащее ни одного элемента, называют пустым и обозначают .

Слайд 3

Операции над множествами
Если каждый элемент множества A является элементом множества B,

то говорят, что A — подмножество множества B , записывают А ⊂ В.
Пересечением (произведением) множеств А и В называется множество, состоящее из всех элементов, принадлежащих одновременно и множеству А, и множеству В. Обозначают пересечение множеств A ∩ B. A ∩ B = {х | х ∈ A и х ∈ B}.

Слайд 4

Операции над множествами
Объединением двух множеств А и В называется множество, состоящее

из всех элементов, принадлежащих хотя бы одному из множеств А или В. Обозначают объединение множеств A ∪ B
Разностью множеств А и В называется множество, состоящее из всех элементов, множества А, не принадлежащих множеству В. Обозначают разность множеств A \ B = {х | х ∈ A и х ∉ B}.

Слайд 5

Операции над множествами
Симметрической разностью множеств А и В называется множество, состоящее

из всех элементов, принадлежащих только одному множеству А или В, обозначают A  B
Универсальное множество U (S) — это самое большое множество элементов, рассматриваемых в задаче
Дополнением множества A до универсального называется множество элементов универсального множества, не принадлежащих множеству A - .

Слайд 6

$Свойства = U \ A= {х | х ∈ U, х$

Свойства
= U \ A= {х | х ∈ U, х ∉ A}
А ∪ А =

А; А ∩ А = А;
А ∪ U = U; А ∩ U = А;
А ∪ ∅ = А; А ∩ ∅ = ∅;
(законы де-Моргана или формулы двойственности).

Слайд 7

Формула включений и исключений
«+», если количество множеств нечетное
«–», если количество множеств

четное.
Чаще эту формулу используют при k=2, оформляя ее отдельной леммой:
Задача 1. Из 100 школьников английский знают 42, немецкий — 30, французский — 28, английский и немецкий — 5, английский и французский — 10, немецкий и французский — 8, английский, немецкий и французский — 3 школьника. Сколько школьников не знают ни одного языка?

Слайд 8

Формула включений и исключений
Обозначим через А — множество школьников, знающих английский

язык; N — множество школьников, знающих немецкий язык; F — множество школьников, знающих французский язык.
Тогда n(A) = 42, n(N) = 30, n(F) = 28, n(A ∩ N) = 5,
n(A ∩ F) = 10, n(N ∩ F) = 8, n(A ∩ N ∩ F) = 3.
Найдем с помощью формулы включений и исключений количество школьников, знающих хотя бы один из перечисленных иностранных языков.
n(A ∪ N ∪ F) = n(A) + n(N) + n(F) –
– n(A ∩ N) – n(A ∩ F) – n(N ∩ F) + n(A ∩ N ∩ F) =
= 42 + 30 + 28 – 5 – 10 – 8 + 3 = 80.
Следовательно, не знают ни одного иностранного языка: 100 – 80 = 20 школьников.

Слайд 9

Формула включений и исключений
С помощью диаграмм Эйлера-Венна:
Так как 3 языка знают

3 школьника, то английский и немецкий знают 5 – 3 = 2, английский и французский — 10 – 3 = 7, немецкий и французский — 8 – 3 = 5 школьников. Только английский знают 42 – (2 + 3 + 7) = 30, только немецкий — 30 – (2 + 3 + 5) = 20, только французский — 28 – (3 + 5 + 7) = 13 школьников. Ни одного языка не знают 100 – (2 + 3 + 5 + 7 + 13 + 20 + 30) = 20 школьников.

Слайд 10

Элементы комбинаторики
Комбинаторика – это раздел математики, в котором исследуются и решаются

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

Слайд 11

Правила комбинаторики
Правило суммы:
Если элемент можно выбрать способами,
элемент - способами, …, -

способами, то или , или , … , или можно выбрать
способами.
Правило произведения
Если элемент можно выбрать способами,
элемент - способами, …, - способами,
то последовательность из k элементов -
картеж, т.е. и , и , … , и можно выбрать
способами.

Слайд 12

Слайд 13

Элементы комбинаторики
Задача 2. В магазине есть 7 видов шариковых ручек и

5 видов гелиевых. Сколько существует способов выбрать одну шариковую ручку и одну гелиевую?
Задача 3. В магазине есть 7 видов шариковых ручек и 5 видов гелиевых. Сколько существует способов выбрать ручку?
Задача 4. Сколькими способами можно назначить двух ребят на дежурство по столовой, если в классе 25 учащихся?

Слайд 14

Упорядоченные выборки
Если исходное множество состоит из n различных элементов, и при

каждом выборе мы будем извлекать из него новый элемент, отличный от всех других – это выбор без повторений.
Если элементы основного множества могут повторяться – это выбор с повторениями.
Извлеченные из исходного множества m элементов составляют выборку.

Слайд 15

Упорядоченные выборки
Всякая упорядоченная выборка объема m из множества, состоящего из n

различных объектов, называется размещением из n элементов по m
Размещение с повторением
Размещение из n элементов по n называются перестановками из n элементов

Слайд 16

Неупорядоченные выборки
Всякая неупорядоченная выборка объема m из множества, состоящего из n

различных объектов, называется сочетанием из n по m
Сочетание с повторением

Слайд 17

Слайд 18

О выборках
Нулевое правило:
Каково основное множество и сколько элементов оно содержит?
Сколько элементов

содержат сами подмножества?
Важен ли порядок элементов?
Повторяются ли элементы в выборках?

Слайд 19

Задачи
Задача 6. Из 30 участников собрания надо выбрать председателя и секретаря.

Сколькими способами это можно сделать?
Задача 7.В классе учится 18 девочек и 14 мальчиков. Для участия в викторине нужно выбрать 4 мальчиков и 3 девочек. Сколько существует различных составов команд?
Задача 8.Сколько автомашин могут иметь номера Томской области (70 RUS)?
Задача 9.Сколькими способами можно составить набор из 8 пирожных, если в продаже есть пирожные 5 сортов?

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

Содержание

МножестваМножество —понятие не сводится к другим понятиям и не определяетсяПредметы (объекты),

Операции над множествамиЕсли каждый элемент множества A является элементом множества B,

Операции над множествамиОбъединением двух множеств А и В называется множество, состоящее

Операции над множествамиСимметрической разностью множеств А и В называется множество, состоящее

Свойства= U \ A= {х | х ∈ U, х ∉ A} А ∪ А =

Формула включений и исключений«+», если количество множеств нечетное«–», если количество множеств

Формула включений и исключенийОбозначим через А — множество школьников, знающих английский

Формула включений и исключенийС помощью диаграмм Эйлера-Венна:Так как 3 языка знают

Элементы комбинаторикиКомбинаторика – это раздел математики, в котором исследуются и решаются

Правила комбинаторикиПравило суммы:Если элемент можно выбрать способами,элемент - способами, …, -

Элементы комбинаторикиЗадача 2. В магазине есть 7 видов шариковых ручек и

Упорядоченные выборкиЕсли исходное множество состоит из n различных элементов, и при

Упорядоченные выборкиВсякая упорядоченная выборка объема m из множества, состоящего из n

Неупорядоченные выборкиВсякая неупорядоченная выборка объема m из множества, состоящего из n

О выборкахНулевое правило:Каково основное множество и сколько элементов оно содержит?Сколько элементов

ЗадачиЗадача 6. Из 30 участников собрания надо выбрать председателя и секретаря.

Похожие презентации