Комбинаторика - основные понятия и формулы. Перестановки, размещения, сочетания

Основные понятия и формулы


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

Правило умножения (основная формула комбинаторики)

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


Пример 1

Монету подбросили 3 раза. Сколько различных результатов бросаний можно ожидать?

Решение

Первая монета имеет  альтернативы – либо орел, либо решка. Для второй монеты также есть  альтернативы и т.д., т.е. .

Искомое количество способов:


Правило сложения

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


Пример 2

На полке 30 книг, из них 20 математических, 6 технических и 4 экономических. Сколько существует способов  выбора одной математической или одной экономической книги.

Решение

Математическая книга может быть выбрана    способами, экономическая -  способами.

По правилу суммы существует  способа выбора математической или экономической книги.


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


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

Размещения без повторений, когда отобранный элемент перед отбором следующего не возвращается в генеральную совокупность. Такой выбор называется последовательным выбором без возвращения, а его результат – размещением без повторений из  элементов по .

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


Пример 3

Расписание дня состоит из 5 различных уроков. Определите число вариантов расписания при выборе из 11 дисциплин.

Решение

Каждый вариант расписания представляет набор 5 дисциплин из 11, отличающихся от других вариантов как составом, так и порядком следования. поэтому:


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


Пример 4

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

Решение

Каждый вариант рассадки отличается только порядком участников, то есть является перестановкой из 4 элементов:


Размещения с повторениями, когда отобранный элемент перед отбором следующего возвращается в генеральную совокупность. Такой выбор называется последовательным выбором с возвращением, а его результат  - размещением с повторениями из  элементов по .

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


Если вам сейчас не требуется платная помощь с решением задач, контрольных работ и типовых расчетов, но может потребоваться в дальнейшем, то, чтобы не потерять контакт
вступайте в группу ВК
сохраните контакт WhatsApp (+79688494598)
сохраните контакт Телеграм (@helptask) .

Пример 5

Лифт останавливается на 7 этажах. Сколькими способами могут выйти на этих этажах 6 пассажиров, находящихся в кабине лифта?

Решение

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

 


Сочетания


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

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

Число сочетаний из  элементов по  равно:


Пример 6

В ящике 9 яблок. Сколькими способами можно выбрать 3 яблока из ящика?

Решение

Каждый вариант выбора состоит из 3 яблок и отличается от других только составом, то есть представляет собой сочетания без повторений из 9 элементов:

Количество способов, которыми можно выбрать 3 яблока из 9:


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

Число сочетаний с повторениями из  элементов по :


Пример 7

На почте продают открытки 3 видов. Сколькими способами можно купить 6 открыток?

Решение

Это задача на отыскание числа сочетаний с повторениями из 3 по 6:


Разбиение множества на группы


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

Число разбиений на  групп, когда в первую попадают  элементов, во вторую -  элементов, в k-ю группу -  элементов, равно:


Пример 8

Группу из 16 человек требуется разбить на три подгруппы, в первой из которых должно быть 5 человек, во второй – 7 человек, в третьей – 4 человека. Сколькими способами это можно сделать?

Решение

Здесь

Число разбиений на 3 подгруппы:

Задачи контрольных и самостоятельных работ


Задача 1

Монету подбросили 3 раза. Сколько различных результатов бросаний можно ожидать?


Задача 2

Доступ к файлу открывается, только если введен правильный пароль – определенный трехзначный номер из нечетных цифр. Какова максимальное число возможных попыток угадать пароль?


Задача 3

Группу из 10 человек требуется разбить на две непустые подгруппы  и . Сколькими способами можно это сделать?


Задача 4

Два наборщика должны набрать 16 текстов. Сколькими способами они могут распределить эту работу между собой.


Задача 5

Шесть студентов-переводников нужно распределить по трем группам. Сколькими способами это можно сделать?


Задача 6

Лифт останавливается на 7 этажах. Сколькими способами могут выйти на этих этажах 6 пассажиров, находящихся в кабине лифта?


Задача 7

В ящике 5 красных и 4 зеленых яблока. Сколькими способами можно выбрать 3 яблока из ящика?


Задача 8

Из ящика, в котором лежат 10 красных и 5 зеленых яблок, выбирают одно красное и два зеленых яблока. Сколькими способами можно это сделать.


Задача 9

В группе из 25 студентов нужно выбрать старосту и 3 членов студенческого комитета. Сколькими способами можно это сделать.


Задача 10

Акционерное собрание компании выбирает из 50 человек президента компании, председателя совета директоров и 10 членов совета директоров. Сколькими способами это можно сделать?


Задача 11

В телевизионной студии работают 3 режиссера, 4 звукорежиссера, 5 операторов, 7 корреспондентов и 2 музыкальных редактора. Сколькими способами можно составить съемочную группу, состоящую из одного режиссера, двух операторов, одного звукорежиссера и двух корреспондентов.


Задача 12

На группу из 25 человек выделены 3 пригласительных билета на вечер. Сколькими способами они могут быть распределены (не более одного билета в руки).


Задача 13

Имеются 7 билетов: 3 в один театр и 4 – в другой. Сколькими способами они могут быть распределены между студентами группы из 25 человек?


Задача 14

Группу из 16 человек требуется разбить на три подгруппы, в первой из которых должно быть 5 человек, во второй – 7 человек, в третьей – 4 человека. Сколькими способами это можно сделать?