Элементы комбинаторики

Тема: Элементы комбинаторики

Записать конспект

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

Пусть имеется множество, содержащее n элементов. Каждое его упорядоченное подмножество, состоящее из k элементов, называется размещением из n элементов по k элементов:

, где n!=1*2*3*…*n

Пример. Группа учащихся изучает 7 учебных дисциплин. Сколькими способами можно составить расписание занятий на понедельник, если в этот день недели должно быть 4 различных урока?

Решение. Число способов равно числу размещений из 7 элементов по 4, т.е. равно . Получаем = .

Размещения из n элементов по n элементов называются перестановками из n элементов:

.

Пример. Сколько шестизначных чисел, кратных пяти, можно составить из цифр 1, 2, 3, 4, 5, 6 при условии, что в числе цифры не повторяются?

Решение. Цифра 5 обязана стоять на последнем месте. Остальные пять цифр могут стоять на оставшихся пяти местах в любом порядке. Следовательно, искомое число шестизначных чисел, кратных пяти, равно числу перестановок из пяти элементов, т.е. 5!=5*4*3*2*1=120.

Сочетания. Пусть имеется множество, состоящее из n элементов. Каждое его подмножество, содержащее k элементов, называется сочетанием из n элементов по k элементов:

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

Решение. Матчей состоится столько, сколько существует двухэлементных подмножеств у множества, состоящего из 16 элементов, т.е. их число равно .

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