Лекция 4.Комбинаторика

1.

❤tt♣✿✴✴♠❛t❤❝②
❜✳❝s✳♠s✉✳s✉

2.

3.

Комбинаторика – раздел дискретной математики,
посвящённый решению задач выбора и расположения
элементов некоторого, как правило, конечного
множества в соответствии с заданными свойствами.
В простейших комбинаторных задачах требуется
подсчитать число способов
выбрать k элементов из n–элементного множества.
То, что получается в результате выбора, называется
выборкой из n по k
или
(n,k)–выборкой.

4.

Понятие
выборки
подмножества:
отличается
от
понятия
• в
выборках
может
допускаться
повторение
элементов,
т.е.
выборки
могут
быть
как
с
повторениями, так и без повторений;
• выборки
могут
быть
упорядоченными
или
неупорядоченными.
Упорядоченность означает, что выборки, состоящие из
одних и тех же элементов, но расположенных в разном
порядке, считаются различными.
Итак, 4 выбора : выборки могут быть с
повторениями
и
без повторений,
упорядоченными
и
неупорядоченными

5.

Упорядоченная (n, k)– выборка без повторений
называется (n, k)– размещением (перестановкой) или
размещением из n элементов по
k.
Упорядоченная (n, k)– выборка с повторениями
называется (n, k)– размещением с повторениями.
(n, n)– размещение без повторений
перестановкой из n элементов.
называется
Неупорядоченная (n, k)–выборка без повторений
называется (n, k) -сочетанием или сочетанием из n
элементов по k, другими словами, это k–элементное
подмножество множества А.
Неупорядоченная (n, k)– выборка с повторениями
называется (n, k)– сочетанием с повторениями.

6.

Например, рассмотрим множество A ={a1,a2,a3}. Составим
выбор из трех элементов по два (3,2):
Размещения - Повторения не разрешены, порядок
существенен (a1, a2), (a2, a1), (a2, a3), (a3, a2), (a1, a3), (a3, a1).
Размещения с повторениями - Повторения разрешены,
порядок существенен (a1,a1), (a1,a2), (a2,a1), (a2,a2), (a1,a3),
(a3,a1), (a2,a3), (a3,a2), (a3,a3).
Сочетания - Повторения не разрешены, порядок
несущественен (a1, a2), (a1, a3), (a2, a3).
Сочетания с повторениями - Повторения разрешены,
порядок несущественен из (a1, a1), (a1, a2), (a1, a3), (a2, a2),
(a2, a3), (a3, a3).
Перестановки из трех элементов − это следующие
упорядоченные без повторений (3,3)-выборки: (a1,a2,a3),
(a1,a3,a2), (a2,a1,a3), (a2,a3,a1), (a3,a1,a2), (a3,a2,a1).

7.

8.

9.

10. Правило суммы гласит, что если А и В -несвязанные события, и существует n1 возможных исходов события A, и n2 возможных исходов

Правило суммы гласит, что если А и В -несвязанные события,
и
существует
и
n2 возможных исходов события B, то возможное число
исходов
возможных
n1
события
A
или
исходов
B
равно
события
сумме
A,
n1+n2.
Правило произведения – если дана последовательность
событий k с n1 возможными исходами первого, n2 -второго, и
т.д., вплоть до nk возможных исходов последнего, то общее
число
исходов
последовательности
произведению n1*n2*nk.
k
событий
равна

11. Правило суммы Если элемент х может быть выбран k способами, а элемент у может быть выбран n другими способами, тогда выбор

элемента х либо у может быть осуществлен
( k+n ) способами.
Правило произведения
Пусть набор (х, у) образуется в результате
последовательного выбора элементов х и у , причем элемент
х может быть выбран k способами, и при каждом выборе
элемента х элемент у может быть выбран n способами,
тогда выбор всех упорядоченных пар (х, у) может быть
осуществлен n⋅ k способами.

12.

Очень
многие
комбинаторные
задачи
решаются
применением трех простых правил: равенства, суммы
и произведения.
Правило равенства. Если между конечными множествами
A и B есть взаимно однозначное соответствие, то
A B
.
Правило суммы. Если A и B – конечные множества и
A, B , то A B A. B .
Правило произведения. Для любых конечных множеств A
и B имеет место равенство :
A B A B

13.

Правило суммы – частный случай формулы включений
и исключений. Если рассматривать А и B как множества
исходов, то | A| = n1, |B|=n2; а поскольку события А и B
не связаны с друг другом, то можно считать, что
соответствующие множества не пересекаются .
Тогда, по формуле включений и исключений A B A B
т.е. множество A B содержит n1+n2 элементов.
Это означает, что имеется возможность n1+n2 исходов
события А или B.
Правило произведения. Пусть А1 множество n1 исходов
первого события, А2 – множество n2 исходов второго
события и т.д. Тогда любую последовательность k
событий можно рассматривать как элемент декартова
произведения A А А , чья мощность равна
1
2
k
A1 А2 Аk = n1 *n2 *…*nk

14.

15.

16.

Задача 4. Сколько существует двузначных четных чисел с
разными цифрами?
Решение. Пусть α = α1α2 − двузначное четное число, у
которого все цифры различны. Тогда α2∈ {0,2,4,6,8} ,а
α1∈{1, 2, 3, 4, 5, 6, 7, 8, 9} \ {α2}.
Если α1 − нечетная цифра, т.е. α1∈{1, 3, 5, 7, 9}, получаем,
что первая цифра α1 может быть выбрана 5 способами.
При каждом выборе первой цифры α1, вторая цифра α2
может быть выбрана 5 способами.
По правилу произведения получим, что существуют 5 ⋅ 5 =
25 двузначных четных чисел, у которых первая цифра
нечетная.
Если α1 − четная цифра, тогда α1∈{2, 4, 6, 8},
а α2∈{0, 2, 4, 6, 8} \ {α1}, т.е. элемент α2 может быть выбран 4
способами.
По правилу произведения, число α может быть выбрано
4 ⋅ 4 = 16 способами.

17. Задача 5. Сколько существует четырехзначных чисел, делящихся на 5, у которых все цифры различны? Решение. Пусть А ={0, 1, 2, 3,

4, 5, 6, 7, 8, 9} – множество
цифр, α= α1α2α3α4− четырехзначное число, где α1∈A\{0},
α4∈{0,5}\{α1},α2∈A\{α1,α4},α3∈A\{α1,α2,α4}.
Если α4=0, тогда цифра α1 может быть выбрана 9
способами, цифра α2 может быть выбрана 8 способами, а α3 –
7 способами. По правилу произведения получаем, что число
α может быть получено 9 ⋅ 8 ⋅ 7 = 504 способами.
Если α4=5, тогда α1∈A\{0, 5 }, т.е. цифра α1 может быть
выбрана 8 способами, цифра α2 может быть выбрана также 8
способами, а α3 – 7 способами. По правилу произведения
получаем, что число α может быть выбрано 8⋅8⋅7=448
способами.
Таким образом, используя правило суммы, получаем, что
существует 504 + 448 = 952 четырехзначных чисел,
делящихся на 5, у которых все цифры различные.

18.

Эту же задачу можно решить другим способом.
Рассмотрим четное двузначное число α = α1α2, где
α1∈{1, 2, 3, 4, 5, 6, 7, 8, 9}, а α2∈{0, 2, 4, 6, 8}.
Первая цифра α1 может быть выбрана 9 способами.
Для каждой фиксированной цифры α1,
вторая цифра α2 может быть выбрана 5 способами.
По правилу произведения получаем, что существует 9 ⋅ 5 =
45 различных четных двузначных чисел.
Среди них четыре числа: 22, 44, 66, 88 – с одинаковыми
цифрами.
Отсюда получаем, что существует 45 – 4 = 41 двузначных
четных чисел с различными цифрами.

19.

20.

21.

22.

n!
A
(n k )!
k
n

23. А –первая буква французского слова arrangement, что означает размещение, приведение в порядок

k
An
n!
(n k )!
Ank n(n 1)(n 2) (n k 1)
(n k )(n k 1) 2 1
n(n 1)(n 2) (n k 1)
(n k )(n k 1) 2 1
n(n 1)(n 2) (n k 1)(n k )(n k 1) 2 1
(n k )(n k 1) 2 1
n!
(n k )!

24.

25. Задача 5. Сколько различных четырехбуквенных «слов» можно составить , используя буквы f,c,o,n,e, если под «словом» понимать

любую
последовательность неповторяющихся букв.
Решение. Имеем дело с подсчетом числа
размещений без повторений. Следовательно,
A64
6!
6! 6 5 4 3 2 1
6 5 4 3 360
(6 4)! 2!
2 1

26.

27.

28.

P – первая буква французского слова
permutation что означает перестановка
P(n) n!

29.

30.

ПРИМЕР:
Сколькими
способами
можно
расположить на шахматной доске 8 ладей так, чтобы
они не могли бить друг друга?
F : 1..8 1..8
Количество
ладей
Занимаемые места на
доске (1 в горизонтали
и 1 в вертикали)
P8 8! 40320

31.

32.

33.

34.

35. Размещение с повторениями из n элементов множества M по k - это всякая конечная последовательность, состоящая из k членов

данного множества M,
все k элементов которой не обязательно различны.
Два размещения с повторениями считаются различными,
если хотя бы на одном месте они имеют различные
элементы множества M.
k
k
An n
Возьмем буквы Б, А, Р. Какие размещения из этих букв, взятых по две,
можно получить?
Сколько таких наборов получиться, если буквы могут повторяться?
Получатся наборы: ББ, БА, БР, АА, АБ, АР, РР, РБ, РА.

36.

37.

n!
C
k!(n k )!
k
n

38.

k
A
n!
k n
Cn
Pk ( n k )! k !

39.

40.

Сколькими способами из колоды в 36 карт можно вытащить
5 карт так, чтобы среди них были три карты червовой масти
и две крестовой масти?
Решение.
Всего в колоде имеем по 9 карт каждой из 4
мастей. Три карты червовой масти можем вытащить
C3
9
способами, а две карты крестовой масти можно
вытащить
C2
9
способами.
По правилу произведения получаем, что существует
C 3 * C 2 способов вытащить из колоды 5 карт определенным
9
9
образом.

41.

42.

43.

44.

СОЧЕТАНИЯ с повторениями.
Пусть имеем неупорядоченное n-элементное множество А,
элементы которого разбиты на n классов (в каждом классе по 1
элементу), которые будут называться типами элементов.
Комбинацией из n элементов по k с повторениями называется
k -элементное подмножество, каждый элемент которого
принадлежит одному из n типов.
Совокупность таких комбинаций называют сочетаниями с
повторениями из n элементов по k.
44

45.

Есть n ящиков, в которых размещается k шариков.
Нас интересует только количество шариков в каждом
ящике.
То есть результатом эксперимента является набор чисел
k1 , k2 ,..., kn
, в котором k — число шариков в ящике с
i
номером i , и
k1 ... kn k
Числа
ki принимают натуральные значения или равны 0.
Изобразим результат такого размещения в виде схемы, в
которой вертикальные линии обозначают перегородки
между ящиками, а кружки
— находящиеся в ящиках
шарики:
45

46.

-размещение 9 шариков по 7 ящикам.
-Здесь 1-й ящик содержит 3 шарика, 2-й и 6-й ящики
пусты, 3-й и 7-й ящики содержат по одному шарику, и в 4м и 5-м ящиках есть по 2 шарика.
-Переложим один шарик из первого ящика во второй и
изобразим таким же образом еще один результат
размещения:
46

47.

И еще один:
Получим, что все размещения можно получить, меняя между
собой шарики и перегородки, или расставляя k шариков на
n-1+k месте.
Число n-1+k получается так: у n ящиков есть ровно n+1
перегородка, считая крайние,
или n-1 перегородка, если не считать крайние, которые двигать
нельзя.
И есть k шариков.
Перебрав все возможные способы расставить k шариков на
этих n-1+k местах (и ставя на оставшиеся места перегородки),
переберем все нужные размещения.
47

48.

Но способов расставить k шариков на n-1+k местах ровно
С nk 1 k— это в точности число способов выбрать из
n-1+k номеров мест
k номеров мест
(без учета порядка и без повторения), на которые нужно
поместить шарики.
Общее количество выборок в схеме выбора
k элементов из n с повторением и без учета порядка
определяется формулой
k
k
n 1
Cn Сn k 1 Cn k 1
48

49.

Задача. В магазине продается 4 сорта пирожных: бизе,
эклеры, песочные, наполеоны. Сколькими способами
можно выбрать 7 пирожных?
Решение. Каждая покупка – это выборка из 4 элементов
по 7, причем с повторениями, так как 4 < 7.
Порядок следования сорта пирожных внутри выборки
не важен. Следовательно, число таких покупок равно числу
всех сочетаний с повторениями:
10! 8 9 10
C C
120.
7! 3! 1 2 3
7
4
7
10

50.

Основные свойства сочетаний
m
n m
1. С n C n
m
m 1
m 1 ФОРМУЛА
2. Cn Cn Cn 1 СЛОЖЕНИЯ
n
ЧИСЛО ВСЕХ
k
n
ПОДМНОЖЕСТВ
3. С n 2
N-ЭЛЕМЕНТНОГО
МНОЖЕСТВА
k 0
ФОРМУЛА
СИММЕТРИИ
50

51.

Сnk
Ank
Ank
Сnk
51

52.

Перестановки с повторениями
Число различных перестановок, которые можно
построить из n элементов, среди которых находятся
n1 - элементов первого типа,
n2 - элементов второго типа,…,
nk - элементов k-го типа равно
n!
P ( n1 , n2 ,.., nk )
n1!n2!...nk !
n1 n2 nk n
52

53.

Число элементов в каждой перестановке равно
n1 n2 nk n
Поэтому если бы все элементы были различны,
то число перестановок равнялось бы n! . Но из-за того, что
некоторые элементы совпадают, получится меньшее число
перестановок. Возьмем перестановку
В которой сначала выписаны все элементы первого типа,
потом все элементы второго типа,…,наконец, все элементы
k-го типа. Элементы первого типа можно переставлять с
друг другом n1! способами. Но так как все эти элементы
одинаковы, то такие перестановки ничего не меняют. Точно
также ничего не меняют n2! перестановок второго типа и
53
т.д.

54.

Например, в перестановке «ммаа» ничего не изменится,
если переставит первый элемент со вторым, или третий
с четвертым.
Перестановки элементов первого типа, второго типа и
т.д. можно делать независимо друг от друга. Поэтому по
правилу произведения элементы нашей перестановки
можно переставлять друг с другом n1 n21 nk !
способами так, что она остается неизменной. То же
самое верно и для любого другого расположения
элементов.
Поэтому множество всех n! перестановок распадается
на части, состоящие из одинаковых перестановок
каждая. Значит число различных перестановок с
повторениями, которые можно сделать из данных
n!
элементов равно
P ( n1 , n2 ,.., nk )
n1!n2!...nk !
54

55.

55

56.

ПРИМЕР:
Сколько различных слов можно построить
перестановкой букв в слове «лаваш»?
Слово «лаваш» включает по одному экземпляру букв
«л», «в», «ш» и два экземпляра буквы «а», а общее
количество букв – 5.
По формуле находим:
5!
5 4 3 60
2! 1! 1! 1!
56

57.

Задача. У врача 3 таблетки одного лекарства,
2 таблетки – другого и 4 таблетки – третьего.
Сколькими способами он может распределить прием
имеющихся таблеток по одной в день?
Решение. Порядок приёма таблеток важен.
Есть повторяющиеся таблетки.
Общее число таблеток 3 + 2 + 4 = 9 равно числу дней
приема лекарств.
Решение задачи сводится к нахождению числа всех
перестановок с повторениями из 9 элементов:
9!
1 2 3 4 5 6 7 8 9 5 7 8 9
P(2,3,4)
1260.
2! 3! 4!
2 6 4!
2

58.

Задача. Сколько различных слов можно получить
перестановкой букв слова ОГОРОД так, чтобы три буквы
"о" не стояли бы рядом?
Решение. Общее количество различных слов,
полученных перестановкой букв слова огород, равно
6! 4 5 6
P(3,1,1,1)
120.
3!
1
Если в каком-то слове все три буквы "о" стоят рядом,
то тройную "о" можно считать единым символом, и
количество слов, в которых три буквы "о" стоят рядом,
равно Р(4) = 4! =24.
В итоге получаем: 120 - 24 = 96.

59.

Найти количество перестановок букв в слове КОЛОБОК .
P(7) 7!
В слове есть 3 буквы О и 2 буквы К, меняя их , не получим
новых слов. Так как P(3) 3! , P( 2) 2! ,
То можем получить всего
7!
420
3!2!
разных слов из слова КОЛОБОК