Общие правила комбинаторики

 

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

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

· выбор без повторения (без возвращения), т.е. отобранные элементы исключаются из множества;

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

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

Пример:

В магазине 5 видов коробок конфет и 4 вида коробок печенья. Сколькими способами можно купить в подарок: а) коробку конфет или коробку печенья; б) набор из коробки конфет и коробки печенья?

Решение: а) Коробку конфет можно выбрать пятью способами, а коробку печенья – четырьмя способами. Следовательно, коробку конфет или коробку печенья можно выбрать 5 + 4 = 9 способами.

б) Будем составлять наборы из коробки конфет и коробки печенья. С первым видом коробки конфет возможно 4 варианта подарка (с каждым из четырех видов коробок печенья), со вторым видом коробок конфет аналогично 4 варианта и т.д. Следовательно, с каждым из пяти видов коробок конфет возможно по 4 варианта подарка. Итого 5*4=20 способов купить подарок.

Правило произведения. Если некоторый объект А можно выбрать m способами, а объект В – k способами, то объект «А и В» можно выбрать ( ) способами.

Пример:

Сколькими способами можно выбрать 3 шара из 8 (без возвращения)?

Решение: Первый шар можно выбрать восьмью способами, второй – семью способами, а третий – шестью способами. Тогда три шара можно выбрать способами.

Правило суммы. Если объект А можно выбрать m способами, а объект В – k способами (выбор объекта А и объекта В - взаимоисключающие действия), то объект «А или В» можно выбрать (m+k) способами.

Пример:

В группе 20 человек – 12 девушек и 8 юношей. Сколькими способами можно выбрать двух человек одного пола?

Решение: Можно выбрать двух юношей или двух девушек. Двух девушек можно выбрать способами, двух юношей способами. Тогда выбрать двух человек одного пола можно выбрать 132 + 36 = 168 способами.

3.2. Размещения, сочетания и перестановки
без повторения (без возвращения)

Пусть дано множество , состоящее из n различных элементов. Из Е будем выбирать m элементов без повторения (без возвращения) последовательно по одному. Будем получать m -элементные подмножества множества Е ().

А) Если при этом порядок следования элементов важен, то будем получать упорядоченные m -элементные подмножества множества Е, отличающиеся друг от друга либо набором элементов, либо порядком их следования. Такие комбинации называют размещениями из n элементов по m без повторения (без возвращения). Их количество вычисляется по формуле:

.

Замечание: Для любого натурального n можно вычислить n -факториал по формуле: . При чем, принято считать, .

Пример:

Имеется 10 футбольных команд. Сколькими способами можно провести награждение этих команд медалями (золотой, серебряной и бронзовой)?

Решение: Из 10 команд нужно выбрать 3. Значит , а . При этом . Порядок следования элементов важен, т.к. если одни и те же элементы брать в разном порядке, то будем получать отличные варианты награждения. Кроме того, награжденная команда исключается из исходного множества команд (выбор без возвращения). Значит, полученные комбинации являются размещениями из 10 по 3 без возвращения. Количество таких комбинаций: . Итак, 720 способов.

Б) Если при этом порядок следования элементов не важен, то будем получать m -элементные подмножества множества Е, отличающиеся друг от друга только набором элементов. Такие комбинации называют сочетаниями из n элементов по m без повторения (без возвращения). Их количество вычисляется по формуле:

.

Пример:

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

Решение: Из 10 человек нужно выбрать 3. Значит , а . При этом . Порядок следования элементов не важен, т.к. трое отобранных дежурных могут быть выбраны в разном порядке – суть от этого не меняется. Кроме того, выбранный дежурный исключается из исходного множества и не может быть выбранным снова (выбор без возвращения). Значит, полученные комбинации являются сочетаниями из 10 по 3 без возвращения. Количество таких комбинаций: . Итак, 120 способов.

Напомним, что имеем множество , состоящее из n различных элементов. Будем задействовать в комбинации все n элементов множества Е, получая при этом множества состоящие из различных элементов, т.е. комбинации без повторения и отличающиеся друг от друга только порядком следования элементов. Таким образом, получим размещениями без повторения, но , т.е. Такие комбинации называют перестановками из n элементов без повторения. Их количество вычисляется по формуле:

Пример:

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

Решение: Из 5 студентов нужно задействовать в комбинации всех 5 студентов. Значит, в комбинации использованы все предоставленные элементы. Выбранный и поставленный в очередь студент исключается из исходного множества и не может быть выбранным снова (выбор без повторения). Значит, полученные комбинации являются перестановками из 5 элементов без повторения. Количество таких комбинаций: . Итак, 120 способами могут встать в очередь 5 студентов.

 

3.3. Размещения, сочетания и перестановки
с повторением (с возвращением)

 

Пусть дано множество , состоящее из n различных элементов. Из Е будем выбирать m элементов с повторением (с возвращением) последовательно по одному. Будем получать m -элементные подмножества множества Е ().

А) Если при этом порядок следования элементов важен, то будем получать упорядоченные m -элементные подмножества множества Е, отличающиеся друг от друга либо набором элементов, либо порядком их следования. Такие комбинации называют размещениями из n элементов по m с повторением (с возвращением). Их количество вычисляется по формуле:

.

Пример:

Сколько различных трехзначных чисел можно составить, используя цифры 2, 4, 6, 7, 9?

Решение: Чтобы составить трехзначное число из 5 цифр нужно выбрать 3. Значит , а . При этом . Порядок следования элементов важен, т.к. если выбрать одни и те же цифры, но в разном порядке, то будем получать отличные друг от друга числа. Кроме того, выбранная цифра может в числе встретиться не один раз, значит выбор с повторением (с возвращением). Значит, полученные комбинации являются размещениями из 5 по 3 с возвращением. Количество таких комбинаций: . Итак, 125 трехзначных чисел можно составить, используя цифры 2, 4, 6, 7, 9.

Б) Если при этом порядок следования элементов не важен, то будем получать m -элементные подмножества множества Е, отличающиеся друг от друга только набором элементов. Такие комбинации называют сочетаниями из n элементов по m с повторением (с возвращением). Их количество вычисляется по формуле:

.

Пусть во множестве встречаются одинаковые элементы. Допустим, элемент встречается раз, элемент встречается раз и т.д. (пусть при этом во множестве F t различных элементов). Будем задействовать в комбинации все n элементов множества F, получая при этом комбинации, отличающиеся друг от друга только порядком следования элементов. Такие комбинации называют перестановками из n элементов с повторением. Их количество вычисляется по формуле:

Пример:

На карточках написаны буквы, образующие слово «математика». Их перемешивают и выкладывают в ряд. Сколько различных вариантов это сделать?

Решение: Из 10 карточек нужно задействовать в комбинации все 10. Значит, в комбинации использованы все предоставленные элементы. Среди 10 букв некоторые встречаются несколько раз, значит комбинации с повторениями и являются перестановками. Количество таких комбинаций: . Ответ: 151200 способов.

Упражнения

 

1.Три друга, Антон, Борис и Виктор, приобрели два билета на футбольный матч. Сколько существует различных вариантов похода на футбол?

2.Антону, Борису и Виктору повезло, они купили 3 билета на футбол на 1-е, 2-е и 3-е места первого ряда стадиона. Сколькими способами могут занять мальчики эти места?

3.В алфавите племени УАУА имеются только две буквы – «а» и «у». Сколько различных слов по три буквы в каждом можно составить, используя алфавит этого племени?

4.Сколько «слов» можно составить из букв слова:

а) «семинар», б) «колокол», в) ваше полное имя?

5.Сколькими способами можно составить трехцветный флаг, если имеется материал:

а) трех различных цветов? б) пяти различных цветов?

6.Сколькими способами можно расположить 6 книг на книжной полке?

7.Для 15 участников конкурса распределяют дипломы пяти степеней. Сколькими способами могут быть распределены места?

8.Сколькими способами может быть сформирована команда из 9 человек на олимпиаду от студенческой группы из 23 человек?

9.У студента 3 экзамена. Сколько возможностей распределения оценок (неудовлетворительно, удовлетворительно, хорошо, отлично)?

10. Сколько существует четырехзначных номеров машин?

11. Сколькими способами можно рассадить на скамейке 4 детей?

12. В 5«А» классе в среду 4 урока: математика, информатика, русский язык, английский язык. Сколько можно составить вариантов расписания на среду?

13. Первого сентября на 1 курсе некоторого факультета запланировано 3 лекции по разным предметам. Всего на 1 курсе изучается 10 предметов. Сколько существует способов составить расписание на 1 сентября?

14. В группе студентов 25 человек. Необходимо избрать старосту, заместителя старосты и профорга. Сколькими способами это можно сделать?

15. Сколько четырехбуквенных слов можно составить из букв слова «семинар»? Сколько таких слов начинается с буквы «р»?

16. Сколько можно составить всевозможных шестизначных номеров телефона, используя цифры от 0 до 9?

17. Сколько слов можно составить из букв слова «кукла», если на первом месте должна быть буква «л», а на последнем буква «к»?

18. Сколькими способами можно составить трехзначное число, используя цифры 2,3,5,7,8,9?

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

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

21. Из А в В ведут 5 дорог, а из В в С – 3 дороги. Сколькими способами можно проехать из А в С?

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

23. Сколько способов выбрать на обед одно первое, два вторых блюда и 3 напитка, если в столовой 3 вида первого блюда, 5 видов вторых и 7 видов напитков?

24. Тринадцать одноклассников решили прийти друг к другу в гости на чай. а) Сколько раз попьет чай каждый? б) Сколько различных встреч при этом произойдет?

25. На вечере встречи 25 выпускников обменялись рукопожатиями. Сколько всего рукопожатий было сделано? На том же вечере они решили обменяться фотокарточками. Сколько всего фотографий будет заказано?

26. В продаже 11 видов роз и 4 вида декоративных украшений. Сколькими способами можно составить букет из 5 роз и 3 декоративных украшений?

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

28. Сколькими способами можно из 15 солдат и 4 офицеров назначить в патруль 3 солдат и одного офицера?

29. Из 4 инженеров и 9 экономистов составляют комиссию, состоящую из 7 человек. Сколькими способами это можно сделать, если в комиссию должны войти хотя бы 2 инженера.

30. Предприятие может предоставить работу по одной специальности 4 женщинами, по другой – 6 мужчинам, по третьей – 3 работникам независимо от пола. Сколькими способами можно заполнить вакантные места, если имеются 14 претендентов: 6 женщин и 8 мужчин?

31. В подъезде поставили кодовый замок. Код – три цифры. Жильцы решили менять код каждый день. Через сколько дней код повторится?

32. В вузе учатся 30 000 студентов. Обязательно ли среди них найдутся хотя бы 2 человека с одинаковыми инициалами (первая буква фамилии, имени, отчества)?

ТЕОРИЯ ВЕРОЯТНОСТЕЙ

 

Историческая справка

 

В Индии еще до н.э. широкое распространение получило религиозное течение джайн. Составной частью этой религии было учение сауд или саудвада. Полное развитие учения «сауд» получило к 6 веку до н.э. Ему уделялось большое внимание и в середине века. Известен трактат, посвященный этой теории, относящийся к 1292 году, имеются и более поздние работы. Основой учения саудвады является возможность следующих семи утверждений относительно изучаемого явления:

1. Может быть есть.

2. Может быть нет.

3. Может быть есть и нет.

4. Может быть это неопределенно.

 

5. Может быть это есть и тоже не определенно.

6. Может быть этого нет и тоже неопределенно.

7. Может быть это есть и нет и тоже неопределенно.

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

 

Случайные события

 

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

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

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

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

Случайным называется событие, которое может произойти или не произойти в результате некоторого испытания (опыта). Случайные события обозначают большими латинским буквами.

Примеры:

1. Бросили монету. Выписать все случайные события.

Решение: Бросание монет – опыт. Событие А – выпал герб. Событие В – выпала решка.

2. Завтра днем – ясная погода. Выписать случайные события.

Решение: Наступление дня – опыт. Событие А – в течение дня наблюдалась ясная погода.

Не всякое предложение описывает событие («Миру нужен мир»).

Событие называется достоверным, если оно при реализации комплекса условий непременно произойдет (принято обозначать буквой U).

Например, событие U – из ящика с белыми шарами вынут белый шар.

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

Например, событие V – из ящика с синими шарами вынут белый шар.

Если событие В происходит каждый раз, как происходит событие А, то говорят, что событие А благоприятно для В и пишут .

Суммой событий А и В называется событие А+В, состоящее в том, что в результате испытания произошло хотя бы одно из событий А или В.

Произведением событий А и В называется событие , состоящее в совместном осуществлении в результате испытания событий А и В.

Разностью событий А и В называется событие А – В, состоящее в том, что событие А происходит, а событие В не происходит.

События А и В называются несовместными, если в результате данного испытания появление одного исключает появление другого. Другими словами, А и В несовместны, если , т.е. если они не могут произойти одновременно.

Например, при бросании одной монеты событие А – выпал герб, событие В – выпала решка. А и В события несовместные.

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

Например, событие А – вошел человек старше 40 лет, событие В – вошла женщина. А и В – совместные события.

События и противоположные, если в данном испытании они несовместны и одно из них обязательно происходит. Событие состоит в том, что событие А не происходит. События А и несовместны.

Например, взята деталь. Событие А – деталь стандартная. Событие - деталь бракованная. А и - несовместные события, т.к. одна и та же деталь не может быть стандартной и бракованной одновременно.

Проиллюстрируем все операции над событиями на примере.

Пример:

По мишени произведено 3 выстрела. Введем следующие события:

А₀ – попаданий нет; А₁ – одно попадание;

А₂ – два попадания; А₃ – одно попадания;

А – произошло не больше двух попаданий.

Тогда верными будут следующие утверждения: , , , , , , и т.д.

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

Например, бросаем игральный кубик. Выпадение грани с номером 1, 2, 3, 4, 5, 6 – равновозможные события. Но нельзя сказать, что событие – число выпавших очков больших 5 и событие – число выпавших очков меньших 5 – равновозможны.

Множество элементарных событий – это полное множество взаимоисключающих исходов эксперимента.

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

Например, при бросании игральной кости в полной группе попарно несовместных событий имеется 6 элементарных событий. Или при бросании монеты в полной группе попарно несовместных событий два события – выпал орел и выпала решка.

 

Определения вероятности

 

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

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

Примеры:

1. Какова вероятность того, что при бросании игрального кубика выпадет число очков не меньше 5?

Решение: Число всех элементарных исходов опыта, которые образуют полную группу попарно несовместных и равновозможных событий равно 6 (выпало 1 очко, 2, 3, 4, 5, или 6). Из них благоприятны только – выпадение 5 и 6 (т.к. не меньше 5). Значит вероятность события А – выпадение числа очков не меньше 5 равна .

2. В группе 20 студентов. В деканат вызвали двух. Какова вероятность того, что вызвали двух юношей, если их в группе 5?

Решение: Число всех элементарных исходов опыта, которые образуют полную группу попарно несовместных и равновозможных событий равно (количество сочетаний из 20 по 2). Из них благоприятных (количество сочетаний из 5 по 2). Значит вероятность события А – в деканат вызвали двух юношей равна .

Замечания:

1. Вероятность достоверного события равна 1, т.к. .

2. Вероятность невозможного события равна 0, т.к. .

3. Для любого события А справедливо условие .

4. Чтобы вероятность указать в процентах, полученное по указанной формуле значение нужно умножить на 100 %.

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

Геометрическое определение вероятности. Вероятность события есть отношение меры (длины, площади, объема) к мере пространства элементарных событий. Другими словами, пусть случайное испытание можно представить себе как бросание точки наудачу в некоторую геометрическую область G (на прямой, плоскости или пространстве). Элементарные исходы – это отдельные точки G, любое событие – это подмножество этой области, пространства элементарных исходов G. Можно считать, что все точки G «равноправны» и тогда вероятность попадания точки в некоторое подмножество пропорционально его мере (длине, площади, объему) и не зависит от его расположения и формы. Геометрическая вероятность события А определяется отношением: , где m(G), m(A) – геометрические меры (длины, площади или объемы) всего пространства элементарных исходов и события А.

Пример:

В прямоугольник 5*4 см² вписан круг радиуса 1,5 см. Какова вероятность того, что точка, случайным образом поставленная в прямоугольник, окажется внутри круга?

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

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

Например, нельзя использовать формулу классического определения вероятности в том случае, когда требуется вычислить вероятность попадания в мишень двух стрелков: профессионала и новичка, т.к. по классической формуле вероятность попадания в мишень каждого из них была бы равно 0,5, что на сомом деле не так (она не может быть одинаковой для этих случаев).

В таком случае оценка вероятности дается из практики. Каждым стрелком производятся N выстрелов. Если стрелок попадает при этом M раз, то вероятность события вычисляется как . при этом называется статистическим значением вероятности.

Статистическое определение вероятности. Пусть проводится некоторое испытание, в результате которого может наступить событие А. предположим, что такое испытание произведено N раз, и при этом событие А появилось ровно M раз. Тогда число называется статистической вероятностью (или относительной частотой) события А в рассматриваемой серии испытаний.

Например, рассмотрим событие рождения мальчика или рождения девочки. По статистике на каждую 1000 рожденных детей приходится 518 мальчиков. Значит статистическая вероятность рождения мальчика (событие А) равна , а статистическая вероятность рождения девочки (событие В) равна .