Урок "Основные понятия и принципы комбинаторики

ОСНОВНЫЕ ПОНЯТИЯ КОМБИНАТОРИКИ

Цель: знать понятия перестановки, размещения, сочетания.

ХОД УРОКА

1. ОРГАНИЗАЦИОННЫЙ МОМЕНТ

1. ИЗУЧЕНИЕ МАТЕРИАЛА

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

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

1. Правило сложения

Пусть некоторую работу можно выполнить с помощью k взаимоисключающих операций. При этом первая операция может быть реализована n₁ способами, вторая – n₂ способами, k-я – n_k способами. Тогда работу можно выполнить n₁ + n₂ + ... + n_k способами.

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

Пусть некоторую работу можно выполнить с помощью k последовательных операций. При этом первая операция может быть реализована n₁ способами, вторая – n₂ способами, k-я – n_k способами. Тогда всю работу можно выполнить способами.

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

Решение. Сигналы можно подавать двумя, тремя и четырьмя флагами. Первым для сигнала из двух флагов может быть любой из имеющихся 4 флагов (4 способа), после чего вторым – любой из трех оставшихся (3 способа). Тогда, согласно правилу умножения, количество возможных способов подачи сигнала из 2 флагов составит 43=12. Аналогично для сигнала из трех флагов имеем: 432=24 способа. Наконец, для сигнала из 4 флагов получим 4321=24 способа.

Все рассмотренные выше варианты предполагают выполнение последовательных операций по выбору флага для сигнала и потому рассчитываются по правилу умножения. Однако подачи сигналов 2, 3 и 4 флагами является взаимоисключающими операциями и потому общее число сигналов можно получить как сумму способов для сигналов из 2, 3 и 4 флагов, т.е. 24+24+12=60 способами. Таким образом, для определения общего количества сигналов используется правило сложения.

2.2. Основные виды комбинаторных соединений

В комбинаторике различают три вида различных соединений (комбинаций) элементов произвольного множества:

– перестановки;

– размещения;

– сочетания.

Рассмотрим последовательно все виды соединений и соответствующие формулы подсчета их количества.

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

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

Общее количество возможных перестановок из m элементов обозначается P_m и определяется выражением P_m = m! = (1)

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

Решение. Общее количество возможных способов расположения книг определяется согласно выражению (1): Р3 = 3! = 6 .

Легко заметить, что такой же результат можно получить, применяя правило умножения. На первое место на полке можно поставить любую из 3 книг (3 способа), после чего на второе – любую из двух оставшихся (2 способа), после чего на третьем месте будет стоять последняя неразмещенная книга (1 способ), что по правилу умножения дает 321 = 6 способов. Таким образом, правило умножения можно считать логическим обоснованием формулы (1).

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

Определение 2. Размещениями из элементов по m называют такие соединения m элементов, которые отличаются друг от друга хотя бы одним новым элементом или порядком их следования (m≤ n).

Общее количество возможных размещений из n элементов по m обозначается и определяется выражением (2)

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

Решение. Общее количество возможных способов расположения книг определяется согласно выражению (2):

Опять же, основанием для использования формулы (2) является правило умножения. На первое место на полке можно поставить любую из 3-х книг (3 способа), после чего на второе – любую из двух оставшихся (2 способа), что по правилу умножения дает 32=6 способов.

3. Сочетания

Определение 2. Сочетаниями из n элементов по m называют такие соединения m элементов, которые отличаются друг от друга хотя бы одним новым элементом (m ≤ n).

Общее количество возможных сочетаний из n элементов по m обозначается и определяется выражением (3)

Пример 4. Сколькими способами можно выбрать две книги из трех.

Решение. Общее количество возможных способов выбора книг определяется согласно выражению (3):

Эта задача отличается от примера 3 тем, что 2 книги, например, АВ и ВА, являются различными размещениями и одинаковыми сочетаниями, т.е. в сочетаниях не учитывается порядок элементов. Следовательно, количество сочетаний может быть получено из числа размещений путем его деления на число перестановок размещаемых (выбираемых) элементов. В данном случае число размещений 3 книг по 2 равно 6; число перестановок из двух выбираемых (или размещаемых в примере 3) книг равно двум, так что выбрать 2 книги из 3 можно 6/2 = 3 способами.

1. Общая связь между перестановками, размещениями и сочетаниями: (4)

2. Свойство сочетаний: (5)

1. ДОМАШНЕЕ ЗАДАНИЕ

Выучить конспект

1. ИТОГ УРОКА