2024_Лекция_4_Комбинаторика

1. Лекция 4

Комбинаторика

2.

Комбинаторика
–
раздел
дискретной
математики,
посвящённый
решению
задач
выбора и расположения элементов
некоторого, как правило, конечного
множества
в
соответствии
с
заданными свойствами.
.

3.

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

4. Основные определения

Если М – конечное множество, которое
содержит n элементов, то будем его называть nмножеством и писать |М|=n.
Подмножество А М, которое содержит k
элементов, называется k-подмножествoм.
n-множество
X
называется
линейноупорядоченным, если каждому его элементу x
взаимно
однозначно
соответствует
номер
i {1,2,..,n}.
Взаимно-однозначное отображение f nмножества М нa себя называется подстановкой
(n-подстановкой).
4

5.

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

6.

7.

8.

Правило суммы
8

9. Правило суммы

Если первая задача может быть сделана n1
способами, а вторая – n2 способами, и если эти
задачи не могут быть сделаны одновременно, то
существует
n1 + n 2
способов сделать любую задачу.
9

10.

Правило суммы
Можно применять правило суммы более, чем
для 2 множеств.
Пусть задачи T1, T2, …,Tm могут быть сделаны n1,
n2, …, nm способами соответственно, и никакие 2 из
этих задач не могут выполняться одновременно.
Тогда количество способов выполнить любую из
задач определяется как
n1+n2+…+nm
10

11. Правило суммы

Пример
В городе находятся 4 технических ВУЗа, 1
медицинский и 2 гуманитарных. Сколькими способами
можно
получить
высшее
образование
по
государственному набору в данном городе?
Решение:
Поскольку государственный набор предполагает
бесплатное обучение только в одном ВУЗе, применимо
правило суммы, по которому число способов N выбора
ВУЗа определяется как: N = 4+1+2 = 7.
11

12. Правило суммы

Если множество М – это объединение множеств
М1, М2, …, Мk, которые не пересекаются попарно
(Mi Mj= ), тогда количество элементов множеств
связаны соотношением
| M | = | М1 | +…+ | Мk |
Пусть объект a1 может быть выбран m1
способами, объект а2 - m2 способами и т. д., объект ak mk способами. Тогда выбор объекта a1 или а2 и т.д.,
или ak может быть сделан m1 +m2+...+mk способами.
Пример
Раньше из Питера в Москву в течение суток
отправлялось 10 поездов, 3 автобуса и 2 самолета.
Всего способов выехать из Питера в Москву:
10+3+2
12

13.

Правило
произведения
13

14. Правило произведения

Пусть задача может быть разбита на 2 подзадачи.
Если первая подзадача может быть сделана n1
способами, а вторая – n2 способами, то существует
n1 ∙ n2
способов сделать эту задачу.
14

15. Правило произведения

Если М1, М2, …, Мk – конечные множества и
М=М1 М2 … Мk – их декартово произведение, то
| M | = | М1 | … | Мk |
Пусть объект a1 выбирается m1 способами, а2 –
m2 способами, и т.д., объект ak – mk способами, и
пусть выбор объекта a1 не влияет на число способов
выбора объектов a2,а3,...ak, выбор объекта а2 не влияет
на число способов выбора объектов a3,а4 ...аk, т.д.
Тогда выбор упорядоченного множества объектов
(a1,a2,...,ak) в указанном порядке можно осуществить
m1 ∙ m2 ∙ m3 ∙... ∙ mk способами.
15

16. Правило произведения

Пример
Имеются 4 научные темы, 3 студента и 2
преподавателя.
Исследовательскую
группу,
занимающуюся одной темой, составляет один студент
и один преподаватель. Сколько существует
комбинаций выбора различных тем и различных
исследовательских групп?
Решение:
Так как одна исследовательская группа может вести
только одну тему, применимо правило произведения,
по которому число комбинаций равно 4∙3∙2=24.
16

17. Правило произведения

Пример
Сколько различных битовых строк длинной 7
можно составить?
Каждый из 7 бит может быть выбран двумя
способами (0 или 1).
Получаем:
27=128
различных битовых строк длинной 7.
17

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

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

19.

20.

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

21.

Задача 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 способами. Всего 25+16=41 вариантов.

22.

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

23.

Формула включений-исключений (для двух
пересекающихся множеств) Формула включений и
исключений
Правило.
n(А) = а, n(В) = b, n(А В) = c
n(A B) = n(А) + n(В) - n(А В) = a + b - c
Обоснование: складывая элементы пересекающихся
множеств А и В, мы дважды считаем элементы,
принадлежащие их пересечению.

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

Сколько положительных целых чисел,
превышающих 1000, делятся на 7 или на 11?
не
A B A B A B
A
B
A B
1000 1000 1000
7 11 7 11
142 90 12
220
A 142
делится на 7
A B 12
B 90
делится на 11
24

25.

Задача. В школьной библиотеке содержатся книги с русскими
текстами, книги с английскими текстами, некоторые книги содержат
как английские, так и русские тексты. Известно, что из 590 книг в 500
есть тексты на русском языке, и в 100 книгах - английские тексты.
Сколько книг содержат тексты как на русском, так и на английском
языке? Сколько книг содержат тексты только на русском языке?
Сколько книг содержат тексты только на английском языке?
Дано:
Решение:
n(Р) = 500
1) А В ≠
n(А) = 100
n(A B) = n(А) + n(В) - n(А В)
n(P A) = 590 2) 590 = 500 + 100 - n(Р А)
n(Р А) = 10 (рус. и англ. книги)
Найти:
3) n(P\(P A)) = 500 – 10 = 490 (рус. книги)
n(P A) - ?
4) n(A\(P A)) = 100 – 10 = 90 (англ. книги)
n(P\(P A)) - ?
n(A\(P A)) - ? Ответ: 10, 490, 90

26.

27.

Объединение 3 пересекающихся множеств
Формула включений и исключений
Правило.
n(A В С)=n(А)+n(В)+n(С)-n(А В)-n(В С)-n(А С)+n(А В С)
Студенты первого курса, изучающие информатику в университете, могут
посещать и дополнительные дисциплины. В этом году 25 из них предпочли
изучать Питон, 27 выбрали СИ, а 12 решили заниматься java. Кроме того,
было 20 студентов, слушающих курс Питона и Си, 5 изучали Питон и java, а 3
— java и СИ. Известно, что никто из студентов не отважился посещать сразу
три дополнительных курса. Сколько студентов посещали по крайней мере
один дополнительный курс? Сколько студентов изучали только java?
Решение:
Дано:
n(А)=25, n(В)=27, n(С) =12 1) n(A B C) = 25 + 27 + 12 – 20 – 5 – 3 +0
n(A B C) = 36
n(A B)=20, n(A C)=5
2) x = 12 – 5 – 3 = 4 (только java)
n(B C)=3
n(A B C)=0
Ответ: 36, 4
Найти:
n(A B C) - ?

28.

VI. Формула включений и исключений
1) n(A B) = n(А) + n(В) - n(А В)
2) n(A В С)=
n(А)+n(В)+n(С)-n(А В)-n(В С)-n(А С)+n(А В С)
3) n(A В С D)=
n(А)+n(В)+n(С)+n(D)-n(А В)-n(А С)-n(А D)-n(В С)-n(В D)n(C D)+n(А В С)+n(А В D)+n(А С D)+n(В С D)n(А В С D)
4) …

29.

30.

31.

32.

Перестановки и
размещения
32

33. Перестановки

Пусть М={а1,а2,...,аn} – фиксированное
множество.
Упорядоченные
k-подмножества
(b1,b2,...,bk) множества M называются его
kперестановками.
Иными
словами, k-перестановка – это
размещение в определенном порядке k элементов из
множества М.
33

34. Размещения

Если в перестановке участвуют все элементы
множества (n-перестановка), то используют термин
перестановка и обозначается Pn .
Два размещения из n по k различны, если
они состоят из различных элементов или из
одинаковых, но расположенных в разном порядке.
k-перестановки множества из n элементов
называются размещениями из n по k элементов и
обозначается Ank .
34

35. Факториал

Компактное представление
последовательности целых чисел.
для
умножения
Применяем n! Для представления произведения
n·(n-1)·(n-2)·...·(2)·(1)
гле n – некоторое целое число.
0!=1
35

36.

37.

38.

n!
A
(n k )!
k
n

39. А –первая буква французского слова 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 )!

40. Размещения без повторений

Ank n(n - 1) ... (n - k 1)
n!
( n k )!
Пример
М = {1,2,3}.
2-перестановки
(1,2);(2,1);(1,3);(3,1);(2,3); (3,2);
3-перестановки
(1,2,3);(1,3,2);(2,1,3); (2,3,l); (3,1,2);(3,2,1).
40

41.

42. Задача 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

43. Размещения без повторений

Пример
Из группы в 25 человек требуется выбрать
старосту, заместителя старосты и профорга.
Сколько вариантов выбора руководящего состава
группы?
Решение: Старосту можно выбрать одним из
25 способов. Поскольку выбранный староста не
может быть своим заместителем, то для выбора
заместителя старосты остается 24 варианта.
Профорга выбирают одним из 23 способов. Всего
вариантов:
25!
23 24 25
13800
22!
43

44.

45. Перестановки без повторений

Ann
Если n=k, тогда
- количество всех
способов упорядочения этих элементов:
Pn Ann n!
Пример
М={1,2,3}
P3= 3!=3∙2∙1=6
45

46.

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

47.

48.

49. Перестановки без повторений

Пример
На кафедре защищаются дипломники А, В, С и D,
причем А и В имеют комплексную тему и В не
может защитить диплом после А. Сколькими
способами можно определить очередность защит?
Решение:
Так как В и А защищают одну тему, необходимо
рассматривать перестановки из трех элементов
Р3=3!=1∙2∙3=6
49

50. Круговые перестановки

Сколькими способами можно рассадить 5 детей за
круглым и за квадратным столом?
Рассмотрим случай, когда дети сидят за квадратным
столом:
A
C
После применения формулы для
количества перестановок получаем:
P(5,5) = 5!
нахождения
50

51. Круговые перестановки

Рассмотрим случай, когда дети
круглым столом :
A
(n-1)!
A
существует
C
D
D
C
B
A
D
A
Для n элементов
перестановок.
B
C
C
D
D
B
C
B
A
сидят за
круговых
51

52. Перестановки с повторениями

k-перестановкой с повторениями n-множества А
или k-перестановкой с повторениями из n элементов
будем называть упорядоченный набор k элементов
(bl,...bk) из множества М.
Пример
A={а,b,с}, |A|=3, Ma={a,a,...}, Mb={b,b,..}, Mc ={с,с,...}.
6-перестановками с повторениями из трех
элементов будут:
(а,b,с,a,a,a), (b,b,c,c,a,b), (c,b,b,c,a,a) и т.д.
52

53. Перестановки с повторениями

Две k-перестановки считаются равными, если
они совпадают как своими элементами, так и
порядком их расположения; и различными, если
они отличаются либо элементами, либо порядком
их расположения.
Пример
М – множество букв разрезной азбуки (все
буквы в азбуке строчные).
Различными 4-перестановками будут:
(м,а,м,а),(р,а,м,а), (н,а,а,а), (а,н,а,а), (а,а,а,н)
и т. д.
53

54. Размещения с неограниченными повторениями

k
n
A n
k
Пример
Сколько строк длиной n может быть
сформировано из букв английского алфавита?
По правилу произведения:
26n
строк длинной n.
54

55.

56.

57.

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

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

59.

60.

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

61.

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

62.

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

63. n-перестановки из n-множества с заданной спецификацией

P ( n ; n1 , n2 ,..., nk ) C C
n1
n
n2
n n1
n!
... C
n1 ! n2 !...nk !
nk
nk
Пример
Сколько слов можно составить из букв слова
“Миссисипи” (слова могут не иметь смысла)?
“м” встречается 1 раз,
“и” – 4 раза,
“с” -3 раза,
“п” - 1 раз
Р(9;1,4,3,1) =9!/(1!·4! ·3! ·1!)= 2520.
63

64.

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

65.

Задача. У врача 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

66.

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

67.

Сочетания
67

68. Сочетания

k-сочетаниями множества М (короче –
сочетаниями) называются неупорядоченные kподмножества {ai,аj,...,аs} множества M.
Два k-сочетания различны тогда и только
тогда, когда они отличаются хотя бы одним
элементом.
Пример
Различными 2-сочетаниями множества
М = {l,2,3 }:
{1,2},{1,3},{2,3}.
68

69.

70.

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

71.

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

72. Сочетания

Количество всех различных сочетаний из n
k
элементов по k обозначают C n :
k
A
n!
k
n
Cn
k ! ( n k )! k !
72

73. Сочетания

Пример
Пусть C = {a, b, c, d}
Количество 2-сочетаний из C равно
4 3 2 1
C
6
( 4 2 )! 2!
2
4
6 подмножеств: {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}.
73

74.

75. Сочетания

Пример
Комитет, который разрабатывает курс по дискретной
математики, должен состоять из 3 преподавателя
дискретной математики математики и 4 программиста.
Есть 9 преподавателей дискретной математики и 11
программистов.
Сколько существует способов сделать это?
После применения правила произведения получаем:
9! 11!
84 330 27720
C C
3! 6! 4! 7!
3
9
4
11
75

76. Свойства сочетаний

C C
k
n
C C
k
n
k 1
n 1
n k
n
C
k
n 1
C C ... C 2
0
n
1
n
n
n
n
76

77.

Сочетания с
повторениями
77

78. Сочетания с повторениями

Сочетаниями с повторениями из n элементов
по k называются неупорядоченные k-подмножества
множества
78

79. Сочетания с повторениями

Пример
А={a,b,с},
6-сочетаниями с
элементов будут:
{а,b,а,а,а,а},
{b,b,a,c,a,a},
{с,с,с,с,b,b} и т.д.
повторениями
из
трех
79

80.

81.

82.

83.

Доказательство. Каждое сочетание полностью
определяется, если указать, сколько элементов
каждого из n типов в него входит. Поставим в
соответствие каждому сочетанию последовательность
нулей и единиц, составленную по такому правилу:
напишем подряд столько единиц, сколько элементов
первого типа входит в сочетание, далее поставим 0 и
после него напишем столько 1, сколько элементов
второго типа входит в это сочетание и т.д.
Тогда сочетаниям из трех букв по две
соответствовать такие последовательности:
1001, 0101, 1010, 0110, 0011.
будут
1100,

84.

85. Сочетания с повторениями

Пример
У преподавателя есть карточки на четыре
различных варианта. Сколькими способами можно
выбрать шесть карточек?
9 8 7
C C C
84
1 2 3
6
4
6
9
3
9
85

86. Свойства сочетаний с неограниченными повторениями

k
k
C n C n k 1
k
k 1
k
C n C n C n 1
86

87.

88. Сочетание с повторением

В магазине есть 5 белых роз, 6 чайных, 4 жёлтых, 2
бордовых. Сколькими способами можно составить букет
из 9 роз?

89.

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

90. Сочетания и размещения «с» и «без» повторений

Тип
Размещение
Сочетание
Есть ли
повторения?
Формула
нет
n!
( n r )!
n!
( n r )! r !
нет
Размещение
да
nr
Сочетание
да
n r 1 !
r ! n 1 !
90

91.

92.

k
An
Сnk
Ank
Сnk
92