Комбинаторика. Лекция1_комбинаторика-1. Лекция 1. Комбинаторика Комбинаторика изучает число комбинаций, которое при определенных условиях можно получить из конечного числа элементов произвольной природы

Название	Лекция 1. Комбинаторика Комбинаторика изучает число комбинаций, которое при определенных условиях можно получить из конечного числа элементов произвольной природы
Анкор	Комбинаторика
Дата	10.09.2022
Размер	381.06 Kb.
Формат файла
Имя файла	Лекция1_комбинаторика-1.pdf
Тип	Лекция #669886

1
Лекция №1. Комбинаторика
Комбинаторика изучает число комбинаций, которое при определенных условиях можно получить из конечного числа элементов произвольной природы.
Перестановками называют комбинации, состоящие из одних и тех же
n
элементов и отличающиеся их порядком. Если указанные
n
элементов различны, то число перестановок можно подсчитать по формуле:
P
n
= n!,
где
n !=
1 2 3...(
1)
n
n
 
 
Пример 1.
В некотором городе четыре тысячи домов. Каждый дом имеет номер, являющийся перестановкой разных символов. Сколько символов в номере дома? Сколько домов дополнительно можно обозначить номерами такой же длины?
Если в номере дома 3 символа, то ими можно занумеровать
3 1 2 3 6
P
   
домов.
Маловато получается. Если возьмем 6 символов, то
6 6! 1 2 3 4 5 6 720
P
       
. Опять не хватило символов. Если возьмем 7 символов, то
7 7! 720 7 5040
P
 
 
. Этого числа символов нам хватит для нумерации наших четырех тысяч домов, и еще останется
1040
дополнительных номеров.
Если указанные
n
элементов не являются различными и среди них имеется
n
1 элементов первого рода,
n
2 элементов второго рода и так далее
n
k
элементов k–го рода, то число
перестановок с повторениями равно
P
n
(n
1
,n
2
,…,n
k
)=
1 2
!
!
! ...
!
k
n
n n
n

 
Пример 2.
Сколько «слов» можно составить из букв слова «галактика»? Здесь имеем перестановки с повторениями.
9!
(1;1;1;1;2;3)
30240 1!1!1!1!2!3!
P


Размещениями называют комбинации, составленные из
n
элементов по
m
элементов, различающиеся либо составом элементов, либо их порядком. Если взятые элементы не возвращаются, то формула для подсчета комбинаций имеет вид:
!
(
)!
n
n
A
n
m


. Если взятые элементы возвращаются, то имеем размещения с повторением:
m
n
A
n

Пример 3.
Спортпрогноз. Пусть требуется назвать тройку призеров чемпионата России по футболу (18 команд). Исход данного эксперимента - выборка объема 3 без повторений, в которой важен порядок. Действительно, на первом месте может оказаться команда «Динамо», на втором –
«Зенит», на третьем – команда «Спартак» из Москвы. В данном примере имеем размещения без повторений. Число таких троек таково:
3 18 18!
1896 15!
A


Сочетаниями называют комбинации, составленные из
n
элементов по
m
элементов, в которых порядок не важен. Если взятые элементы нельзя возвращать, то имеем сочетания без повторений. В этом случае формула для подсчета числа сочетаний с повторениями имеет вид:

2
!
!(
)!
m
n
n
C
m n
m


. Если взятые элементы можно возвращать, то имеем сочетания с повторениями, формула для подсчета которых такова:
1
m
m
n
n m
C
C
 

Пример 4.
В группе 24 студента. Из деканата позвонили и сняли с занятий три человека для проведения тестирования. Сколько троек студентов можно составить? В данном примере имеем сочетания без повторений, поэтому число таких троек студентов равно:
3 24 24!
2024 3!(24 3)!
C



Пример 5.
В магазине продают
CD
RV

диски четырех различных скоростей. Я могу купить 5 дисков, все равно каких. Сколько вариантов покупки? В этой задаче мы имеем сочетания (порядок не важен) с повторениями. Число комбинаций в этом случае будет таким:
5 5
4 4 5 1 8!
56 5!3!
C
C
 



Замечание. В математике принято считать, что
(0)! 1

Подсчет числа комбинаций для гипергеометрического распределения.
Пусть имеется
n
1 элементов первого рода,
n
2 элементов второго рода и так далее
n
k
элементов k–го рода, причем
1 2
k
n
n
n
n

 

. Из них наудачу выбирают
r
объектов.
Число комбинаций (таких, что среди этих
r
объектов будет
1
r
- первого рода,
2
r
- второго рода,
….,
k
r
-
k
-того рода) равно:
1 2
1 2
k
k
r
r
r
n
n
n
C
C
C
C


 
Пример 6.
В группе двенадцать студентов, среди которых восемь отличников. По списку наудачу отобраны девять студентов. Сколько будет вариантов таких, что среди них шесть отличников?
В данном примере 12 = 8 (отличников) + 4 (других). Нужное число вариантов будет таким:
6 3
8 4
8!
4!
112 6! 2! 3!1!
С С С





При решении задач комбинаторики часто используют следующие правила:
Правило суммы. Если некоторый объект
A
может быть выбран из совокупности объектов
m
способами, а объект
B
может быть выбран
n
способами, то либо объект
A
, либо объект
B
можно выбрать
m
n

способами.
Пример 7.
В ящике 6 груш, 4 яблока, 3 киви и 7 мандаринов. Сколькими способами можно выбрать один фрукт? Ответ очевиден: 6+4+7+3=20 - задача на правило суммы.
Правило произведения. Если некоторый объект
A
может быть выбран из совокупности объектов
m
способами, а после этого объект
B
может быть выбран
n
способами, то пара объектов
( ; )
A B
может быть выбрана
m n

способами.
Пример 8.
На каникулы школьник получил задание выучить доказательство одной из 6 теорем, прочитать один из семи романов, написать сочинение по одной из четырех тем. Сколькими способами можно выполнить задание? Легко увидеть, что эта задача на правило произведения, а число способов подсчитаем так:
6 7 4 168
  

3
Теория вероятностей.
Первые работы по теории вероятностей связаны с попытками создания теории азартных игр (Кордано, Ферма, Гюйгенс, Паскаль - XVI – XVII века). Следующий период ознаменовался работами Якоба Бернулли (1654-1705), доказавшего теорему, которую сейчас называют «Закон больших чисел». Далее значимые результаты были получены математиками Муавром, Лапласом,
Гауссом, Пуассоном. Дальнейший период был связан с работами российских математиков
(девятнадцатый век) П. Л. Чебышева, А. А. Маркова. В двадцатом веке важные результаты были получены советскими математиками А. А. Колмогоровым и А. Я. Хинчиным.
Классическая теория вероятностей.
Опр. 1. Каждый из возможных результатов испытания назовем элементарным исходом в предположении, что элементарные исходы несовместны, равновозможны и образуют полную группу.
Опр. 2. Те элементарные исходы, в которых интересующее нас событие наступает, назовем благоприятствующими этому событию.
Опр. 3. Вероятностью события
A
назовем отношение числа благоприятствующих этому событию исходов к общему числу всех равновозможных несовместных элементарных событий, образующих полную группу:
m
P
n

, здесь
m
- благоприятные исходы,
n
- общее число исходов.
Опр. 4. Достоверное событие – это событие, которое должно произойти при каждом испытании.
Опр. 5. Невозможное событие – это событие, которое не может произойти ни в одном испытании.
Свойство вероятности
Свойство 1. Вероятность достоверного события равна единице. Действительно, в этом случае
m
n

Свойство 2. Вероятность невозможного события равна нулю. В этом случае
0
m

Свойство 3. Так как
0
m
n
 
, то для любого события вероятность заключена между нулем и единицей:
0
( ) 1
P A


Статистическая частота
Опр. 6. Относительной частотой события
A
называют отношение числа испытаний, в которых событие
A
появилось, к общему числу фактически произведенных испытаний:
( )
m
W A
n

(
m
- число испытаний, в которых
A
появилось;
n
- общее число испытаний).
Замечание 2. Вероятность вычисляется до опыта, относительная частота – после опыта.
Пример. Отдел технического контроля обнаружил три нестандартных детали в партии из
80 деталей:
3
( )
80
W A

Если производят достаточное число опытов, то относительная частота изменяется мало, колеблясь около некоторого постоянного числа. Оказалось, что это постоянное число и есть вероятность события.

4
Пример. Производят многократное бросание монеты. Вероятность появления «герба» равна 0,5.
При 4040 бросаний отклонение относительной частоты от 0,5 было 0,0069; а при 24000 бросаний – лишь 0,0005.
Статистическое определение вероятности
Опр. 7. В качестве статистической вероятности принимают или относительную частоту, или число, близкое к ней (причины: невозможно произвести бесконечное число испытаний; трудно проверить несовместность и равновозможность исходов).
Свойства статистического определения вероятности
Для достоверного события
( ) 1
W D

; для невозможного события
( )
0
W N

; для любого события
0
( ) 1
W A


Для существования статистической вероятности события
A
требуется: 1) возможность хотя бы в принципе проводить бесконечное число испытаний; 2) устойчивость относительных частот в различных сериях достаточно большого числа испытаний.
Недостаток. Неоднозначность статистической вероятности:
0,4 0,39 0,41


.