Теория вероятностей. Комбинаторика. Часть 2

Василиса Волконская

Теория вероятностей. Комбинаторика. Часть 2

Содержание:

1) Основные понятия.

2) Комбинации без повторения элементов.

3) Свойства сочетаний.

4) Комбинации с повторениями элементов.

5) Решение различных задач.

Комбинаторика.

1)) Основные понятия.

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

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

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

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

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

Если множество А состоит из m элементов; a множество B состоит из k элементов; причём эти множества не имеют общих элементов, то выбор а или b, где а принадлежит А, b принадлежит B, можно осуществить n + k способами.

Если элемент А1 можно выбрать n1 способами, элемент А2 можно выбрать n2 способами, элемент A3 можно выбрать n3 способами и так далее; и элемент Аk можно выбрать nk способами, отличными от предыдущих способов (к - 1), то выбор одного из элементов, или А1, или A2, или Аk, может быть осуществлён n1 + n2 + … + nk способами; при условии, что выборы элементов (объектов) А1, А2, Ak несовместны.

Выборы объектов несовместны, если выбирая один из объектов, мы одновременно не выбираем ни какой из других объектов.

В основе правила суммы лежит следующее свойство:

Если попарно не пересекающиеся множества А1, А2, … Aк состоят из n1, n2, …, nk элементов соответственно, то объединение этих множеств содержит n1 + n2 + … + nk элементов.

Правило суммы можно обобщить и для трёх или более множеств.

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

Если элемент a можно выбрать m способами; и после каждого такого выбора элемент b можно выбрать k способами, то выбор а и b в указанном порядке можно осуществить m × k способами.

Если элемент A1 можно выбрать n1 способами, элемент А2 (после того, как A1 уже выбран) можно выбрать n2 способами, элемент Аk (после того, как все предыдущие объекты уже выбраны) можно выбрать nk способами, то упорядоченный выбор всех элементов А1, А2, …, Аk можно выбрать n1 × n2 × … × nk способами.

Правило произведения можно обобщить и на большее количество элементов.

Пример один.

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

Решение.

По признаку делимости числа на пять (кратности 5) число делится на пять, если оно оканчивается на 5 или на 0.

Двузначных чисел 90.

Из них:

1. Девять чисел оканчиваются на ноль (10, 20, 30, …, 90);

2. Девять чисел оканчиваются на пять (15, 25, 35, …, 95).

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

9 + 9 = 18

Ответ: 18

Пример два.

Пользуясь правилом произведения посчитать количество различных чётных трёхзначных чисел, которые можно составить, используя цифры 0, 1, 7, 5, 8.

Решение:

Трёхзначное число состоит из трёх цифр xyz

Первая цифра x - это количество сотен.

Вторая цифра у - это количество десятков.

Третья цифра z - это количество единиц.

Если число трёхзначное, то количество сотен не должно равняться нулю; а то получится двузначное число.

Если число чётное, то оно должно оканчиваться чётной цифрой или нулём.

Так как ноль первым быть не может, то первую цифру мы можем выбрать четырьмя способами.

Потому что первая цифра может быть и чётной и нечётной.

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

Третья цифра должна быть чётной или нулём.

Так как трёхзначное число чётное.

Значит, третью цифру мы можем выбрать двумя способами; потому что две цифры из данных чисел чётные (8 и 0).

Всего искомых чисел:

4 × 5 × 2 = 40

Ответ: 40.

2)) Комбинации без повторения элементов.

Пусть задано множество М, состоящее из n различных элементов.

M = {a1, a2, …, an}

1. Перестановки без повторений.

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

Теорема.

Число перестановок Pn из n элементов, вычисляется по формуле:

Pn = n!

n! = n × (n - 1) × … × 3 × 2 × 1

Доказательство:

Если нам дано множество различных элементов и нужно определить сколькими способами их можно переставить местами, то первый элемент можно прибавить n способами, второй элемент можно прибавить n - 1 способами … последний элемент можно прибавить одним способом.

Pn = n × (n - 1) × … × 3 × 2 × 1 = n!

Пример один.

Сколькими способами можно три различные книги расположить на полке.

P3 = 3! = 3 × 2 = 6 (способов).

Ответ: 6 способов.

Элементы различаются только порядком расположения.

Если решать эту задачу методом перебора, то обозначим первую книгу a, вторую книгу b, третью книгу c.

Теперь посмотрим, как их можно представить:

abc; acb; bac; bca; cab; cba

Получим шесть способов.

Ответ: 6 способов.

Если будет больше элементов для перестановки, перебирать их будет трудно.

Поэтому будем использовать формулу.

Пример два.

Сколькими способами можно рассадить шесть человек на лавке.

P6 = 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720 способов.

Ответ: 720 способов.

Элементы различаются только порядком расположения.

2. Размещения без повторений.

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

Теорема.

Доказательство:

Если нам дано множество различных элементов; и нужно найти, сколько элементов m можно выбрать из элементов n, то первый элемент можно выбрать n способами, второй элемент можно выбрать (n - 1) способами, третий элемент можно выбрать (n - 2) способами, … последний элемент можно выбрать (n - m + 1) способами.

Если n = m, то:

Так как 0! = 1

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

Пример один.

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

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

Значит, это размещения с повторениями.

Ответ: 6 способов.

Если решать эту задачу методом перебора, то:

Обозначим первую книгу а, вторую книгу b, третью книгу c.

Теперь посмотрим, как можно выбрать две из трёх:

ab; ac; ba; bc; ca; cb

Получим шесть способов.

Ответ: 6 способов.

Пример два.

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

Решение.

Уроки различные, из разных предметов. Значит, они отличаются составом.

И в расписании уроки можно расположить по-разному. Значит, они различаются и порядком.

= 10 × 9 × 8 × 7 × 6 × 5! / 5! = 30240 (способов).

Ответ: 30240 способов.

3. Сочетания без повторений.

Если комбинации из n элементов по m элементам, отличаются только составом элементов, то их называют сочетаниями из n элементов по m элементам.

Теорема.

Доказательство:

Если нам надо множество различных элементов, которые отличаются только составом; и нужно найти, сколько элементов m можно выбрать из элементов n, то первый элемент можно выбрать n способами, второй элемент можно выбрать (n - 1) способами … и последний элемент можно выбрать (n - m + 1) способами.

И так как расположение элементов, которые выбирали нам не важно, то эти выборы мы поделим на перестановку по m элементам.

= n × (n - 1) × (n - 2) × … × (n - m + 1) / (m - 1) × … × 2 × 1 = n! / m! (n - 1)!

Из этой теоремы можно сделать вывод, что:

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

Сочетания используются, если элементы отличаются только составом.

Перестановки используются, если элементы только переставляются местами (отличаются расположением).

Значит, размещения из n элементов по m элементам, равны произведению сочетаний из n элементов по m элементам на перестановки по m элементам.

= (n! / m! (n - m)!) × m! = n! m! / m! (n - m)! = n! / (n - m)!

3)) Свойства сочетаний.

1. Сочетания из n элементов по m элементам, равно сочетанию из n элементов по n - m элементам.

2.

3.

Пример 1.

В шахматном турнире участвуют 16 человек.

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

Решение:

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

= 16! / 2! × 14! = 16 × 15 × 14! / 2 × 14! = 16 × 15 / 2 = 120 (способов).

Ответ: 120 способов.

4)) Комбинации с повторениями элементов.

Пусть дано множество M {a1, a2, …, an}

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

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

Если в размещениях из n элементов по m элементам, некоторые из элементов или все, могут оказаться одинаковыми, то такие размещения называются размещениями с повторениями.

Теорема.

Пример 1.

Сколькими способами можно составить трёхзначное число, используя цифры 1 и 2.

Решение:

Трёхзначное число, которое можно составить из цифр 1 и 2 представляет собой размещения с повторениями.

Так как элементы 1 и 2 отличаются, и составом, и порядком расположения и могут повторяться.

Мы из двух элементов должны составить трёхзначное число.

Если решать эту задачу методом перебора, то получим:

1 1 1; 1 1 2; 1 2 1; 2 1 1; 2 2 1; 2 1 2; 1 2 2; 2 2 2

Это все варианты.

Получили восемь способов.

Ответ: 8 способов.

Пример 2.

В конкурсе по 4 кульминациям участвуют 10 кинофильмов.

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

Решение:

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

Причём могут повторяться несколько раз; то есть представляют размещения с повторениями из десяти элементов по пять элементов.

Ответ: 10 000

Пример 3.

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

Решение:

Уроки из различных предметов.

Они отличаются составом и в расписании уроки можно расположить по-разному. Значит, они различаются и порядком.

И уроки в расписании могут повторяться; то есть они представляют размещения с повторениями из десяти элементов по пять элементов.

Ответ: 100 000

2. Перестановки с повторениями.

Если в перестановках из общего числа n элементов, есть m различных элементов; при этом первый элемент повторяется n1 раз, второй элемент повторяется n2 раза, … m - ный элемент повторяется n раз; причём n1 + n2 + n3 + … + n m = n

То такие перестановки называются перестановками с повторениями

Теорема.

Число Pn (n1, n2 … nm) перестановок с повторениями заданного состава, вычисляется по формуле:

Pn (n1, n2 … nm) = n! / n1! × n2! × nm!

Доказательство:

Рассмотрим m различных элементов.

a1: a1 (1) a1 (2) a1 (3) … a1 (n1)

a2: a2 (1) a2 (2) a2 (3) … a2 (n2)

… … …

am: an (1) an (2) an (3) … an (nm)

n1 + n2 + … + nm = n

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

1. Выбрать перестановку с повторениями из элементов a1 a2 … аm заданного состава n1, n2, … nm

Это можно сделать Pn (n1, n2 … nk) способами.

2. На тех местах, где расположены элементы a1, записать перестановку a1 (1) a1 (2) a1 (3) … a1 (n1)

Это можно сделать n1! способами.

На тех местах, где расположены элементы a2 записать перестановку элементов a2 (1) a2 (2) a2 (3) … a2 (n2)

Это можно сделать n2! способами.

Указанными способами можно получить любую перестановку из n данных различных элементов; причём разными способами выбора в пунктах 1) и 2) совпадают разные перестановки n данных различных элементов.

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

Pn (n1, n2 … nm) = n1! × n2! × n3! × … × nm!

С другой стороны это равно n!

Отсюда следует формула:

Pn (n1, n2 … nm) = n! / n1! n2! … nm!

Пример 1.

Имеется два одинаковых учебника по математике и два одинаковых учебника по физике.