Kitobni o'qish: «Теория вероятностей. Комбинаторика. Часть 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 представляет собой размещения с повторениями.