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

Глава 1. Основные понятия теории вероятностей

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

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

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

 Рассмотрим фиксированное множество , содержащее п различных элементов.

 Правило суммы. Пусть элемент а₁  из множества М можно выбрать числом n₁ способов, элемент а₂ из множества М можно выбрать числом n₂ способов, элемент а_к из множества М можно выбрать числом n_k способов.

Тогда один из элементов множества М ( а₁ , или а₂, или, . . ., или а_к ) можно выбрать числом п₁+ п₂ + . . . + п_к способов.

Правило произведения. Пусть элемент а₁ из множества М можно выбрать числом n₁  способов, элемент а₂. из множества М можно выбрать числом n₂ способов,  … элемент а_к из множества М можно выбрать числом n_k способов. Причем, выбор элемента а₁ не влияет на число способов выбора всех последующих элементов, выбор элемента а₂ не влияет на число способов выбора всех последующих элементов и т.д. Тогда все к элементов а₁ ,а_2, … , а_к в указанном порядке можно выбрать числом n₁  …n_k способов.

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

4В конкурсе участвуют 7 коллективов, следовательно, первое место может быть распределено n₁=7 способами, второе место ‑ n₂ = 6, третье ‑ n₃ = 5 способами. Тогда, по правилу произведения, число способов распределения призовых мест среди 7 коллективов: n_1∙n₂×n₃=7 ×6 ×5=210.3

Формулы комбинаторики определяют число способов, которыми из множества М, содержащего n элементов, можно выбрать по определенным правилам какую-либо комбинацию k элементов, образующую подмножество М_k исходного множества.

Существуют две разные схемы выбора элементов: без повторений и с повторениями. В схеме выбора без повторений выбор элементов осуществляется без возвращения в исходное множество, т.е. выбранный элемент исключается из множества М и не участвует в дальнейшем выборе. При этом выбор может осуществляться как поэлементно, так и партиями. В схеме выбора с повторениями выбранный элемент фиксируется в подмножестве М_к и возвращается в исходное множество М. Таким образом, в выборе любого элемента подмножества М_k участвуют каждый раз все элементы множества М. Схема такого выбора осуществляется обязательно поэлементно.

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

Сочетаниями из n элементов по k называют произвольные неупорядоченные k-элементные подмножества М_k n-элементного множества М. Сочетания отличаются друг от друга только составом элементов. Порядок следования элементов в них не имеет значения.

Число сочетаний из n элементов по k обозначается  и вычисляется по формуле 

                         .                                    (1.1)

Символом n! (n факториал) обозначается произведение всех натуральных чисел от 1 до n, т.е. n!=1×2×3×…×n; k!=1×2×…×k; (n-k)!=1×2×…×(n-k).  Принято считать 0!=1 и 1!=1 . Для числа сочетаний из п элементов по к имеют место соотношения:

;     .

Пример 1.3. Предприятие выпускает 25 наименований продукции. Сколько существует способов выбрать 3 различных наименования продукции для презентации на выставке?

4Элементами множества М являются наименования продукции. Выбранные 3 наименования представляют неупорядоченное подмножество М₃. Схема выбора - выбор без повторений. Тогда число способов выбора равно:  =  =  = =2300.3

Размещениями из n элементов по k называют упорядоченные k-элементные подмножества М_k  n-элементного множества М. Отличаются размещения друг от друга и составом элементов, и порядком их следования.

Число размещений из n элементов по kобозначается A_n^k и вычисляется по формуле

=n×(n-1)×(n-2)×…×(n-k+1) (1.2).

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

4Код представляет собой упорядоченное 3-элементное подмножество, выбранное из 10-элементного множества М = {0, 1,…, 9}. Число возможных кодов, состоящих из различных цифр, равно

 = = =  = 8×9×10 = 720.3

Перестановками называют размещения, в которых участвуют все элементы множества М.Если в перестановке изменить порядок следования элементов, то получится новая перестановка. Например, перестановками множества М={a,b,c} будут: М ={a,b,c}, М ={a,c,b}, М ={b,a,c}, М ={b,c,a}, М ={c,a,b}, М ={c,b,a}.

Число всех перестановок п-элементного множества обозначается P_n и вычисляется по формуле:    

                            (1.3)

 Это число определяет, сколькими способами можно упорядочить множество, состоящее из nэлементов.

Пример 1.5. К билетной кассе одновременно подошли 5 человек. Сколько существует способов составить из них очередь?

4Очередь - это упорядоченное множество, число способов составить очередь равно: P₅ = 5! = 1×2×3×4×5 = 120.3

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

Число сочетаний из n элементов по k с повторением обозначается f_n^k и вычисляется по формуле:    

= .                      (1.4)

Пример1.6.Каждая кость домино представляет собой комбинацию из двух чисел от 0 до 6. Сколько различных костей содержит игра?

4Каждая кость домино состоит из двух полей, точки на поле определяют число, следовательно, кость можно рассматривать как неупорядоченное 2-элементное подмножество М₂, элементы которого выбраны из 7 элементов множества М = {0,1,2,3,4,5,6}. Поля на кости могут определяться и одинаковыми числами, т.е. элементы М₂ могут повторяться. Тогда число различных костей в игре равно:

3

Размещениями с повторением изn элементов по k называют упорядоченное k-элементное подмножество М_k^у, элементы которого могут повторяться. К размещениям с повторением приводит схема выбора с повторением.

Число размещений из n элементов по k с повторениемобозначается A_n^k(повт) и вычисляется по формуле              

A_n^k(повт) = =n^k.                     ( 1.5 )

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

4Код описывается упорядоченным 3 элементным подмножеством с повторяющимися элементами, составленным из множества М={0,1,…,9}. Число кодов равно:  =10³=1000.3

Перестановками с повторением называют различные упорядоченные множества, состоящие из одних и тех же, но отличающихся расположением элементов, причем некоторые элементы множества одинаковы. Например, перестановками множества М={a,а,c,b} будут: М₁={a,а,c,b}, М₂={a,c,а,b}, М₃={с,a,а,b}, М₄={b,c,a,a}, М₅={a,b,c,a}, М₆={a,a,b,c}, М₇={a,b,а,c}, М₈={b,a,а,c}, М₉={c,b,a,a}, М₁₀={a,c,b,a}, М₁₁={b,а,c,a}, М₁₂={c,a,b,а}.

Пусть задано n-элементное множество М, которое содержит k₁ элементов первого типа, k₂ элементов второго типа, …, k_m элементов m-го типа, причем k₁+k₂+…+k_m=n. Число перестановок n-элементного множества с повторением обозначается P_n(k₁,k₂,…,k_m) и вычисляется по формуле:

P_n(k₁,k₂,…,k_m)= .                          (1.6)

Пример 1.8. Предприятие для маркировки своей продукции использует товарный знак, состоящий из 4 полос, две из которых красного цвета, одна- желтого и одна – синего. Сколько различных товарных знаков может быть составлено с такой маркировкой?

4Товарный знак – это упорядоченное множество, состоящее из 4 элементов, среди которых два повторяются, т.е. имеем n=4, k₁=2, k₂=1, k₃=1. Число N различных товарных знаков будет:

N=P₄(2,1,1)= =12.3

Разбиение множества на группы. Разбиением множества на группы называют представление n элементного множества М в виде суммы m попарно непересекающихся подмножеств , (i= ), содержащих соответственно k_i элементов, причем k₁+k₂+…+k_m = n. Число способов, которыми М можно разбить на группы , обозначается C_n (k₁,k₂,…,k_m) и вычисляется по формуле:

C_n(k₁,k₂,…,k_m) = .                         (1.7)

Пример 1.9. Сколькими способами можно расселить в общежитии 8 студентов по 3 комнатам: одноместной, трехместной и четырехместной?

4Здесь n =8, k₁=1, k₂=3, k₃=4. Число способов расселения равно:

C₈(1,3,4) = =5×7×8= 280.3

Задачи

1.1. Сколько существует способов провести воскресный вечер, если выбирать между посещением театра, дискотеки, ресторана, кинотеатра, считая, что территориально удобно расположены 5 театров, 4 дискотеки, 6 ресторанов и 3 кинотеатра?

Ответ: 18.

1.2. Имеется 5 видов конвертов без марок и 4 вида марок одинаковой стоимости. Сколькими способами можно выбрать конверт с маркой для посылки письма?

Ответ: 20.

1.3. У одного студента 5 книг, у другого – 9. Все книги различные. Сколькими способами студенты могут произвести обмен: а) одной книги на одну? б) двух книг на две книги?

Ответ: а) 45; б) 360.

1.4. На вершину горы ведут 5 тропинок. Сколькими способами турист может подняться в гору и потом спуститься с нее, если а) подъем и спуск могут происходить и по одной тропинке; б) подъем и спуск должны происходить по разным тропинкам?

Ответ: а) 25; б) 20.

1.5. На окружности выбрано 10 точек. а) Сколько можно провести хорд с концами в этих точках? б) Сколько существует треугольников с вершинами в этих точках?

Ответ: а) 45; б) 120.

1.6. Сколькими способами можно выбрать три различные краски из имеющихся пяти?

Ответ: 10.

1.7. Сколько различных трехцветных полосатых флагов можно сшить, если имеется материал пяти различных цветов?

Ответ: 60.

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

Ответ: 20.

1.9. Сколькими способами из 10 спортсменов можно отобрать команду из 6 человек?

Ответ: 210.

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

Ответ: 60.

1.11. В команду КВН отбирают 5 игроков из 10 претендентов. Сколькими способами это можно сделать, если два определенных претендента должны обязательно войти в команду?

Ответ: 56.

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

Ответ: 12.

1.13. Сколько существует способов рассадить 6 посетителей кафе: а) за круглый стол; б) за стойку бара.

Ответ: а) 5!=120; б) 6!=720.

1.14. Имеется 5 сигнальных фишек различной расцветки для маркировки товаров. Сколько видов товара можно промаркировать, если для маркировки использовать а) 2 фишки из 5; б) 3 фишки из 5; в) 4 фишки из 5; г) различное количество фишек.

Ответ: а) 20; б) 60; в) 120; г) 320.

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

Ответ: 39.

1.16. Три фининспектора проверяют 6 фирм. Сколькими способами это можно сделать, если проверку одной фирмы производит один инспектор, и каждый инспектор может проверить только две фирмы?

Ответ: = 90.

1.17. Сколько букв русского алфавита может быть передано азбукой Морзе, состоящей из точек и тире, если для передачи одной буквы отводить а) ровно 4 позиции; б) не более 4 позиций; в) равно 5 позиций.

Ответ: а) 16; б) 30; в) 32.

1.18. Номер автомобиля состоит из 2-букв латинского алфавита и трехзначного числа. Сколько существует автомобильных номеров?

Ответ: =676000.

1.19. В учебной группе 25 студентов. Сколько существует способов разбить группу на 3 подгруппы по 7, 8, и 10 человек для проведения лабораторных занятий?

Ответ: .

1.20. Восемь человек должны сесть в 2 автомобиля, причем в каждом должно быть не менее 3 человек. Сколькими способами они могут это сделать?

Ответ: =126.

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

Ответ: 1320.

1.22. Сколько различных шестизначных шифров можно получить, из цифр 1,2,3,4,5,6,7,8,9, если каждый шифр должен состоять из 3 четных и 3 нечетных цифр, причем никакая цифра не входит в шифр более одного раза?

Ответ: =28 800.

1.23. Фирма закупила четыре различные партии товара. Сколькими способами можно распределить эти партии среди 12 фирменных магазинов, так, чтобы ни один магазин не получил более одной партии нового товара?

Ответ:  =11880.

1.24. Сколькими способами можно расставить на витрине 9 различных экспонатов так, чтобы рядом стоящими оказались: а) два; б) три; в) четыре определенных экспоната?

Ответ: а) .

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

Ответ: 2047. (Воспользоваться свойством сочетаний: ).

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

Ответ:1573.

1.27. Сколькими способами 3 различного вида работ Т₁, Т₂, Т₃ можно распределить между 15 исполнителями, если а) никто из исполнителей не должен выполнять более одной работы; б) работу Т₁ должно получить определенное лицо?

Ответ: а) 2730; б) 182.

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

Ответ: 3024.

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

Ответ:

1.30. Сколько существует различных идентификационных кодов, состоящих из пяти цифр, если первая цифра не равна нулю?

Ответ:

1.31. Менеджеру из своего офиса нужно попасть на деловую встречу, посетив при этом предприятие N, затем вернуться в офис, предварительно опять побывав в N. Сколькими способами он может это сделать, если из офиса в N можно попасть тремя путями, а из N в фирму ведут 4 пути?

Ответ: 144.

1.32. Сколькими способами можно расставить на стоянке 7 различных автомобилей в один ряд, если: два определенных автомобиля а) должны стоять рядом; б) не должны стоять рядом? Ответ: а) 2∙ 6!; б) 5∙6!.

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

Ответ: 6561.

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

Ответ: 9!/(2! ∙2!).

1.35. Сколько различных 10 позиционных кодов можно составить из шести вертикальных и четырех горизонтальных штрихов, если на одну позицию помещать только один штрих?

Ответ:210.

1.36. Найти число всевозможных буквосочетаний из букв слова: а)"сессия", б)"программирование".

Ответ: а) 6!/3!; б)16!/(3!∙2!∙2!∙2!∙2!);

А сколько таких буквосочетаний, в которых 3 буквы а) "с", б) "р" стоят рядом?

Ответ: а) 4!; б) 14!/(2! ∙2! ∙2! ∙2!).

1.37. Имеется 20 наименований товаров. Сколькими способами их можно распределить по 3 магазинам, если известно, что в первый магазин должно быть доставлено 8 наименований, во второй – 7 наименований и в третий – 5 наименований товаров?

Ответ:20!/(8!∙7!∙5!).

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

Ответ: 1260.

1.39. Абитуриент должен сдать четыре вступительных экзамена. Он полагает, что для поступления достаточно набрать 17 баллов. Сколькими способами он может сдать экзамены, набрав не менее 17 баллов и не получив ни одной двойки?

Ответ: 31.

1.40. В кошельке лежат по две монеты достоинством в 1, 2, 5, 10 копеек и по одной монете в 25 и 50 копеек. Сколькими способами можно уплатить этими монетами за покупку стоимостью 76 копеек?

Ответ:4.

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

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

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

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

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

Невозможным называется событие, которое при испытании заведомо не произойдет. Это событие обозначают буквой V.

Случайным называется событие, которое при испытании может произойти или не произойти. Обозначаются случайные события большими буквами латинского алфавита: A, B, C, . . . .

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

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

Несколько событий называются А₁, А₂,…, А_n называют попарно несовместными, если появление каждого из них исключает появление любого из остальных.

События А₁, А₂,…, А_n образуют полную группу событий, если они попарно несовместны, и в результате опыта одно из них обязательно произойдет.

Операции над событиями

Операции над событиями определяют правила действий с событиями и позволяют выражать одни события через другие.

Суммой (объединением) событий А и В называется событие С=А+В (С=АÈВ), состоящее в том, что произойдет хотя бы одно из них ( или А, или В, или оба) . На диаграмме (рис 1.2.) событию С соответствует заштрихованная область С, представляющая объединение областей А и В. Аналогично, суммой нескольких событий А₁, А₂,…, А_n называется событие С, состоящее в том, что произойдет хотя бы одно из событий А_i, i= . Если события А₁, А₂,…, А_n образуют полную группу, то их сумма равна достоверному событию: .

Произведением (пересечением) событий А и В называется событие С=А×В (С=АÇВ), состоящее в совместном появлении событий А и В. На рис 1.3.а событие С представлено пересечением областей А и В. Если А и В – несовместные события, то их произведение - невозможное событие , т. е. А×В=V (рис. 1.3.б).

Произведение событий А₁, А₂,…, А_n – это событие С, состоящее в совместном появлении всех событий А_i, i= : С= . Произведения попарно несовместных событий А₁, А₂,…, А_n – невозможные события: А_i×А_j=V, для любого i¹j.

Противоположным событием  для события А называется событие, состоящее в том, что событие А не произошло.

Свойства операций над событиями.

1.  Переместительные свойства:    А+В=В+А, А·В=В·А.

2.  Сочетательные свойства: (А+В)+С=А+(В+С), (АВ)С=А(ВС).

3.  Распределительное свойство:   А(В+С)=АВ+АС.

4.  Из определений операций над событиями следуют свойства:

    А+А=А; А+U=U; А+V=А; А·А=А;  А·U=А; А·V=V.

5 .  Из определения противоположного события следует, что:

А+ =U; А× =V; =А; =V; =U; U+V=U; U×V=V.