Перестановки. Комбинаторика – это раздел математики, занимающийся исследованием различных комбинаций элементов всевозможных множеств

Понятие множества

Тема № 2. ОСНОВЫ КОМБИНАТОРИКИ

Комбинаторика – это раздел математики, занимающийся исследованием различных комбинаций элементов всевозможных множеств. Формулы комбинаторики широко используются теории вероятностей, в теории вычислительных машин, в некоторых разделах экономике, в статистике и других прикладных дисциплинах.

Пусть A = {a₁,..., a_n} − конечное множество. Совокупность из k элементов множества A (не обязательно различных) называется k-выборкой множества A. Выборка называется упорядоченной, если каждому ее элементу поставлен в соответствие номер − натуральное число, не превосходящее k так, что разным элементам соответствуют разные числа. Упорядоченные выборки будем называть также наборами. Элементы упорядоченных выборок будем заключать в круглые скобки, а элементы неупорядоченных выборок − в фигурные скобки. Например, (a₁,a₂,a₂) и (a₂,a₁,a₂) − две различных упорядоченных выборки, а {a₁,a₂,a₂} и {a₂,a₁,a₂} − одна и та же неупорядоченная выборка.

Определение. Перестановкой n-элементного множества A = {a₁,..., a_n} называется любой набор (a_i1,...,a_in), состоящий из элементов A, в котором каждый элемент из A встречается ровно один раз.

Например, у трехэлементного множества {a₁,a₂,a₃} существует ровно шесть различных перестановок:

(a₁,a₂,a₃), (a₁,a₃,a₂),

(a₂,a₁,a₃), (a₂,a₃,a₁),

(a₃,a₁,a₂), (a₃,a₃,a₁).

Найдем число P_n различных перестановок n-элементного множества, где P − первая буква французского слова permutation − перестановка. Для этого возьмем n различных элементов a₁, a₂, a₃, … a_n и будем переставлять эти элементы всевозможными способами, оставляя без изменения число элементов и меняя только порядок их расположения. Тогда первый выбранный элемент станет первым элементом упорядоченной выборки, второй − вторым и т. д. Нетрудно видеть, что первый элемент можно выбрать n способами. Второй элемент будет выбираться из (n−1) оставшихся элементов, поэтому его можно выбрать (n − 1) способом. Продолжая выбор, заметим, что после выбора первых k элементов останется (n − k) невыбранных элементов. Следовательно, (k+1)-й элемент можно выбрать (n − k) способами.

Перемножив числа способов, которыми можно выбрать первый, второй,..., (n − 1)-й и n-й элементы, получим величину, равную числу способов, которыми можно упорядочить n-элементное множество.

Таким образом,

P_n = n · (n − 1) ·... · 2 · 1= n!

Такие перестановки называются перестановками без повторений (один и тот же элемент не может повториться в комбинации, все элементы различны).

Пример: шесть человек могут в разном порядке сесть за круглый стол, сколько существует способов разместить эти шесть человек за столом?

Решение: т.к. все люди различны и их комбинации различаются только порядком следования, то мы имеем перестановки без повторений. Определим их число:

Р(6) = 6! = 1 • 2 • 3 • 4 • 5 • 6 = 720.