Programming, robotics, traveling

23 Jun 2013

Комбинаторика: Перестановки и размещения

Статья явяляется заметкой из студенческого курса по теории вероятности.

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

Задача

Условие: На полке стоят 3 книги (a, b, c). Сколькими cпособами можно расставить книги на полке?

Решение: Pn - число перестановок. Перестановкой из n элементов называется каждое расположение этих элемнтов в определенном порядке.

Pn = n! = 1*2*3*…*(n-2)*(n-1)*nP3 = 3! = 1*2*3 = 6.

abc; acb; bac; bca; cab; cba.

Размещение: составим из элементов множества {a, b, c, d} все возможные пары, чтобы в каждой паре элементы не повторялись. A4^2, где 4 - количество элементов, 2 - количество значений в паре a,b; a,c; a,d; b,a; b,c; b,d; c,a; c,b; c,d; d,a; d,b; d,c;

Размещением из n элементов конечного множества по k, где k<=n, называется упорядоченное множество содержащее k элементов.

Теорема: Число размещений состаящих из n элементов по k

An^k = n!/(n-k)! = n*(n-1)*(n-2)*…*(n-(k-1)),

тоесть равно произведению k последующих натуральных чисел, большим из которых является n.

Замечание: 0!=1.