Элементы комбинаторики - сочетания

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

Сочетания

2.

Вопрос дня:
КАК РАЗЛИЧАТЬ
ПРИМЕНЕНИЕ ТЕОРЕМ?

3.

Вопрос дня: КАК различить:
задача на перестановки или
размещения?
Количество рассматриваемых элементов множества
совпадает с исходным
количеством элементом
меньше исходного
количества элементов

4.

Перестановкой из n элементов
множества называется
расположение этих элементов
в определённом порядке
Размещением из n элементов
по k элементов называется любое
множество, состоящее из k элементов,
взятых в определённом порядке из данных
n элементов.
Сочетанием из n элементов по k называется
любое множество, составленное из k
элементов, выбранных из данных n элементов

5.

Пусть имеются пять гвоздик разного цвета:
a, b, c, d, e.
Требуется составить букет из трёх гвоздик.
Если в букет входит гвоздика a, то можно
составить такие букеты:
abc, abd, abe, acd, ace, ade
Если в букет не входит гвоздика a, но входит
гвоздика b, то можно составить такие букеты:
bcd, bce, bde
Если в букет не входят ни гвоздика a, ни
гвоздика b, возможен один вариант
составления букета c, d, e

6.

Указали все возможные способы
составления букетов, в которых поразному сочетаются три гвоздики из
данных пяти
Составили все возможные СОЧЕТАНИЯ
из 5 элементов по 3 элемента.
Обозначение:
С
k
n
В рассмотренном примере
С53 10
«combinations»

7.

Рассмотрим множество, содержащее n элементов, и
из его элементов составлены все возможные
сочетания по k элементов.
Число таких сочетаний равно Сnk
В каждом сочетании можно выполнить
перестановок
Рk
В результате получим все размещения ,
которые можно составить из n элементов по k
Их число равно
значит
Отсюда
Ank Cnk Pk
k
A
Сnk n
Pk
Аnk

8.

Другими словами:
n(n 1)(n 2) .... (n (k 1))
C
1 2 3 4 .... (k 1) k
k
n
Несложные преобразования
приводят полученную формулу к виду:
n!
С
k! (n k )!
k
n
Запомним 0!=1

9. Пример 1:

Из 15 членов туристической группы надо
выбрать 3 дежурных. Сколькими способами это
можно сделать?
Речь идёт о сочетаниях из 15 элементов по 3.
Сnk C153
n!
15! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 13 14 15
455
k! (n k )! 3! 12! 1 2 3 1 2 3 4 5 6 7 8 9 10 11 12 13
1 2 3

10. Пример 2:

Из вазы с фруктами, в которой лежит 9 яблок и
6 груш, надо выбрать 3 яблока и 2 груши.
Сколькими способами можно сделать такой
выбор?
3
С
Выбрать 3 яблока из 9 можно
9 способами,
А выбрать 2 груши из 6 можно С 2 способами.
6
Таким образом, учитывая правило умножения, выбор,
соответствующий условию задачи, можно сделать
9 8 7 6 5
С С
1260
1 2 3 1 2
3
9
2
6

11.

Вопрос дня: как распознать решение задачи