Схема выбора без возвращений

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

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

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

Число размещений из элементов по элементов обозначается символом (<<A из эн по эм>>) и вычисляется по формуле

или

, где , , .

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

Пример 3. Составить различные размещения по из элементов множества ; подсчитать их число.

Из трёх элементов можно образовать следующие размещения по два элемента: , , , , , . Число размещений из трёх по два равно .

Перестановкой из элементов по элементов. Число перестановок по из элементов обозначается символом (<<пэ из эн>>) и вычисляется по формуле

.

Эта формула следует из определения перестановки:

.

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

Из элементов данного множества можно составить следующие перестановки: , , , , , . По формуле для расчёта перестановок имеем: .

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

Искомое число способов равно числу перестановок из элементов (книг), т.е. .

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

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

Число сочетаний из элементов по обозначается символом

(<<цэ из эн по эм>>) и вычисляется по формуле.

или

.

Число размещений из элементов по можно найти следующим образом: выбрать элементов из множества, содержащего элементов (это можно сделать способами); затем в каждом из полученных сочетаний (подмножеств) сделать все перестановки для упорядочения подмножеств (это можно сделать способами). Следовательно, по правилу умножения, можно записать: . Отсюда .

Запишем следующее очевидное выражение

По существу эта формула представляет собой выражение для числа перестановок из элементов. Эта формула записана справа налево. Из этой формулы следует, что . Из этого соотношения следует, что .

С учётом последнего соотношения запишем

Имеют место формулы:

Эта формула доказывается очень просто. В выражении следует положить .

.

.

, .

Формула выражает число всех подмножеств из элементов (оно равно . Числа являются коэффициентами в разложении бинома Ньютона:

.

Пример 5. Составить различные сочетания по 2 из элементов множества

; подсчитать их число.

Из трёх элементов можно образовать следующие сочетания по два элемента: . Их число .

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

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

Далее: красную гвоздику можно выбрать способами. Выбрать две розовые гвоздики из имеющихся четырёх можно

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

способами.