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

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

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

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

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

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

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

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

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

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

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

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

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

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