Леммы 1 и 2 называются основными правилами комбинаторики

Пусть имеется множество из n элементов a₁, a₂,a_n. Будем рассматривать выборку объема k из n элементов. Все выборки можно классифицировать по 2 признакам:

1. упорядоченные и неупорядоченные.

2. с возвращением и без возращения.

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

Если выборка считается неупорядоченной, то все выборки с одним и тем же составом элементов отождествляются.

Пример. Возьмем множество из трех элементов {1,2,3}. Выбираем k=2.

Составим общую таблицу числа выборок:

		С возвращением
		Без возвращения
упорядоченная	Неупорядоченная	Выборка

Упорядоченная выборка с возвращением ). Каждый элемент выборки может принимать n значений, т.е. число выборок . Упорядоченная выборка без возвращения .

o Упорядоченная выборка без возвращения называется размещением. Число размещений .

Пример. В лифт 12-этажного дома зашли 3 человека. Найти вероятность того, что все вышли на разных этажах.

n=11³.

, .

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

P_k-число перестановок из k элементов. , поскольку 0!=1.

o Произвольное k-элементное подмножество множества n элементов называется сочетанием из n элементов по k элементов. Сочетание—это неупорядоченная выборка объема k из n элементов. Обозначается число всех сочетаний из n элементов по k элементов через .

. , где .

.

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

1. .

2. .

3. .

4. .