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

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

Тема № 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.