7 (2)

1.

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

2. Проблемы комбинаторного анализа

Задачи на перечисления, в которых необходимо
определить количество размещений элементов
конечного
множества,
удовлетворяющих
определенным условиям;
Задачи о существовании и построении
Задачи о выборе
2

3. Магический квадрат

Разместить числа 1,2,3,4,5,6,7,8,9 в виде
квадрата так, чтобы сумма чисел из каждого из
столбцов, строк и диагоналей была одинакова.
4
3
8
9
5
1
2
7
6
3

4.

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

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

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

6.

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

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

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

8.

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

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

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

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

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

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

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

12.

13.

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

14.

Набор элементов xi1,…, xik из множества X={x1, …, xn}
называется выборкой объема k из n элементов или,
иначе, (n, k)-выборкой.
Выборка называется упорядоченной, если задан
порядок следования элементов в ней. Две
упорядоченные выборки, различающиеся лишь
порядком следования элементов, считаются
различными.
Если порядок следования элементов в выборке не
является существенным, то такая выборка называется
неупорядоченной.
14

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

Перестановкой без повторений из n элементов
называется всякий упорядоченный набор из этих
элементов.
Пример
М={1,2,3}
P3= 3!=3∙2∙1=6
15

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

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

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

Размещением без повторений из n элементов по k
называется упорядоченный набор из k различных
элементов некоторого n-элементного множества
(упорядоченная (n, k)-выборка без возвращений
называется). Перестановка также является размещением
из n элементов по n.
Число различных размещений (без повторений) из n
элементов по k обозначается и вычисляется по формуле
k
An n(n-1) ... (n-k 1)
n!
(n k )!
17

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

Пример
М = {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).
18

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

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

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

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

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

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

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

Перестановками с повторениями из n элементов по k
называется упорядоченное подмножество из k
элементов n-элементного множества, в которой
каждый элемент множества встречается ki раз
(причем, k1+k2+...+kn=k). Число перестановок с
повторениями обозначается
Пример
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) и т.д.
22

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

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

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

P(k1 , k 2 ,...,k k ) Cnk1 Cnk 2 k ... Ckkn
1
n
n!
k1!k 2 !...k k !
Пример
Сколько слов можно составить из букв слова
“Миссисипи” (слова могут не иметь смысла)?
“м” встречается 1 раз,
“и” – 4 раза,
“с” -3 раза,
“п” - 1 раз
Р(9;1,4,3,1) =9!/(1!·4! ·3! ·1!)= 2520.
24

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

P ( n ; n1 , n2 ,...,nk ) C C
n1
n
n2
n n1
n!
... C
n1 ! n2 !...nk !
nk
nk
25

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

Размещением с повторениями из n элементов по k
называется упорядоченный набор из k элементов
некоторого n-элементного множества, среди которых
могут быть одинаковые элементы (упорядоченная (n,
k)-выборка с возвращением). Число элементов
каждого вида неограниченно.
Число различных размещений с повторениями из
n элементов по k обозначается Akn и вычисляется по
формуле
k
k
An n
26

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

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

28.

Сочетания
28

29. Сочетания

Сочетанием без повторений из n по k
называется неупорядоченный набор k элементов,
выбранных из данных n элементов
(неупорядоченная (n, k)-выборка без возвращения).
Наборы, отличающиеся только порядком
следования элементов (но не составом), считаются
одинаковыми, этим сочетания отличаются от
размещений.
Количество всех различных сочетаний (без
повторений) из n элементов по k обозначают C nk
или n
k
k
n
A
n!
k
n
Cn
k k! (n k )!k!
29

30. Сочетания

Пример
Различными 2-сочетаниями множества
М = {l,2,3 }:
{1,2},{1,3},{2,3}.
30

31. Сочетания

Пример
Пусть 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}.
31

32. Сочетания

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

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

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
33

34.

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

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

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

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

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

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

А={a,b,с},
{а,b,а,а,а,а}, 11111010
{b,b,a,c,a,a}, 11101101
{с,с,с,с,b,b} 01101111
37

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

Имеются предметы п различных видов. Число элементов
каждого вида неограниченно. Сколько существует расстановок
длины k, если не принимать во внимание порядок элементов?
Такие расстановки называют сочетаниями с повторениями,
количество и обозначение которых следующее:
C C
k
n
k
n r 1
n k 1 !
k ! n 1 !
38

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

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

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

k
k
C n C n k 1
k
k 1
k
C n C n C n 1
40

41.

41

42.

Бином Ньютона
42

43. Бином Ньютона

Биномиальная теорема:
Для произвольного положительного целого числа n
справедливы равенства:
n
( a b ) C a b
n
r 0
r
n
r
n r
n
C a
r 0
r
n
n r
b
r
43

44. Бином Ньютона. Пример

Получить разложение
( 2 x 3 y 2 )3
C 30 ( 2 x )3 C 31 ( 2 x )2 ( 3 y 2 )1
C 32 ( 2 x )1 ( 3 y 2 )2 C 33 ( 3 y 2 )3
8 x 3 x 3 y 3 2 x 9 y 27 y
3
2
2
4
6
8 x 3 36 x 2 y 2 54 xy 4 27 y 6
44

45.

n
Пример: Доказать тождество
C 2
k 0
k
n
n
Решение: Воспользуемся формулой бинома Ньютона, в
которой положим, а = 1 и b = 1, тогда
n
( 1 1 ) C 1 1
n
k 0
k
n
k
n k
45

46. Треугольник Паскаля

C 00
C10
C 20
C 30
C 40
C 50
C 21
C31
C41
C51
C11
C 22
C 32
C 42
C 52
C 33
C 43
C 53
C 44
C 54
C 55
C nr 11
C nr 1
C nr
Каждый из внутренних элементов треугольника
равен сумме двух элементов расположенных над ними.
46

47. Треугольник Паскаля

(n+1) ряд треугольника состоит из коэффициента
разложения (a+b)n
1
1
1
1
2
3
1
1
1
3
6
4
5
1
10
1
4
10
1
5
1
47

48. Полиномиальная формула

49. Полиномиальная формула

50. Полиномиальная формула

51.

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

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

Пусть даны N объектов (предметов), каждый
из которых может обладать или не обладать одним
или несколькими из свойств a1,a2,...,an .
/
Через ai обозначим отсутствие свойства ai;
через N(a) –
количество предметов,
обладающих свойством а (а – любое из свойств аi
или ai/ );
через N(a,b,c,…,k) – количество предметов,
обладающих попарно различными свойствами
а,b,c,..,,k
52

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

Если все свойства ai попарно не
совместимы (т.е. N(aiak)=0 при i k), то
формула имеет вид:
/
/
N ( a1 ...a n ) N
N ( ai )
1 i n
53

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

) N N ( ai )
/ /
N ( a1 a 2 ) N N ( a1 ) N ( a 2 ) N ( a1a 2 )
Тогда, очевидно, N ( a
/
i
т.к. при вычитании N(а1) и N(a2) из общего числа
предметов число N(ala2) вычитается дважды.
54

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

N ( a a a ) N N ( a1 ) N ( a2 ) N ( a3 )
/
1
/
2
/
3
N ( a1a2 ) N ( a1a3 ) N ( a3 a2 ) N ( a1a2 a3 )
a1 a 2
a1
a2
a1 a3
a 2 a3
a1 a 2 a 3
a3
55

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

При произвольном n справедлива формула
включений и исключений:
N ( a a ...a ) N N ( ai )
/
1
/
2
/
n
1 i n
N ( a a ) ... ( 1 ) N ( a a ...a )
n
1 i j n
i
j
1 2
n
56

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

Сколько положительных целых чисел,
превышающих 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
57

58.

Задачи о встречах и
беспорядках

59.

Формулы включений и исключений.
Задача о беспорядках
59

60. Задача о беспорядках

60

61. Задача о встречах. Формулировка

61

62. Задача о встречах.

62