Основные понятия комбинаторики. Лекция.

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

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

Комбинаторные задачи делятся на: задачи на перестановки, задачи на размещение, задачи на сочетание.

Определение: Факториал – это произведение всех натуральных чисел от 1 до n.

Обозначение: n! = 1 · 2 · 3 · ... · n.Читается: «эн факториал».

Пример: 4! = 1 · 2 · 3 · 4 = 24. Кроме того: 0! = 1.

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

Формула

Типичная смысловая нагрузка: «Сколькими способами можно переставить n объектов?»

Сколькими способами можно расставить 3 различные книги на книжной полке?

Решение: Выбираем одну из 3-х книг и ставим на первое место. Это можно сделать 3-мя способами. Вторую книгу мы можем выбрать из 2-х оставшихся двумя способами, получаем 3·2 способов. Третью книгу мы можем выбрать 1 способом.

Получится 3·2·1=6 способов.

Определение: Размещением из n элементов по k (k≤n) называется любое множество, состоящее из k элементов, взятых в определённом порядке из данных n элементов.

Формула:

Типичная смысловая нагрузка: «Сколькими способами можно выбрать k объектов и в каждой выборке переставить их местами?»

Учащиеся второго класса изучают 9 предметов. Сколькими способами можно составить расписание на один день, чтобы в нём было 4 различных предмета?

Решение:

Определение: Сочетанием из n элементов по k (kn) называется любое множество, составленное из k элементов, выбранных из данных n элементов (не имеет значения, в каком порядке указаны элементы).

Формула:

Типичная смысловая нагрузка: «Сколькими способами можно выбрать k объектов из n?»

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

Решение:

Правило сложения комбинаций

Знак «плюс» следует понимать и читать как союз ИЛИ.

Задача. Студенческая группа состоит из 23 человек, среди которых 10 юношей и 13 девушек. Сколькими способами можно выбрать 2-х человек одного пола?

Решение: Условие «выбрать 2-х человек одного пола» подразумевает, что необходимо выбрать двух юношей или двух девушек:

– способами можно выбрать 2-х юношей;

– способами можно выбрать 2-х девушек;

Таким образом, двух человек одного пола (без разницы – юношей или девушек) можно выбрать:  способами.

Правило умножения комбинаций

Знак «умножить» следует понимать и читать как союз И.

Задача. Студенческая группа состоит из 23 человек, среди которых 10 юношей и 13 девушек. Сколькими способами можно составить пару из юноши и девушки?

Решение:

– способами можно выбрать 1 юношу;

– способами можно выбрать 1 девушку.

Таким образом, 1-го юношу и 1 девушку можно выбрать: способами.

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

Типичная смысловая нагрузка: «Количество способов, которыми можно переставить n объектов, среди которых 1-й объект повторяется n₁ раз, 2-й объект повторяется n₂раз, 3-й объект повторяется n₃раз, …, k-й объект повторяется n_kраз».

Формула:

У мамы 2 яблока и 3 груши. Каждый день в течение 5 дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано?

Решение:Имеем набор {я, я, г, г, г}. Всего перестановок пятиэлементного множества 5!, но мы не должны учитывать перестановки, в которых объекты одного типа меняются местами несколько раз, поэтому нужно поделить на возможное число таких перестановок: 2! · 3!.

В итоге получаем

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

Типичная смысловая нагрузка: «Для выбора предложено n множеств, каждое из которых состоит из одинаковых объектов. Сколькими способами можно выбрать m объектов?»

Формула: .

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

Решение: Используя формулу количества сочетаний с повторениями, получаем

способами можно выбрать 3 монеты из кошелька.

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

Типичная смысловая нагрузка: «Дано множество, состоящее из n объектов, при этом любой объект можно выбирать неоднократно. Сколькими способами можно выбрать m объектов, если важен порядок их расположения в выборке?В частности, возможен случай, когда из n имеющихся объектов m раз будет выбран какой-то один объект».

Формула: .

Человек, пришедший в гости, забыл код, открывающий дверь подъезда, но помнил, что он составлен из нулей и единиц и всего имеет четыре цифры. Сколько вариантов кода в худшем случае ему придётся перебрать, чтобы открыть дверь?

Решение: