kombinatorika_lektsia

Перестановки. Сочетания. Размещения.

Комбинаторика
Комбинаторикой называется раздел математики, в котором исследуется, сколько различных комбинаций (всевозможных объединений элементов), подчиненных тем или иным условиям, можно составить из элементов, принадлежащих данному множеству.
Слово «комбинаторика» происходит от латинского слова combinare, которое означает «соединять, сочетать».
Термин "комбинаторика" был введён знаменитым Готфридом Вильгельмом Лейбницем, - всемирно известным немецким учёным.

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

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

n! = n(n-1)(n-2)*…..*2*1, где n - натуральное число
Принято считать, что 0! = 1
ПОНЯТИЕ ФАКТОРИАЛА
Пример:
Произведение всех натуральных чисел от n до 1 называют n-факториал и обозначают n!

Решить уравнение:
Решаем квадратное уравнение, получаем:
Ответ:
ПОНЯТИЕ ФАКТОРИАЛА
Пример:
Решение:
-6 посторонний корень, так как n натуральное число

Проверьте себя.
Вычислите:

Ответы
1) 42
2) 3003
3)

Решаем самостоятельно (1 вариант – нечетные варианты, 2 – четные)
1 вариант
1
2
3
2 вариант
1
2
3

Проверяем:
1 вариант
100
8,25
48,2
2 вариант
1) 2015
2) 40
3) 1,1

Различают три вида соединений:
размещения, перестановки и сочетания.
Размещения
Размещениями называют различные комбинации из объектов, которые выбраны из множества различных объектов, и которые отличаются друг от друга как составом объектов в выборке, так и их порядком.
Определение: Пусть имеется множество, содержащее m элементов. Каждое его упорядоченное подмножество, состоящее из n элементов называется размещением из m элементов по n элементов.

Размещения
Количество размещений рассчитывается по формуле:
А теперь решим задачу для случая m=8, n=3:

Решим задачу:

Сочетания
Сочетаниями называют различные комбинации из объектов, которые выбраны из множества различных объектов, и которые отличаются друг от друга хотя бы одним объектом. Иными словами, отдельно взятое сочетание – это уникальная выборка из элементов, в которой не важен их порядок (расположение). Общее же количество таких уникальных сочетаний рассчитывается по формуле .
Определение: Пусть имеется множество, состоящее из m элементов. Каждое его подмножество, состоящее из n элементов называется сочетанием из m элементов по n элементов.

Сочетания

Решим задачу

Перестановки
Перестановками называют комбинации, состоящие из одних и тех же различных объектов и отличающиеся только порядком их расположения.
Определение: Размещения из m элементов по m элементов называются перестановками из m элементов.

Перестановки
Количество всех возможных перестановок выражается формулой
Рm=m!
Решим задачу для m=4
P4=4!=4*3*2*1=24

Решаем задачу:
Сколько шестизначных чисел, кратных пяти можно составить из цифр 1,2,3,4,5,6 при условии, что в числе нет одинаковых цифр.
Решение: при составлении подмножеств мы будем использовать сразу все шесть цифр. Важен лишь их порядок. Так как число кратно 5, то на последней позиции должна стоять цифра 5 или 0. Нуля нам не предлагают, поэтому числа должны оканчиваться цифрой 5. Поэтому переставлять местами мы может только первые пять цифр.
P5= 5! = 5*4*3*2*1 = 120 (чисел)

Задания для самопроверки
Выбрать и решить задачи, где рассматривается комбинация ПЕРЕСТАНОВКИ,СОЧЕТАНИЯ, РАЗМЕЩЕНИЯ
Изменяя порядок слов: руки, мою, я, составьте всевозможные предложения.
Сколькими способами в игре «спортлото» можно выбрать 6 номеров из 49?
Сколькими способами можно выбрать 2 буквы из слова "конверт"?
Из коллектива работников в 25 человек нужно выбрать председателя, заместителя, бухгалтера и казначея. Каким количеством спосо­бов это можно сделать?
Сколько существует способов выбора трёх ребят из 4-х желающих дежурить в столовой?
На собрании пожелали выступить 5 человек – Иванов, Петров, Сидоров, Белочкин и Пеночкин. Сколькими способами можно составить список ораторов?
Сколько экзаменационных комиссий, состоящих из 3 человек, можно создать из 5 преподавателей?
Сколько различных трехзначных чисел, в каждом из которых все цифры различны, можно составить из цифр 1, 2, 3, 4?
Сколько различных четырехзначных чисел, в каждом из которых все цифры различны, можно составить из цифр 1, 2, 3, 4?
Сколькими способами можно составить расписание на день из 4 различных уроков, если изучается 10 предметов?
Сколькими способами можно записать в виде произведения простых множителей число 30?
В хирургическом отделении работают 40 врачей. Сколькими способами из них можно образовать бригаду в составе хирурга и ассистента?

Проверяем себя

ПЕРЕСТАНОВКИ
1 Изменяя порядок слов: руки, мою, я, составьте всевозможные предложения.
На собрании пожелали выступить 5 человек – Иванов, Петров, Сидоров, Белочкин и Пеночкин. Сколькими способами можно составить список ораторов.
9 Сколько различных четырехзначных чисел, в каждом из которых все цифры различны, можно составить из цифр 1, 2, 3, 4?
11 Сколькими способами можно записать в виде произведения простых множителей число 30?

СОЧЕТАНИЯ
2 Сколькими способами в игре «спортлото» можно выбрать 6 номеров из 49?
3 Сколькими способами можно выбрать 2 буквы из слова "конверт"?
5 Сколько существует способов выбора трёх ребят из 4-х желающих дежурить в столовой?
7 Сколько экзаменационных комиссий, состоящих из 3 человек, можно создать из 5 преподавателей?

РАЗМЕЩЕНИЯ
4 Из коллектива работников в 25 человек нужно выбрать председа­теля, заместителя, бухгалтера и казначея. Каким количеством способов это можно сделать?
8 Сколько различных трехзначных чисел, в каждом из которых все цифры различны, можно составить из цифр 1, 2, 3, 4?
10 Сколькими способами можно составить расписание на день из 4 различных уроков, если изучается 10 предметов?
12 В хирургическом отделении работают 40 врачей. Сколькими способами из них можно образовать бригаду в составе хирурга и ассистента?

Ответы
Я мою руки. Руки мою я. Мою я руки. Я руки мою. Руки я мою.
Мою руки я. = 6
С499 = 1383816
3. С72 = 21
4. А254 = 303600
5. С43 = 4
6. Р5 = 120
7. С73 = 35
8. А43 = 24
9. Р4 = 24
А 104 = 30240
11. Р3 = 6
А402 = 1560

Проверь себя
1.Определите вид соединений:
а) Соединения из n элементов, отличающиеся друг от друга только порядком расположения в них элементов, называются __________
б) Соединения из m элементов по n, отличающихся друг от друга только составом элементов, называются _______________
в) Соединения из m элементов по n, отличающихся друг от друга составом элементом и порядком их расположения, называются _________

2.Восстановите соответствие типов соединений и формул для их подсчёта

Задача
Встретились несколько друзей и все обменялись рукопожатиями. Всего было сделано 15 рукопожатий. Сколько встретилось друзей?

Исторические сведения
Комбинаторика как наука стала развиваться в XIII в. параллельно с возникновением теории вероятностей.
Первые научные исследования по этой теме принадлежат итальянским ученым Дж. Кардано, Н. Чарталье (1499-1557), Г. Галилею (1564-1642) и французским ученым Б.Пискамо (1623-1662) и П. Ферма.
Комбинаторику, как самостоятельный раздел математики, первым стал рассматривать немецкий ученый Г. Лейбниц в своей работе «Об искусстве комбинаторики», опубликованной в 1666г. Он также впервые ввел термин «Комбинаторика».

Леонард Эйлер
1707-1783
Готфрид Вильгельм Лейбниц
1646-1716
Блез Паскаль
1623-1662
Пьер Ферма
1601-1665
Первые научные исследования по комбинаторике принадлежат: