ЛК2 (1)

1. Неупорядоченные выборки (сочетания).

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 - A .

6. Свойства

•A = U \ A= {х | х U, х A}
• А А = А; А А = А;
• А U = U; А U = А;
• А = А; А = ;
• A A U ; A A ;
• A A;
• U ; U ;
(законы де-Моргана или формулы
двойственности).
A B A B;
A B A B.

7. Формула включений и исключений

N Ai N A1 ... N Ak N A1 A2 ... N Ak 1 Ak
i
N A1 A2 A3 ... N Ak 2 Ak 1 Ak ... 1 k 1 N A1 A2 ... Ak
• «+», если количество множеств нечетное
• «–», если количество множеств четное.
Чаще эту формулу используют при k=2, оформляя ее
отдельной леммой:
N A1 A2 N A1 N A2 N A1 A2
Задача 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. Правила комбинаторики

• Правило суммы:
Если элемент x1 можно выбрать m1способами,
элемент x 2 - m2 способами, …, x-k mkспособами,
то или x1, или x 2, … , или xkможно выбрать
m1 m 2 ... m k способами.
• Правило произведения
Если элемент x можно выбрать mспособами,
1
1
элемент x - m способами, …, x- m способами,
2
2
k
k
то последовательность из k элементов - x , x , ..., x
1 2
k
картеж, т.е. и , и , … , и x можно выбрать
x1 x 2
k
способами.
m1 m2 ... mk

12.

Теорема: Число подмножеств n - элементного множества
n
a
.
M
,
a
,
...
a
2
12 n
Доказательство
Метод мат. индукции
1.
Если M не содержит элементов, т.е. n=0, то М содержит
только одно подмножество – пустое:
. Причем, справа
M
0
.
2
1
k
,k
0
2.
Пусть утверждение верно для n
. Т.е. подмножеств
2k .
n
k
1
a
получено добавлением элемента ak 1 к k –
Пусть M
,
...
a
,
a
1 kk
1
a
.
элементному M...
,a
1
k
Тогда любое подмножество множества М либо содержит ak 1 ,
либо не содержит ak 1 .
Подмножеств, не содержащих ak 1 – 2 k штук.
Подмножеств, содержащих ak 1 – ______ штук
k
Т.е. искомое число подмножеств 2
.
____
____
3.

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

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

14. Упорядоченные выборки

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

15. Упорядоченные выборки

• Всякая упорядоченная выборка объема m из
множества, состоящего из n различных
объектов, называется размещением из n
n!
элементов по m
m
An
n m !
• Размещение с повторением A m n m
n
• Размещение из n элементов по n
называются перестановками из n
элементов
n
Pn An n!

16. Неупорядоченные выборки

• Всякая неупорядоченная выборка объема m
из множества, состоящего из n различных
объектов, называется сочетанием из n по m
n!
.
m! n m !
n
• Сочетание с повторением C m Cnn m 1
m
Cn

17.

Свойства сочетаний
m
n
m
1. C
C
n
n
Аналитическое доказательство.
n
!
n
! m
n
m
C
C
n
n
n
!
n
n
!
n
!
m
m
m
m
!
Комбинаторное доказательство: Каждая неупорядоченная выборка
объемом m однозначно определяет некоторую неупорядоченную
выборку объема n
. Следовательно, число сочетаний, состоящее из m
m
элементов:
элементов равно числу сочетаний, состоящих из n
m
m
n
m
.
C
C
n
n
m
1
n
m
1
2. C
C
C
n
1
n
n
Аналитическое доказательство.
n
m
n
!
n
!
n
!
1
m
n
m
1
C
C
n
n
n
!
!
m
! m
!
n
!
m
m
! n
m
1
1
1
m
n
n
!
n
!
1
1
m
1
1
C
1
m
!
n
!
m
!
n
m
n
1
m
1
1
1
0 1 2
n
3. C
C
C
...
2
n n n

18. О выборках

ВЫБОРКИ
Упорядоченные
Размещения
Простые
Ank
n!
n k !
С повторениями
k
An n k
Неупорядоченные
Сочетания
Перестановки
Простые
С повторениями
Pn n!
Pn
n!
n1!n2!...nk !
Простые
Cnk
n!
k ! n k !
С повторениями
k
C n Cnk k 1
Нулевое правило:
• Каково основное множество и сколько элементов оно
содержит?
• Сколько элементов содержат сами подмножества?
• Важен ли порядок элементов?
• Повторяются ли элементы в выборках?

19. Задачи

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

20. Задачи

• Задача 10. Сколько можно составить пятизначных чисел, все
цифры которых различны, из цифр 0; 1; 2; 3; 4;?
• Задача 11. Каждая из 5 подруг собирается вечером пойти либо
в кино, либо в театр. Сколькими различными способами эти 5
подруг смогли бы провести вечер?
• Задача 12. «Вороне как-то Бог послал кусочек сыра», брынзы,
колбасы, сухарика и шоколада. «На ель Ворона взгромоздясь,
позавтракать совсем уж было собралась, да призадумалась»:
• а) если есть кусочки по очереди. то из скольких вариантов
придется выбирать;
• б) сколько получится «бутербродов» из двух кусочков;
• в) если съесть сразу три кусочка, а остальные спрятать, то из
скольких вариантов придется выбирать;
• г) сколько получится вариантов, если какой-то кусочек все-таки
бросить Лисе, а потом ответить на вопрос пункта а)?

21. Спасибо за снимание!