Комбинаторика и вероятность. Применение формул

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

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

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

Правило суммы

Если некоторый объект А можно выбрать m способами, а объект В - k способами (не такими, как А), то объект либо А, либо В можно выбрать m + k способами.

Пример: В ящике имеется n разноцветных шариков. Произвольным образом вынимаем один шарик. Сколькими способами это можно сделать? Конечно, n способами.

Теперь эти n шариков распределены по двум ящикам: В первом m шариков, во втором k. Произвольно из какого-нибудь ящика вынимаем один шарик. Сколькими разными способами это можно сделать? Из первого ящика шарик можно вытянуть m различными способами, из второго k: различными способами, всего n = m + k способами.

Правило произведения

Если объект А можно выбрать m способами, а после каждого такого выбора другой объект В можно выбрать (независимо от выбора А) k способами, то пары объектов А и В можно выбрать m·k способами.

Задача: В студенческой группе 14 девушек и 6 юношей. Сколькими способами можно выбрать, для выполнения различных заданий, двух студентов одного пола?

По правилу умножения двух девушек можно выбрать 14 ·13 = 182 способами, а двух юношей 6·5 = 30 способами. Следует выбрать двух студентов одного пола: двух студентов или студенток. Согласно правилу сложения таких способов выбора будет 182 + 30 = 212.

Задача: Сколько можно записать двузначных чисел в десятичной системе счисления?

Поскольку число двузначное, то число десятков (m) может принимать одно из девяти значений: 1,2,3,4,5,6,7,8,9. Число единиц (k) может принимать те же значения и может, кроме того быть равным нулю. Отсюда следует, что m = 9, а k= 10. Всего получим двузначных чисел n = m ·k = 9·10 =90.

Следствие

Правило произведения справедливо и для любого конечного числа объектов.

Если некоторый объект Аi (i = 1, 2, … , n) можно выбрать Кi (i = 1, 2, … , n) способами (причем, каждый следующий объект выбирается независимо от выбора предыдущего объекта), то объекты А1, А2, … , Аn можно выбрать k = k1 · k2 ·…· kn способами.

Например, сколькими способами можно составить трехзначное число, делящееся на 5? Число имеет три позиции, каждую из которых мы назовем событием:

событие А1 –число сотен, их можно выбрать k1 =9 (все цифры, кроме 0) способами;

событие А2 – число десятков, их можно выбрать k2 = 10 (все цифры, включая 0) способами;

событие А3 – число единиц, которым удовлетворяет только две цифры: 0 и 5, следовательно, k3 = 2. Таким образом, всего получаем n = k1 · k2 · k3 = 9 · 10 · 2 = 180 чисел.

Типы соединений

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

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

Множество будем записывать, располагая его элементы в фигурных скобка {a, b, c, … , e, f}.

Во множестве порядок элементов роли не играет, так {a, b} = {b, a}.

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

Множества элементов называются соединениями.

Различают три типа соединений:

перестановки из n элементов;

размещения из n элементов по m;

сочетания из n элементов по m (m < n).

Перестановки. Число перестановок

На практике часто возникают задачи, связанные с установлением порядка во множестве. Например, число мест равно количеству людей, на которых мы должны разместить их. Такая ситуация встречается часто – рассадить n человек на n мест, или приписать каждому человеку номер. Первый человек может выбрать любое из n мест, второй человек выбирает из (n - 1) оставшихся мест, третий человек может выбрать из уже (n - 2) мест, …, предпоследний человек выбирает из 2 мест, последний человек получает последнее место. Мы получаем произведение всех целых чисел от n до 1.

В общем виде произведение всех целых чисел от 1 до n включительно обозначают n! = 1·2·3…(n – 2) · (n – 1) · n.

Определение: Установленный в конечном множестве порядок называют перестановкой его элементов.

Перестановки можно образовывать из элементов любого конечного множества. Число перестановок из n элементов обозначают Рn. Возьмем одноэлементное множество {a}. Ясно, что один элемент можно упорядочить единственным образом, следовательно, Р1 = 1.

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

Возьмем двух элементное множество {a, b}. В нем можно установить два порядка: {a, b} или {b, a}. Следовательно, число перестановок из двух элементов Р2 = 2.

Три буквы во множестве {a, b, c} можно расположить, по порядку шестью способами: {a, b, c}{a, c, b}{b, a, c}{b, c, a}{c, b, a}{c, a, b}.

Следовательно, общее число способов упорядочения трех элементов множества Р3 = 3 · Р2 = 3 · 2 · 1 = 6.

Рn = n · (n - 1) · (n – 2) · … · 2 · 1 = n!

Определение: Пусть n - натуральное число. Через n! (читается "эн факториал") обозначается число, равное произведению всех натуральных чисел 1 от до n:n! = 1 · 2 · 3 · ... · n. В случае, если n = 0, по определению полагается: 0! = 1.

Пример:

Найдем значения следующих выражений:

 1! = 1

 2! = 1 · 2 = 2

 3! = 1 · 2 · 3 = 6

 

Задача 1.

Чему равно а)Р5 б) Р3

Задача 2.

Упростите а) 7! · 8 = 8! б) 12! · 13 ·14 = 14! в) κ! · (κ + 1) = (κ + 1)!

Размещения. Упорядоченные множества

Определение: Множество вместе с заданным порядком расположения его элементов называется упорядоченным множеством. Если в упорядоченном множестве изменить расположение элементов, то мы получим другое, отличное от первого множество.

В комбинаторике конечные упорядоченные множества называются размещениями.

Число размещений из n элементов по m обозначают Anm (читают А из эм по эн).

При m = 0 по формуле получаем: An0 = 1.

Это верно: существует только одно пустое множество, оно является подмножеством любого множества.

Заметим еще, что 0! = 1; 1! = 1; и Ann = Рn = n!

 Пусть исходное множество состоит из букв (а, в, с). Ставится задача: посчитать количество размещений из трех элементов по два: A32.

Будем составлять упорядоченные двухэлементные подмножества из данных трех элементов а, в, с.

Для наглядности составим таблицу, где и запишем все возможные подмножества.   а     в    с

а     (а,а)  (а,в)  (а,с)

в    (в,а)  (в,в)  (в,с)

с    (с,а)  (с,в)  (с,с)

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

В дальнейшем размещения без повторений мы будем называть одним словом – «размещения».

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

Будем составлять упорядоченные двухэлементные подмножества из данных трех элементов а,в,с. (а,в); (а,с); (в,с); (в,а); (с,а); (с,в).

 На первое место можно поставить любой из трех элементов, это можно сделать тремя способами, на второе место – любой из оставшихся элементов, то есть двумя способами, всего получим 3 · 2 соединений,т.е. A32 = 3 · 2 = 6.

Задача 1: Учащиеся 11-го класса изучают 9 учебных предметов. В расписании учебных занятий на один день можно поставить 4 различных предмета. Сколько существует различных способов составления расписания на один день?

Решение: Имеем 9-элементное множество, элементы которого учебные предметы. При составлении расписания мы будем выбирать 4-элементное подмножество и устанавливать в нем порядок. Число таких способов равно числу размещений из девяти по четыре, то есть A94:

Сочетания и некоторые свойства сочетаний

Сочетания из n по m m-элементные подмножества n-элементного множества.

Пример: Решим следующую задачу. Пусть в коробке находится пять пронумерованных шаров {1, 2, 3, 4, 5}. Перечислите все способы выбора двух шаров из этих пяти.

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

Обратите внимание, что подмножества (2,1) и (1,2) содержат один и тот же набор элементов и поэтому отождествляются. Итак, у пятиэлементного множества 10 двухэлементных подмножеств.

Рассмотрим все подмножества, состоящего из трех элементов {a, b, c}.

Их восемь:

Ø – пустое множество, как принадлежащее любому множеству;

{a}, {b}, {c} – одноэлементные 3 множества;

{a, b}, {a, c}, {b, c} – двухэлементные 3 множества;

{a, b, c} – одно множество из трех элементов, то есть полное рассматриваемое множество.

В сумме получили 8 различных подмножеств.

Число подмножеств, m элементов в каждом, содержащихся во множестве из n элементов, обозначается Cnm (читается "це из эн по эм") Буква C выбрана для обозначения числа сочетаний в связи тем, что по-французски слово "сочетание" - "combinaison" - начинается с этой буквы.

C52 = 10

В комбинаторике конечные множества называются сочетаниями.

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

Важно, какие конкретно элементы множества входят в каждое соединение.

Сочетания с повторениями

Сочетание с повторениями – каждый элемент, входящий в соединение, может быть представлен более чем одним элементом:

В дальнейшем сочетание без повторений мы будем называть одним словом – «сочетание».

Задача: В классе 22 учащихся. Двух из них следует назначить дежурными. Сколькими способами это можно сделать?

Замечание

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

Типичные задачи, в которых обычно путаются учащиеся

Сочетания 

1. Сколько рукопожатий получится, если здороваются 5 человек?

 {Вася, Петя} = {Петя, Вася} – одно и тоже.

 Значит, порядок неважен, значит это подмножество по два элемента из 5, значит это сочетание из пяти по два.

Размещения

2. Сколькими способами пять человек могут обменяться фотографиями?

 {Вася, Петя} ≠ {Петя, Вася} – разные обмены.

 Значит, порядок важен, значит это последовательность по два элемента из 5, значит это размещение из пяти по два.

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

1. 1. Сколькими способами n человек могут сесть на одной скамейке? Pn = n!   
   2. Сколькими способами n человек могут сесть за круглым столом?