Лекционный курс в ворде

Глава 1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

§1.Элементы теории множеств

Множество-это совокупность объектов определенной природы.

Для обозначения множеств используют заглавные буквы A,B…,

для обозначения элементов множеств используют прописные буквы

a,b…

a A(a принадлежит множеству A)

а А(a не принадлежит множеству A)

Существуют стандартные обозначения:

N -множество натуральных чисел

Z -множество целых чисел

Q -множество рациональных чисел

R -множество действительных чисел

C -множество комплексных чисел

-пустое множество

Если множество А В, то А В(А является подмножеством В)

Если А В и В А ,то А=В

1.Сложение множеств

Сложением двух множеств A B является множество, которое состоит из всех элементов А или В

В теории множеств действует правило сложения: если элемент a A может быть выбран k способами, а b В – c способами ,то элемент “ a или b ” может быть выбран k+c способами.

Пусть А и В конечные множества(содержат конечное число элементов) и

n(A)=n ^A , n(B)=n ^B , A B=

n(A B)= n ^A + n ^B

если множества А и В пересекаются A B , то

n(A B)= n ^A + n ^B - n(A B) -формула перекрытия

пример 1:

n(A)=9 , n(B)=8

n(C)= n(A B)=9+8-3=14

пример 2:

n(A)=6 , n(B)=7 , n(C)=7

n(A B C)= n ^A + n ^B +n ^C – n(A B)- n(A C)- n(B C) + n(A B C)=

=6+7+7-2-2-2+1=15

2.Разность множеств

Разностью двух множеств A \ B=C является множество состоящее из тех элементов А, которые В

A B= A \ B=A

3.Произведение(пересечение) множеств

если A B

Введем понятие декартово произведения двух множеств

пусть А и В

А={a₁,a₂,…,a_m},

B={b₁,b₂,…,b_n}

A B - декартово произведение это тоже множество состоящее из

всевозможных пар (a _i , b _j), i (1…m), j (1…n)

количество таких пар равно m n

это правило обобщается на любое число конечных множеств

A₁, A₂,…, A _k

n₁, n₂,…, n _k

A₁* A₂*…* A _k состоит из всевозможных наборов длинной k.

Введем понятия дополнения к множеству

Если A U, то U \ A = А – дополнение к множеству А

A А=U

Множество А называют счетным, если его элементу можно поставить в соответствие натуральное число или пронумеровать его элементы.

Счетные множества могут быть как конечные, так и бесконечные .

§2. Основные правила комбинаторики

Комбинаторика-раздел математики, который решает задачи о выборе и размещении элементов некоторого множества. Древнейшей задачей комбинаторики была задача о магическом квадрате - расстановка первых n²

Натуральных чисел по строкам и столбцам квадрата, так чтобы сумма чисел по вертикали, горизонтали и диагонали была одинакова(постоянна)

4 9 2

3 5 7

8 1 6

Действуют те же правила сложения и умножения.

Правило сложения: если A₁, A₂,…, A _m не зависимы, причем A₁ можно выполнить K₁ способами, A₂ – K₂ способами,…, A _m - K_m способами,

то

A₁ A₂ … A _m можно выполнить K₁ +K₂ +…+K_m способами

В случае……

Если A₁ можно выполнить K₁ способами, A₂ – K₂ способами,…, A _m - K_m способами, то

A₁ A₂ = A₁*A₂ можно выбрать K₁*K₂ способами

пример 1:

Найти количество четных трехзначных чисел состоящих из цифр 0,1,2,3,4,5,6

A_2* A_1* A₀ = A₂*100 + A₁*10 + A₀

6*7*4

пример 2:

В розыгрыше принимают участие 18 номеров. Определить количество вариантов распределения 1,2 и 3 мест

1 2 3

18 17 16

Количество вариантов = 18*17*16

§3. Основные задачи комбинаторики

При выборе m элементов из n элементов мы имеем дело с соединением m элементов из n элементов.

В комбинаторике различают 3 вида соединения:

без повтора

размещение

с повтором

без повтора

перестановка

с повтором

без повтора

сочетание

с повтором

Размещение-соединение m элементов из n ….. либо порядком ,либо составом

Рассмотрим задачу о числе размещений без повтора, то есть каждое соединение не содержит одинаковых элементов

Такие соединения мы выбираем из n различных элементов и m ≤n

Число таких размещений A

m мест, на первое место элементы можно поставить n способами, на второе (n-1)способами,…,на последнее (n-m+1)

A = n(n-1)(n-2)…(n-m+1)

A = =

пример 1:

Найти количество семизначных телефонных номеров без повтора цифр

A = = =4*5*6*7*8*9*10=604800

пример 2:

выпишем все размещения с повтором из a,b,c,d по 2

(ab),(ba),(ac),(ca),(ad),(da),(bc),(cb),(bd),(db),(cd),(dc)

(aa),(bb),(cc),(dd)

Для количества размещений с повтором используем Ã

à =16= 4 ²

m=k A =n ^k

m=k+1 A =n ^k+1

для размещения с повтором

m<n , m=n ,m >n

пример 3:

Буквы азбуки Морзе(· ─) n=2.Найти количество возможных букв, при условии, что каждая состоит не более чем из 5 символов.

Каждая буква-размещение с повтором

à =2 à =4 à =8 à =16 à =32

Перестановка

Соединение n конечных элементов и отличающихся только порядком, называется перестановкой без повтора.

Перестановка без повтора- размещение из n по m

P = A =n!

Введем понятие перестановки с повтором

n₁-1го типа

n₂-2го типа

n₁ + n₂ +…+n _k =n

P _n (n₁ ,n_2, …,n _k )=

Найдем количество таких перестановок. Возьмем каждую перестановку с повтором

n₁ !

n₂ !

…

n _k !

P _n (n₁ ,n_2, …,n _k )=n!

пример 4:

Сколько различных гирлянд можно составить из 3 зеленых и 5 красных лампочек?

n₁=3

n₁=5

n₁=8

P₈(3,5)=

Сочетание

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

C

Если в каждом соединении выподает всего перестановки, то получим число размещений без повтора

P _m C = A C ₌

C =

пример 4:

Составить сочетания из 4 элементов без повтора a,b,c,d

ab, ac, ad, bc, bd, cd

C =4!/(2!*2!)=6

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

1.С =С m ≤ n

=

С =C =

2.Рекурентная формула

С +С = С

+ = = =

= С

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

n=0 С

n=1 С С

n=2 С С С

n=3 С С С С

n=4 С С С С С

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

Сочетание называется биномиальными, так как они являются коэффициентами разложения бинома Ньютона

(а+b)²=a ⁿ +n*a ^n-1 *b+ +…+

+ +…+ b ⁿ

С a ⁿ + С a ⁿ b+ С a ^n-2 b ² +…+ С a ^n-m b ^m +…+ С b ^m

Коэффициенты бинома Ньютона обладают симметрией относительно середины этого ряда

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

Сочетание из n элементов по m с повтором называется соединения содержащие m элементов, причем каждый элемент может входить любое число раз не более m (порядок элемента в таких соединениях не имеет значения)

пример 1:

Составить из двух элементов a и b сочетания по 3 элемента

aaa, bbb, aab, abb

В таких сочетаниях m может принимать любые значения. Таких сочетаний с повтором

С (m)= С

n=2, m=3

С = С = 4

пример 2:

В кондитерской имеются пирожные 5 типов. Сколько различных наборов можно составить из четырех пирожных.

Если в наборах будут различные пирожные, то число таких наборов будет

С = С =5

А если в наборах будут одинаковые пирожные, то число таких наборов будет

С (4)= С = =70

Глава 2. Случайные события.

Введение

Возникновение теории вероятности, как раздела математики, относится к 17 веку и связано с именами Ферма, Бернулли, Гюйгенса. Первоначально вопросом теории вероятности было изучение массовых явлений на основе карточных игр, страхования. Эти задачи решались с применением комбинаторики и арифметики. С развитием в теории вероятности возникают теория стрельб, теория ошибок, проблемы статистики, требующие развития математического аппарата. В теории вероятности появляется дифференциальное и интегральное исчисление. Эти разделы теории вероятности связаны с именами Гаусса, Лапласа, Чебышева, Маркова.

За последние десятилетия возникли новые разделы: теория надежности, теория игр, теория массового обслуживания.

§1.Основные понятия теории вероятности.

1.Достоверные, невозможные и случайные события.

Событие – всякий факт, который может произойти или нет при испытании (опыте).

Пример: Кидают игральную кость. Событие – выпадение четного числа. Каждое событие имеет вероятность, то есть каждое событие можно связать с числом, показывающим вероятность появления данного события.

При кидании кости степень возможности выпадения четного числа равна 50% или 1/2.

Степень возможности называется вероятное события, если события обозначаются заглавными буквами ( А,В,С, D ), то события обозначаются Р(А), Р(В).

Установим меру достоверности события.

Введем понятие достоверности события U и определим его вероятность Р( U ) =1.

Введем понятия невозможного события (если в результате испытаний события никогда не произойдет).

При бросании монеты она никогда не встанет на ребро и вероятность события = 0. Р(О)=0

Тогда событие которое может произойти или не произойти в результате испытаний называется случайными, а его вероятность 0<Р(А)<1.