Сочетания

Пусть некоторое множество содержит n элементов.

Определение 4. Всякое m- элементное подмножество n- элементного множества называется
сочетанием из n элементов по m.

- число всех сочетаний.

(3)

Пример 5. Для соревнований из 30 спортсменов надо выбрать трех человек. Сколькими способами это
можно сделать?
Решение. Команда из 3 спортсменов - это подмножество из трех элементов, то есть сочетание из 30 по 3, поэтому количество способов выбора таких команд вычисляется по формуле (3):

.

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

1.
2. .

Из данных свойств следует, что , тогда , далее ,

,

и так далее.
Можно расположить эти числа в виде таблицы:

.....................................................

или

1 1

1 2 1

1 3 3 1

1 4 6 4 1

.......................

Эта таблица в виде треугольника называется треугольником Паскаля.

Определение 5. Выражение a+b называется биномом.

(4)

Формула (4) называется биномиальной формулой Ньютона, а коэффициенты называются биномиальными
коэффициентами. Из данной формулы вытекает следующее свойство числа сочетаний

(5)

Вопрос. .

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

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

Определение 6. Сочетание с повторениями - это m- элементное подмножество множества, содержащего n видов
элементов, в котором элементы повторяются.

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

(5)

Пример 6. В кондитерском магазине продаются пирожные четырех видов: наполеоны, эклеры, песочные и бисквитные. Сколькими способами можно купить 7 пирожных?
Решение. Любая покупка - это подмножество, в котором могут быть одинаковые элементы, поэтому
это сочетание с повторениями. Число всех возможных покупок находим по формуле (5):
.

Вопрос. В формуле (5) m может быть больше n.

Размещения

Определение 7. Упорядоченное m - элементное подмножество n- элементного множества называется размещением.

- число всех размещений из n элементов по m. Число всех размещений из n по m больше числа всех
сочетаний из n по m, так как из каждого подмножества из m элементов с помощью перестановок можно получить m! упорядоченных подмножеств, получаем формулу для числа размещений

(6)

Пример 7. В группе 25 человек. Нужно выбрать актив группы: старосту, заместителя старосты и профорга.
Сколькими способами это можно сделать?
Решение. Актив группы - это упорядоченное подмножество из трех элементов, так как надо выбрать не только
трех человек, но и распределить между ними должности, значит актив группы - это размещение, число всех
размещений вычисляем по формуле (6):
.

Вопрос. Во сколько раз число сочетаний из 20 по 4 меньше числа размещений из 20 по 4?

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

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

Определение 8. Упорядоченные m- элементные подмножества n- элементного множества, в которых элементы могут повторяться, называются размещениями с повторениями.

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

(7)

Пример 8. В лифт десятиэтажного дома вошли 5 человек. Каждый из них может выйти на любом этаже,
начиная со второго. Сколькими способами они могут это сделать?
Решение. Так как каждый человек может выйти на любом этаже, начиная со второго, то этажей для выхода 9.
Надо выбрать этажи для возможности выхода каждого человека: для первого человека - можно выбрать любой из девяти этажей, аналогично для остальных пассажиров, тогда по формуле (7):
способов.

Вопрос. Вычислить .