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

Для формулирования и решения задач по комбинаторике используют следующие конфигурации: перестановки, размещения, сочетания.

Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое число (номер элемента) от 1 до n, где n - число элементов множества.

Перестановка.

Пусть мы имеем некое упорядоченное множество N состоящее из n различных элементов. Перестановкой из n элементов называется такой набор элементов множества, которые отличаются от исходного лишь порядком элементов. Обычно перестановка обозначается как P_n и рассчитывается по формуле:

P_n = n!

Размещение.

Пусть мы имеем некое упорядоченное множество N состоящее из n различных элементов. Размещением из n элементов по k будет называться упорядоченное подмножество из k не повторяющихся элементов выбранные из множества, состоящего из n элементов. Обычно перестановка обозначается как A_n^k и рассчитывается по формуле:

Сочетание.

Пусть мы имеем некое упорядоченное множество N состоящее из n различных элементов. Сочетанием из n элементов по k будет называться подмножество из k не повторяющихся элементов выбранные из множества, состоящего из n элементов. Подмножества, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений. Обычно сочетание обозначается как С_n^k и рассчитывается по формуле:

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

1. С_n⁰ = 1.

2. С_n^k = С_n^{n - k}.

3. С_n^k = С_{n - 1}^{k - 1} + С_{n - 1}^k

4. С_n⁰ + С_n¹ + С_n² + ... + С_n^{n - 1} + С_nⁿ = 2ⁿ.

Сочетание играет важную роль в математике. В частности, он используется в биноме Ньютона.

Бином Ньютона.

Бином Ньютона - это отношение, позволяющая представить выражение (a + b)ⁿ (n ∈ Z⁺) в виде многочлена, а именно:

(a + b)ⁿ = aⁿ + С_n¹a^{n - 1}b + С_n²a^{n - 2}b² + ... + С_n^ka^{n - k}b^k + ... + С_n^{n - 1}ab^{n - 1} + bⁿ.

Числа С_n¹, С_n², ... , С_n^{n - 1} называются биномиальными коэффициентами.

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

Слева указана степень n, справа значения соответствующих биномиальных коэффициентов.