Практическое занятие 1.1.

Элементы комбинаторики

 

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

 

Комбинаторика является самостоятельным разделом высшей математики. В узком смысле комбинаторика – это подсчёт различных комбинаций, которые можно составить из некоторого множества дискретных объектов. Принципиально важно, что эти объекты поддаются перечислению.

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

 

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

 

На столе находятся яблоко, груша и банан. Выкладываем фрукты на столе слева направо.

Вопрос 1: сколькими способами их можно переставить?

Возможны комбинации:

яблоко / груша / банан                яблоко / банан / груша

груша / яблоко / банан                груша / банан / яблоко

банан / яблоко / груша                банан / груша / яблоко

Итого: 6 комбинаций или 6 перестановок.

 

Основной закон комбинаторики. Пусть нужно произвести k действий, причем первое действие можно произвести п1 способами, второе – п2 способами, …, k-ое – пk способами. Тогда все действия можно произвести способами.

Определение 1. Перестановкой из п элементов называется набор из п элементов, расположенных в определенном порядке.

 

1.Факториал

     0!=1                                3!=1 ·2 ·3= 6

     1!=1                                4!= 1 ·2 ·3·4=24

     2!=1·2=2                        5!= 1 ·2 ·3·4·5=120

              (n-1)! =1· 2 ·3· 4 ·5· ... ·(n-1)    

               n! = 1· 2 ·3· 4 ·5· ... ·(n-1)·n  

2. Формула количества перестановок

Pn=n! =1· 2 ·3· 4 ·5· ... ·(n-2)·(n-1)·n

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

 

Количество всех возможных перестановок выражается формулой Рп=п!

По формуле количества перестановок: 3 объекта можно переставить  Р3=3!=1·2·3=6 способами.

 

Задача 1. Сколькими способами можно рассадить 5 человек за столом?

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

 

Р5=5!=120

 

Ответ: 120 способами

 

Сочетания

 

Вопрос 2: сколькими способами можно выбрать: а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт из предложенных: яблоко, груша и банан.

а) Несложно понять, что один фрукт можно выбрать тремя способами – взять либо яблоко, либо грушу, либо банан.

Определение 2. Сочетанием из п элементов по т элементов называется набор из т элементов, выбранных из данных п элементов

 

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

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

 

Формальный подсчёт проводится по формуле количества сочетаний:

 

.

 

б) Перечислим все возможные сочетания выбора двух фруктов: яблоко и груша; яблоко и банан; груша и банан.

Количество комбинаций легко проверить по той же формуле:

 

 

Запись  понимается аналогично: «сколькими способами можно выбрать 2 фрукта из трёх?».

в) наконец, три фрукта можно выбрать единственным способом: яблоко, груша, банан

 

 

Формула количества сочетаний сохраняет смысл и для пустой выборки:

 

 

способом можно выбрать ни одного фрукта – собственно, ничего не взять и всё.

г) Сколькими способами можно взять хотя бы один фрукт? Условие «хотя бы один» подразумевает, что нас устраивает 1 фрукт (любой) или 2 любых фрукта или все 3 фрукта:

 

 

способами можно выбрать хотя бы один фрукт.

 

Задача 2. В ящике находится 15 деталей. Сколькими способами можно взять 4 детали?

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

В задаче речь идёт о выборке из 4 деталей, «просто выбираем 4 детали и всё». Таким образом, считаем их количество:

 

 

 

Здесь, конечно же, не нужно ворочать огромные числа 11!=39916800, 15!=1307674368000.

В похожей ситуации я рекомендую использовать следующий приём: в знаменателе выбираем наибольший факториал (в данном случае 11!) и сокращаем на него дробь. Для этого числитель следует представить в виде 15!=11!·12·13·14·15. Распишем очень подробно:

 

 

способами можно взять 4 детали из ящика.

Ответ: 1365 способами

 

Задача 3. В шахматном турнире участвует k человек и каждый с каждым играет по одной партии. Сколько всего партий сыграно в турнире?

Исходя из проведённых рассуждений, общее количество сыгранных партий рассчитывается по формуле  . Однако можно заметить, что на самом деле здесь можно руководствоваться самыми что ни на есть банальными сочетаниями:

 

 

 

Размещения

 

Вопрос 3: сколькими способами можно раздать по одному фрукту Даше и Наташе из предлагаемых в нашем примере набора: яблоко, груша, банан?

Для того чтобы раздать два фрукта, сначала нужно их выбрать. Это можно сделать  способами: яблоко и груша; яблоко и банан; груша и банан.

Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов:

яблоком можно угостить Дашу, а грушей – Наташу;

либо наоборот – груша достанется Даше, а яблоко – Наташе.

 

И такая перестановка возможна для каждой пары фруктов.

В данном случае работает формула количества размещений.

 

 

Определение 3. Размещением из п элементов по т элементов называется набор из т элементов, выбранных из данных п элементов в определенном порядке, т.е. два различных размещения различаются либо составом, либо (при одинаковом составе) порядком элементов.

 

4. Формула количества размещений

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

 

Задача 4. Боря, Дима и Володя сели играть в карты. Сколькими способами им можно раздать по одной карте? (колода содержит 36 карт)

Решение: ситуация похожа на Задачу 3, но отличается тем, что здесь важно не только то, какие три карты будут извлечены из колоды, но и то, как они будут распределены между игроками. По формуле размещений:

 способами можно раздать 3 карты игрокам.

Ответ: 42840

 

Кроме приведенных формул еще применяются комбинации элементов с повторениями.

 

5. Формула количества перестановок с повторениями

Типичная смысловая нагрузка: «Количество способов, которыми можно переставить n объектов, среди которых 1-й объект повторяется n1 раз, 2-й объект повторяется n2 раз, 3-й объект – n3 раз,…, k -й объект –nk раз»

6. Формула количества сочетаний с повторениями

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

То есть, здесь в выборке могут оказаться одинаковые объекты, и если m>n, то совпадения точно будут. По умолчанию предполагается, что исходная совокупность содержит не менее m объектов каждого вида, и поэтому выборка может полностью состоять из одинаковых объектов.

7. Формула количества размещений с повторениями

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