Комбинаторика. Курс лекций Дискретная математика

Пусть имеется множество из n элементов. Перестановкой называется конкретное размещение этих элементов в определенном порядке.
На рисунке слева изображены все возможные перестановки в множестве, элементами которого являются три разноцветных шарика. В данном случае n = 3, а числе всех перестановок равно 6.

Рассмотрим общий случай. Выберем первый элемент нашего множества. Имеется n способов его размещения на n позициях. Следующий элемент можно разместить n-1 способами, поскольку одно место уже занято. А количество вариантов размещения двух первых элементов, очевидно, равно nх(n–1). Размещение трех первых элементов имеет nх(n-1)х(n-2) вариантов. И так далее, рассуждая подобным образом, мы приходим к выражению nх(n-1)х(n-2)х…х2х1.
В математике принято обозначение
n! = 1 х 2 х … х (n-1) х n (читается как n-факториал)
Итак, число всевозможных перестановок в множестве из n элементов выражается формулой
Pn = n!
Кстати, в нашем примере число шариков равнялось 3. Поэтому P3 = 3! = 1х2х3 = 6.
7.3. Число размещений из n элементов по m
Прежде чем дать общее определение, рассмотрим вполне практическую задачу. Из группы в n человек требуется рассадить за столом в определенном порядке m человек (m
Пронумеруем m стульев. Тогда на первый стул можно усадить одного из n человек. Пусть первое место уже занято. На второе место остается n–1 претендент. Каждая из n возможностей занять первое место сочетается с n-1 возможностью занять второе место. Таким образом, имеется nх(n-1) вариантов занять первые

Ясно поэтому, что число размещений должно превосходить число сочетаний во столько раз, сколько можно сделать перестановок в множестве из m элементов, чтобы превратить его из неупорядоченного множества, сочетания, в то, что мы называем размещением. Иными словами, имеет место равенство
И отсюда окончательная формула для числа всевозможных сочетаний из n элементов по m
7.5.. Свойства биномиальных коэффициентов
Выражения , с которыми мы часто встречаемся в комбинаторике, называются биномиальными коэффициентами. И это не случайно, ибо они являются коэффициентами в знаменитом соотношении, именуемом биномом Ньютона:

Любопытно отметить, что биномиальные коэффициенты образуют так называемый треугольник Паскаля, в котором каждое новое число является суммой ближайших к нему двух чисел предыдущего ряда.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1