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

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

Комбинаторика занимается различного рода соединениями, которые можно образовать из элементов некоторого конечного множества. Термин «комбинаторика» происходит от латинского combina – сочетать, соединять.

Комбинаторика – область математики, в которой рассматриваются задачи о тех или иных комбинациях объектов.

Правило суммы: пусть имеется n попарно непересекающихся множеств A ₁, A ₂, …, A_n, содержащих m ₁, m ₂, …, m_n  элементов соответственно. Число способов, которыми можно выбрать один элемент из всех этих множеств, равно

m ₁ + m ₂ + … + m_n.

Кортеж – конечная последовательность (допускающая повторения) элементов какого-нибудь множества.

Правило произведения: пусть имеется n множеств A ₁, A ₂, …, A_n содержащих m ₁, m ₂, …, m_n элементов соответственно. Число способов, которыми можно выбрать по одному элементу из каждого множества, т. е. построить кортеж (а ₁, а ₂,...,  а_n), где а_i Î А_i (i = 1, 2, …, n), равно

m ₁ ּ m ₂ ּ … ּ m_n.

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

Размещения без повторений (n различных элементов):

.

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

Пример 1. Возьмем буквы Б, А, Р. Какие размещения из этих букв, взятых по две, можно получить? Сколько таких наборов получиться, если: 1) буквы в наборе не повторяются; 2) буквы могут повторяться?

1) Получатся следующие наборы: БА, БР, АР, АБ, РБ, РА.

.

2) Получатся наборы: ББ, БА, БР, АА, АБ, АР, РР, РБ, РА.

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

Перестановки без повторений (n различных элементов):

Перестановки c повторениями (k различных элементов, где элементы могут повторяться n ₁, n ₂, …, n_k раз и n ₁ + n ₂ + … + n_k = n, где n – общее количество элементов):

Пример 2. Возьмем буквы Б, А, Р. Какие перестановки из этих букв можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) буква А повторяется два раза?

1) Получатся наборы: БАР, БРА, АРБ, АБР, РАБ, РБА.

2) Получатся наборы: БАРА, БРАА, БААР, ААРБ, ААБР, АБАР, АРАБ, АРБА, АБРА, РАБА, РААБ, РБАА.

 

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

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

Сочетания без повторений (n различных элементов, взятых по m):

.

Сочетания c повторениями (n элементов, взятых по m, где и элементы в наборе какой-нибудь комбинации могут повторяться):

.

Пример 3. Возьмем плоды: банан (Б), ананас (А) и репа(Р).Какие сочетания из этих плодов, взятых по два, можно получить? Сколько таких наборов получится, если: 1) плоды в наборе не повторяются; 2) можно брать по два одинаковых плода?

1) Получатся наборы: БА («банан, ананас» и «ананас, банан» – один и тот же набор), АР и РБ.

.

2) Получатся наборы: ББ, БА, БР, АА, АР, РР.

.

 

Контрольные вопросы

1. Приведите примеры множеств и их подмножеств.

1. Проиллюстрируйте примерами «из жизни» пересечение, объединение и разность множеств.

1. Постройте диаграммы Эйлера – Венна на свойства разности и дополнения множеств.

2. Что представляет собой кортеж?

3. Назовите виды комбинаций, где важен порядок при составлении наборов и где он не важен.

1. Какие комбинации называются перестановками?

1. Какие комбинации называются сочетаниями?

1. Какие комбинации называются размещениями?

4. В чем сходства и отличия таких комбинаций, как перестановки и размещения?

5. В чем сходства и отличия таких комбинаций, как сочетания и размещения?