Лекция "ЭЛЕМЕНТЫ КОМБИНАТОРИКИ"

Лекция

Тема: «Элементы комбинаторики»

Перечень вопросов, рассматриваемых в теме:

1. Элементы комбинаторики – комбинации без повторений

1.1. Размещения

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

1.3. Сочетания

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

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

2.2. Правило умножения 

3. Элементы комбинаторики – комбинации с повторениями

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

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

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

4. Примеры и разбор решения заданий тренировочного модуля

1. Элементы комбинаторики – комбинации без повторений

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

1.1. Размещения. Пусть имеется множество, содержащее n элементов. Каждое его упорядоченное подмножество, состоящее из m элементов, называется размещением из n элементов по m элементов:

_, где

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

Решение. Число способов равно числу размещений из 7 элементов по 4, т.е. равно .

Получаем

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

1.2. Перестановки. Размещения из n элементов по n элементов называются перестановками из n элементов:

Пример 2. Сколько шестизначных чисел, кратных пяти, можно составить из цифр 1, 2, 3, 4, 5, 6 при условии, что в числе цифры не повторяются?

Решение. Цифра 5 должна стоять на последнем месте. Остальные пять цифр могут стоять на оставшихся пяти местах в любом порядке. Следовательно, искомое число шестизначных чисел, кратных пяти, равно числу перестановок из пяти элементов, т.е.

Ответ: 120 чисел.

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

Решение. Получатся наборы: БАР, БРА, АРБ, АБР, РАБ, РБА.

По формуле получаем:  наборов. 

Ответ: 6 наборов.

1.3. Сочетания. Пусть имеется множество, состоящее из n элементов. Каждое его подмножество, содержащее m элементов, называется сочетанием из n элементов по m элементов:

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

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

=120.

Ответ: 120 матчей.

Свойства сочетаний:

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

2.1. Правило суммы (правило «или») — одно из основных правил комбинаторики. Если элемент   можно выбрать   способами, а элемент  можно выбрать  способами, то выбрать   или   можно   способами.

2.2. Правило умножения (правило «и») — одно из основных правил комбинаторики. Если элемент   можно выбрать    способами, и при любом выборе   элемент   можно выбрать   способами, то пару можно выбрать  способами. Естественным образом обобщается на произвольное количество независимо выбираемых элементов.

Пример 6. Выбрать книгу и диск из книг и дисков можно  способами.

3.Элементы комбинаторики – комбинации с повторениями

3.1. Размещение с повторениями или упорядоченная выборка с возвращением — это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз. Если при выборке элементов из – элементы возвращаются обратно и упорядочиваются, то это размещения с повторениями или упорядоченная выборка с возвращением. 

Число размещений с повторениями из   по m, обозначаемое , равно:

Пример 7. Например, количество вариантов 3-значного кода, в котором каждый знак является цифрой от 0 до 9 и может повторяться, равно:

Пример 8. Сколько можно составить «слогов» по 2 буквы с повторениями из 4 элементов:

Количество таких «слогов» по 2 буквы равно   Эти размещения следующие:

3.2. Сочетание с повторениями или неупорядоченная выборка с возвращением — это сочетание «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз. Если при выборке элементов из – элементы возвращаются обратно без последующего упорядочивания, то говорят, что это сочетания с повторениями или неупорядоченная выборка с возвращением.

 Число сочетаний с повторениями из n по m, обозначаемое , равно:

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

Число перестановок c повторениями (  различных элементов, где элементы могут повторяться

раз и где общее количество элементов)

вычисляется по формуле:

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

Решение.

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

По формуле получаем:

  аборов.

Ответ: 12 наборов.