Лекция 10

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

Комбинаторика – раздел элементарной математики, в котором для конечных множеств рассматриваются различные соединения элементов, такие, как сочетания, размещения, перестановки, а также все виды соединений с повторениями. Задачи комбинаторики впервые рассматривались в связи с возникновением теории вероятностей, где к задачам комбинаторики приводит подсчет вероятностей на основе гипотезы равновозможных элементарных событий.

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

Мы выбираем из этой совокупности элементов. Произвольная упорядоченная выборка из этих элементов (;
) называется соединением. Эта выборка может быть как без повторений, так и с повторениями.

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

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

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

Рассмотрим следующие возможные схемы выбора:

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

И в том, и в другом случае результатом выбора является набор из номеров шариков. Удобно считать, что шарики всегда выбираются последовательно, по одному (с возвращением или без). Условимся, какие результаты мы будем считать различными. Есть ровно две возможности:
Выбор с учетом порядка: два набора номеров шариков считаются различными, если они отличаются составом или порядком номеров. Так, при выборе трех шариков из урны, содержащей 5 шариков, наборы (1,5,2), (2,5,1) и (4,4,5) различны, если производится выбор с учетом порядка.
Выбор без учета порядка: два набора номеров шариков считаются различными, если они отличаются составом. Наборы, отличающиеся лишь порядком следования номеров, считаются одинаковыми. Так, в примере выше первые два набора (1,5,2) и (2,5,1) есть один и тот же результат выбора, а набор (4,4,5) — другой результат выбора.

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

Выбор без возвращения, с учетом порядка

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

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

Чтобы определить число размещений из элементов по , будем строить произвольное соединение последовательно. Сначала определим его первый элемент Очевидно, что из данной совокупности элементов его можно выбрать различными способами. После выбора первого элемента , для второго элемента остается способов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Для элементов формула приобретает вид:

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

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

Общее количество выборок в схеме выбора элементов из без возвращения и с учетом порядка называется числом перестановок
и определяется по формуле