Школьный курс комбинаторики обычно имеет дело с задачами выбора и расположения элементов некоторого, обычно конечного, множества, согласно неких правил.
Для формулирования и решения задач по комбинаторике используют следующие конфигурации: перестановки, размещения, сочетания.
Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое число (номер элемента) от 1 до n, где n - число элементов множества.
Перестановка.
Пусть мы имеем некое упорядоченное множество N состоящее из n различных элементов. Перестановкой из n элементов называется такой набор элементов множества, которые отличаются от исходного лишь порядком элементов. Обычно перестановка обозначается как Pn и рассчитывается по формуле:
Pn = n!
Пример:
Найти число перестановок множества, состоящего из трех элементов: A, B, C.
Согласно формуле, количество перестановок будет равно 3! = 6.
Действительно, это наборы (ABC),(ACB),(BAC),(BCA),(CAB),(CBA).
Размещение.
Пусть мы имеем некое упорядоченное множество N состоящее из n различных элементов. Размещением из n элементов по k будет называться упорядоченное подмножество из k не повторяющихся элементов выбранные из множества, состоящего из n элементов. Обычно перестановка обозначается как Ank и рассчитывается по формуле:
| Ank = | n! (n - k)! |
Пример:
Найти число размещений множества, состоящего из четырех элементов: A, B, C, D по два, т.е. сколько различных размещений по два элемента можно составить из указанного множества.
Согласно формуле, количество размещений будет равно 4!/(4-2)! = 24/2 = 12.
Действительно, это наборы (AB),(BA),(AC),(CA),(AD),(DA),(BC),(CB),(BD),(DB),(CD),(DC).
Сочетание.
Пусть мы имеем некое упорядоченное множество N состоящее из n различных элементов. Сочетанием из n элементов по k будет называться подмножество из k не повторяющихся элементов выбранные из множества, состоящего из n элементов. Подмножества, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений. Обычно сочетание обозначается как Сnk и рассчитывается по формуле:
| Сnk = | n! k!(n - k)! |
Пример:
Найти число сочетаний множества, состоящего из четырех элементов: A, B, C, D по два.
Согласно формуле, количество сочетаний будет равно 4!/2!(4-2)! = 24/4 = 6.
Действительно, это наборы (AB),(AC),(AD),(BC),(BD),(CD).
Свойства сочетаний:
1. Сn0 = 1.
2. Сnk = Сnn - k.
3. Сnk = Сn - 1k - 1 + Сn - 1k
4. Сn0 + Сn1 + Сn2 + ... + Сnn - 1 + Сnn = 2n.
Сочетание играет важную роль в математике. В частности, он используется в биноме Ньютона.
Бином Ньютона.
Бином Ньютона - это отношение, позволяющая представить выражение (a + b)n (n ∈ Z+) в виде многочлена, а именно:
(a + b)n = an + Сn1an - 1b + Сn2an - 2b2 + ... + Сnkan - kbk + ... + Сnn - 1abn - 1 + bn.
Числа Сn1, Сn2, ... , Сnn - 1 называются биномиальными коэффициентами.
С помощью следующей таблицы можно определить значения биномиальных коэффициентов для любой степени. Строится он следующим образом - любое число образуется суммой рядом стоящих чисел над ним. Именно потому эта таблица имеет название треугольник Паскаля.
Слева указана степень n, справа значения соответствующих биномиальных коэффициентов.
Пример:
Представить в виде многочлена (a + 1)4.
Согласно таблице, в случае четвертой степени коэффициенты результирующего многочлена будут равны 1, 4, 6, 4, 1.
И, действительно (a + 1)4 = a4 + 4a3 + 6a2 + 4a + 1.
