Материал: нефти и газа

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

омбинаторика – раздел математики, изучающий дискретные

Кобъекты, множества (сочетания, перестановки, размещения и перечисление элементов) и отношения на них. Комбинаторика отве-

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

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

 Перестановки. Пусть n объектов необходимо расположить в различных порядках следования друг за другом. Каждый способ расположения этих объектов называется перестановкой. Об-

щее количество перестановок из n объектов определяется вы-

ражением

Pn n (n 1) ... 1 n!

 Размещения без повторений. Пусть из общего количества n

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

называется размещением без повторения. Общее количест-

во возможных групп будет

Пусть n – количество раз-

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

5

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

Amn nm

 Сочетания получаются, если из общего количества n объек-

тов необходимо отобрать группу из m объектов без учета по-

рядка их следования. Число таких групп равно

ПРИМЕР 1. Мама оставила дочке к чаю три конфеты: Комиль-

фо, Рафаэлло и Ферреро Роше. Сколькими способами девочка может их съесть за чаем?

Решение. Дочь может съесть свои три конфеты в различных порядках. Общее количество способов равно числу перестановок из трех объектов:

P3 3! 1 2 3 6.

ПРИМЕР 2. В студенческой группе 25 человек. Сколькими спо-

собами группа может выбрать старосту и профорга?

Решение. Из 25 человек нужно отобрать двоих, причем поря-

док отбора имеет значение, т.к. староста и профорг ‒ различные должности. Общее количество способов равно количеству размеще-

ний из 25 элементов по 2:

6

ПРИМЕР 3. Студент во время проведения финала КВН позна-

комился с девушкой из другого вуза и записал номер ее телефона на клочке бумаги. Впоследствии он обнаружил, что две последние циф-

ры номера оторвались. Сколько времени ему понадобится, чтобы на-

верняка дозвониться до новой знакомой, если на набор каждого но-

мера уходит по 45 секунд?

Решение. Каждая из двух последних цифр номера может при-

нимать значение от 0 до 9, и цифры могут повторяться. Общее коли-

чество возможных номеров равно количеству размещений с повторе-

ниями из 10 цифр по 2 цифры:

A102 102 100.

Если каждый номер набирать 45 секунд, то студенту потребуется не более 100 45 4500 секунд, или 1 часа 15 минут.

ПРИМЕР 4. Для прохождения производственной практики на Московском НПЗ из группы, состоящей из 20 студентов, необходимо отобрать 5 человек. Сколькими способами это можно сделать?

Решение. Поскольку порядок отбора студентов не имеет значе-

ния (все пятеро попадут на НПЗ), то общее количество способов рав-

но количеству сочетаний из 20 элементов по 5:

19 18 17 16 19 3 17 16 15504. 3 2 1

7

Задачи к разделу 1

1.1. Из города А в город В ведут 5 дорог, а из города В в город С

‒ 7 дорог. Сколькими способами можно из города А проехать в город С через город В?

1.2. В финале конкурса должны выступить 6 пианистов. Порядок их выступления решили определить жребием. Сколько существует вари-

антов жеребьевки?

1.3. Код цифрового замка на портфеле содержит три набора по 10

цифр каждый (от 0 до 9). Рассеянный профессор забыл установлен-

ный им ранее код замка. Какое максимальное время придется потра-

тить ученому, чтобы открыть портфель, если на проверку каждого кода уходит 5 секунд?

1.4. В чемпионате России по футболу приняли участие 16 команд.

Сколькими способами они могут поделить призовые места?

1.5. В чемпионате России по футболу участвуют 16 команд. Две по-

следние по итогам сезона переходят во вторую лигу. Сколькими спо-

собами команды могут перейти во вторую лигу?

1.6.В симпозиуме приняли участие 16 ученых. При встрече они все обменялись рукопожатиями. Сколько всего состоялось рукопожатий?

1.7.Каждый из 72 студентов первого курса, присутствующих на лекции, поговорил по мобильному телефону с двумя своими товари-

щами, находящимися в той же аудитории. Какую сумму при этом за-

работали компании сотовой связи, если каждый разговор стоил 10

рублей?

8

1.8. Сколькими способами из колоды в 32 карты, можно отобрать 8

карт так, чтобы среди них оказалось ровно три туза?

1.9. После окончания первого курса 23 студента призывного возрас-

та c факультета экономики и менеджмента имеют более двух акаде-

мических задолженностей и подлежат отчислению. Военкомат дол-

жен призвать на военную службу 9 человек. Сколькими способами это можно сделать?

1.10. Полководец Суворов перед походом через Альпы решил женить

10 своих холостых солдат. В деревне, через которую шла армия, ока-

залось 15 подходящих по возрасту девушек. Сколькими способами Суворов может осуществить задуманное?

1.11. В автомобильных номерах каждого региона России должно быть три цифры и три буквы. Каково максимальное число номеров для ка-

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

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

если пассажиры должны сидеть в разных автомобилях?

1.13. Для игры в лотерее «Спортлото» необходимо отметить в кар-

точке 5 чисел из 36. Сколькими способами можно заполнить карточку лотереи?

1.14. Сколько различных трехбуквенных слов можно составить из слова «КАРАКАТИЦА»?

9